# [Direct BAT] Sword refers to the offer classic test questions (1)

3.1 Find the source of repeated numbers in the array: AcWing

Title description Given an integer array nums of length n, all the numbers in the array are in the range of 0 n 1.

Some numbers in the array are repeated, but I don't know how many numbers are repeated, and I don't know how many times each number is repeated.

Please find any duplicate number in the array.

Note: If some numbers are not in the range of 0 n 1, or the array does not contain repeated numbers, -1 will be returned;

Sample

Given nums = [2, 3, 5, 4, 3, 2, 6, 7].

Return 2 or 3. Solution After the solution is sorted, scan sequentially to determine whether there is a repetition. The time complexity is O(n ).

Solution 2: Use a hash table to traverse the array. If there is no such element in the hash table, store it in the hash table, otherwise return a duplicate element. The time complexity is O(n), and the space complexity is O(n).

Solution 3 The length is n, and the value range of the elements is also n. If there are no repeated elements, then the value corresponding to each subscript of the array is equal to the subscript.

Traverse the array from beginning to end, when scanning to the number nums[i] of the subscript i:

If it is equal to i, continue to scan down;

If it is not equal to i, compare it with the nums[i]th number. If it is equal, it means there is a duplicate value and return nums[i]. If they are not equal, exchange the i-th number with nums[i]-th number. Repeat this comparative exchange process.

The time complexity of this algorithm is O(n), because each element only needs to be exchanged twice at most to determine the position (for example, exchange 2 with 5, then 2 is in the correct position, and 5 needs to be exchanged again to run To the correct location). The space complexity is O(1).

``````class Solution {

/**
*
*
* @param nums
* @return
*/
public int duplicateInArray(int[] nums) {
if (nums == null || nums.length < 2) {
return -1;
}

int n = nums.length;
for (int e : nums) {
if (e < 0 || e > n - 1) {
return -1;
}
}
for (int i = 0; i < n; ++i) {
while (nums[i] != i) {
int val = nums[nums[i]];
if (nums[i] == val) {
return val;
}
swap(nums, i, nums[i]);
}
}
return -1;
}

private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
``````

3.2 Find the source of duplicate numbers without modifying the array: AcWing

Title description Given an array nums of length n+1, all the numbers in the array are in the range of 1 n, where n 1.

Please find any duplicate number in the array, but you cannot modify the input array.

Sample

Given nums = [2, 3, 5, 4, 3, 2, 6, 7].

Return 2 or 3. Thinking question: What should I do if I can only use the extra space of O(1)?

Solution Solution 1: Create an auxiliary array of length n+1, and copy the elements of the original array to the auxiliary array. If the copied number of the original array is m, put it at the mth position of the auxiliary array. This makes it easy to find duplicate elements. The space complexity is O(n).

The value range of the elements of the second array of solution is [1, n]. The range is divided in half, divided into [1, middle], [middle+1, n]. Calculate how many (count) elements in the array fall within the range of [1, middle]. If count is greater than middle-1+1, then there are duplicate elements in this range, otherwise it is in another range. Continue to divide this range in half and continue to count the number of elements in the range.

The time complexity is O(n * log n), and the space complexity is O(1).

Note that this method cannot find all duplicate elements.

``````class Solution {

/**
*  0
*
* @param nums
* @return
*/
public int duplicateInArray(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int start = 1, end = nums.length - 1;
while (start <= end) {
int mid = start + ((end - start) >> 1);
int cnt = getCountRange(nums, start, mid);
if (start == end) {
if (cnt > 1) {
//
return start;
}
break;
}
if (cnt > mid - start + 1) {
end = mid;
} else {
start = mid + 1;
}
}
return 0;
}

/**
*  [from, to]
*
* @param nums
* @param from
* @param to
* @return
*/
private int getCountRange(int[] nums, int from, int to) {
int cnt = 0;
for (int e : nums) {
if (e >= from && e <= to) {
++cnt;
}
}
return cnt;
}
}
``````

4 Search source in two-dimensional array: AcWing

The topic is described in a two-dimensional array, each row is sorted in increasing order from left to right, and each column is sorted in increasing order from top to bottom.

Please complete a function, input such a two-dimensional array and an integer to determine whether the integer is contained in the array.

Sample

Input array:

[[1,2,8,9], [2,4,9,12], [4,7,10,13], [6,8,11,15]]

If the input search value is 7, it returns true,

If the input search value is 5, it returns false. The solution starts from the upper right of the two-dimensional array:

If the element value is equal to target, return true;

If the element value is greater than target, cut off this column, namely --j;

If the element value is less than target, cut off this line, that is, ++i.

You can also start the search from the bottom left of the two-dimensional array. The following code uses the bottom left as the starting point for the search.

Note that you cannot select the numbers at the top left or bottom right, because this will not narrow the search range.

``````class Solution {

/**
*
*
* @param array
* @param target
* @return
*/
public boolean searchArray(int[][] array, int target) {
if (array == null || array.length < 1) {
return false;
}
int m = array.length, n = array.length;
int i = 0, j = n - 1;
while (i < m && j >= 0) {
if (array[i][j] == target) {
return true;
}
if (array[i][j] < target) {
++i;
} else {
--j;
}
}
return false;
}
}
``````

5 Source of replacement spaces: AcWing

Title description Please implement a function to replace each space in the string with "%20".

You can assume that the maximum length of the input string is 1000. Note that the length of the output string may be greater than 1000.

Sample

Input: "We are happy."

Output: "We%20are%20happy." Solution Solution One uses regular matching and replacement.

``````class Solution {

/**
*  %20
*
* @param str
* @return
*/
public String replaceSpaces(StringBuffer str) {
return str == null ? null : str.toString().replaceAll(" ", "%20");
}
}
``````

The second solution is to traverse the original string first, and when it encounters a space, append any two characters at the end of the original string, such as two spaces.

Use pointer i to point to the end of the original string, j to point to the end of the current string, i, j traverse from back to front, when i encounters a space, the j position should be assigned the values '0', '2','%' in turn, if Not a space, directly assign the character pointed to by i.

Idea expansion:

When merging two arrays (including strings), if copying each number (or character) from front to back needs to move the number (or character) multiple times, then we can consider copying from back to front, which can reduce the movement The number of times, thereby improving efficiency.

``````class Solution {

/**
*  %20
*
* @param str
* @return
*/
public String replaceSpaces(StringBuffer str) {
if (str == null) {
return null;
}

int len = str.length();
for (int i = 0; i < len; ++i) {
if (str.charAt(i) == ' ') {
str.append("  ");
}
}

int i = len - 1, j = str.length() - 1;
for (; i >= 0; --i) {
char ch = str.charAt(i);
if (ch == ' ') {
str.setCharAt(j--, '0');
str.setCharAt(j--, '2');
str.setCharAt(j--, '%');
} else {
str.setCharAt(j--, ch);
}
}
return str.toString();
}
}
``````

6 Print the linked list from end to beginning Source: AcWing

The title description enters the head node of a linked list, and returns the value of the node in order from the end to the head.

The returned result is stored in an array.

Sample

Input: [2, 3, 5] Return: [5, 3, 2] The solution traverses the linked list, pushes the value of each linked list node into the stack, and finally pops the elements in the stack into the array in turn.

``````/**
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {

/**
*
*
* @return
*/
return null;
}
Stack<Integer> stack = new Stack<>();
int cnt = 0;
while (cur != null) {
stack.push(cur.val);
cur = cur.next;
++cnt;
}

int[] res = new int[cnt];
int i = 0;
while (!stack.isEmpty()) {
res[i++] = stack.pop();
}
return res;
}
}
``````

7 Rebuild Binary Tree Source: AcWing

Title Description Input the results of pre-order traversal and middle-order traversal of a binary tree, please rebuild the binary tree.

Sample

Given: The pre-order traversal is: [3, 9, 20, 15, 7] The middle-order traversal is: [9, 3, 15, 20, 7]

Return: [3, 9, 20, null, null, 15, 7, null, null, null, null] The returned binary tree is as follows:
3/9 20/15 7 The solution is in the preorder traversal sequence of the binary tree, the first A number is always the value of the root node. In the middle-order traversal sequence, the value of the root node is in the middle of the sequence, the node of the left subtree is located to the left of the root node, and the node of the right subtree is located to the right of the value of the root node.

Traverse the in-order sequence, find the root node, recursively build the left subtree and the right subtree.

Pay attention to adding if judgments for special cases.

``````/**
* Definition for a binary tree node.
* class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {

/**
*
*
* @param preorder
* @param inorder
* @return
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length == 0 || preorder.length != inorder.length) {
return null;
}

return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}

private TreeNode build(int[] preorder, int[] inorder, int s1, int e1, int s2, int e2) {
int rootVal = preorder[s1];
TreeNode root = new TreeNode(rootVal);
if (s1 == e1) {
return root;
}

int i = s2, cnt = 0;
for (; i <= e2; ++i) {
if (inorder[i] == rootVal) {
break;
}
++cnt;
}

root.left = cnt > 0 ? build(preorder, inorder, s1 + 1, s1 + cnt, s2, i - 1) : null;
root.right = i < e2 ? build(preorder, inorder, s1 + cnt + 1, e1, i + 1, e2) : null;
return root;
}
}
``````

8 The source of the next node of the binary tree: AcWing

Title Description Given a node of a binary tree, please find the next node in the in-order traversal sequence.

note:

If the given node is the last in the middle-order traversal sequence, an empty node is returned;

The binary tree must not be empty, and the given node must not be an empty node.

Sample

Assuming that the binary tree is: [2, 1, 3, null, null, null, null], the node whose value is equal to 2 is given.

It should return a node with a value equal to 3.

Explanation: The structure of the binary tree is as follows, and the successor node of 2 is 3. 2/1 3 The solution for node p:

If it has a right subtree, the leftmost node of the right subtree is its next node;

If it does not have a right subtree, determine its position with the parent node p.father:

If it is the left child of the parent node, then the parent node p.father is its next node;

If it is the right child of the parent node, it keeps looking up until a certain node is found, which is the left child of its parent node, then the parent node is the next node of p.

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode father;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {

/**
*
*
* @param p
* @return p
*/
public TreeNode inorderSuccessor(TreeNode p) {
if (p == null) {
return null;
}

TreeNode cur = p.right;

//
if (cur != null) {
while (cur.left != null) {
cur = cur.left;
}
return cur;
}

//
TreeNode father = p.father;
while (father != null && father.left != p) {
p = father;
father = p.father;
}
return father;
}
}
``````

9.1 Use two stacks to implement the queue source: AcWing

For topic description, please use a stack to implement a queue, supporting the following four operations:

push(x)-Insert element x to the end of the queue.

pop(x)-Pop the element at the head of the line and return it.

peek()-Return the element at the head of the team.

empty()-Returns whether the queue is empty.

note:

You can only use the standard operations of the stack: push to top, peek/pop from top, size and is empty;

If the programming language you choose does not have a stack standard library, you can use list or deque to simulate stack operations;

The input data is guaranteed to be legal, for example, when the queue is empty, operations such as pop or peek will not be performed;

Sample

``````MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  //returns 1
queue.pop();   //returns 1
queue.empty(); //returns false
``````

Solution: Push operation is stored in s1 each time; pop operation is taken from s2 each time:

When the s2 stack is not empty, the s1 element cannot be poured into it;

When the s2 stack is empty, you need to pour all the s1 elements at once.

``````class MyQueue {

private Stack<Integer> s1;
private Stack<Integer> s2;

/** Initialize your data structure here. */
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}

/** Push element x to the back of queue. */
public void push(int x) {
s1.push(x);
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
int t = peek();
s2.pop();
return t;
}

/** Get the front element. */
public int peek() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.peek();
}

/** Returns whether the queue is empty. */
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}

/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
``````

9.2 Implement stack source with two queues: LeetCode

The topic describes the use of queues to implement the following operations of the stack:

push(x) - push element x onto the stack

pop() - remove the top element of the stack

top() - Get the top element of the stack

empty() - returns whether the stack is empty

note:

You can only use the basic operations of the queue--that is, push to back, peek/pop from front, size, and is empty operations are legal.

The language you are using may not support queues. You can use list or deque (double-ended queue) to simulate a queue, as long as it is a standard queue operation.

You can assume that all operations are valid (for example, no pop or top operations are called on an empty stack).

When the solution is out of the stack, the elements of the queue are first moved into another queue in turn, until there is one element left in the queue. Dequeue the element.

When pushing the stack, just push the element into the queue that is not empty. If both queues are empty, just push into one of the queues.

``````class MyStack {

private Queue<Integer> q1;
private Queue<Integer> q2;

/** Initialize your data structure here. */
public MyStack() {
}

/** Push element x onto stack. */
public void push(int x) {
if (empty() || q2.isEmpty()) {
q1.offer(x);
} else {
q2.offer(x);
}
}

/** Removes the element on top of the stack and returns that element. */
public int pop() {
if (q1.isEmpty()) {
while (q2.size() > 1) {
q1.offer(q2.poll());
}
return q2.poll();
}

while (q1.size() > 1) {
q2.offer(q1.poll());
}
return q1.poll();
}

/** Get the top element. */
public int top() {
int val = pop();
push(val);
return  val;
}

/** Returns whether the stack is empty. */
public boolean empty() {
return q1.isEmpty() && q2.isEmpty();
}
}

/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
``````

10.1 Fibonacci sequence source: AcWing

Title description Enter an integer n to find the nth term of the Fibonacci sequence.

Suppose it starts from 0, and the 0th item is 0. (n<=39)

Sample

Input integer n=5

Return 5 Solution Solution 1 uses a recursive method, which is concise and clear, but the efficiency is very low and there are a lot of repeated calculations.

``````                f(10)
/
f(9)         f(8)
/          /
f(8)     f(7)  f(7)   f(6)
/      /
f(7)  f(6)  f(6) f(5)
``````
``````class Solution {

/**
*  n n 0
*
* @param n  n
* @return  n
*/
public int Fibonacci(int n) {
if (n < 2) {
return n;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
``````

Solution 2: Calculate from bottom to top, recursively, time complexity is O(n). It can be stored in an array with a space complexity of O(n); it can also be stored in a variable with a space complexity of O(1).

``````class Solution {

/**
*  n n 0
*
* @param n  n
* @return  n
*/
public int Fibonacci(int n) {
if (n < 2) {
return n;
}

int a = 1, b = 1;
for (int i = 2; i < n; ++i) {
b = a + b;
a = b - a;
}
return b;
}
}
10.2
NowCoder

1 2 n

n   n-1   1   n-2   2

f(n) = f(n-1) + f(n-2)
class Solution {

/**
*
*
* @param target
* @return
*/
public int JumpFloor(int target) {
if (target < 3) {
return target;
}
int a = 1, b = 2;
for (int i = 3; i <= target; ++i) {
b = a + b;
a = b - a;
}
return b;
}
}
``````

10.3 Abnormal jump source: NowCoder

The title describes that a frog can jump up to one level or two at a time...it can also jump up to n levels. Find the total number of jumping methods the frog jumps on an n-level step.

Solution Solution 1: Mathematical derivation jumps to n-1 steps, you can jump from n-2 to 1 level, or from n-3 to 2... Then

f(n-1) = f(n-2) + f(n-3) + ... + f(0) Jump up to n steps, you can jump from n-1 to 1 level, or from n -2 level jumps up to level 2...then

f(n) = f(n-1) + f(n-2) + ... + f(0)

f(n)-f(n-1) = f(n-1) i.e.

f(n) = 2*f(n-1) so f(n) is a geometric sequence

class Solution {

``````/**
*  II
*
* @param target
* @return
*/
public int JumpFloorII(int target) {
return (int) Math.pow(2, target - 1);
}
``````

} Note that this solution has been simultaneously contributed to the open source repository CS-Notes.

Solution 2: Whenever dynamic programming calculates res[i], add up all the previous results.

``````class Solution {

/**
*  II
*
* @param target
* @return
*/
public int JumpFloorII(int target) {
if (target < 3) {
return target;
}
int[] res = new int[target + 1];
Arrays.fill(res, 1);
for (int i = 2; i <= target; ++i) {
for (int j = 1; j < i; ++j) {
res[i] += res[j];
}
}
return res[target];
}
}
``````

10.4 Rectangular coverage source: NowCoder

The title describes that we can use 2 1 small rectangles horizontally or vertically to cover larger rectangles. How many ways are there to cover a large 2*n rectangle with n 2 1 small rectangles without overlapping?

The solution covers a 2*n rectangle:

You can cover a 2 n-1 rectangle first, and then cover a 2 1 rectangle;

You can also cover a 2*(n-2) rectangle first, and then cover two 1*2 rectangles.

Solution 1: Use an array to store the result

``````class Solution {

/**
*
*
* @param target 2*target
* @return
*/
public int RectCover(int target) {
if (target < 3) {
return target;
}
int[] res = new int[target + 1];
res = 1;
res = 2;
for (int i = 3; i <= target; ++i) {
res[i] = res[i - 1] + res[i - 2];
}
return res[target];
}
}
``````

Solution 2: Use variables directly to store the result

``````class Solution {

/**
*
*
* @param target 2*target
* @return
*/
public int RectCover(int target) {
if (target < 3) {
return target;
}
int a = 1, b = 2;
for (int i = 3; i <= target; ++i) {
b = a + b;
a = b - a;
}
return b;
}
}
``````

11 The smallest number source of the rotating array: AcWing

The title describes moving several elements from the beginning of an array to the end of the array, which we call the rotation of the array.

Input a rotation of an ascending array, and output the smallest element of the rotated array.

For example, the array {3,4,5,1,2} is a rotation of {1,2,3,4,5}, and the minimum value of the array is 1.

The array may contain duplicates.

Note: The elements contained in the array are non-negative. If the size of the array is 0, please return -1.

Sample

Input: nums=[2,2,2,0,1]

Output: 0 Solution Solution 1 traverse the array directly to find the minimum value. The time complexity is O(n), which is not recommended.

``````class Solution {

/**
*
*
* @param nums
* @return
*/
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int min = nums;
int n = nums.length;
if (min < nums[n - 1]) {
return min;
}
for (int i = 1; i < n; ++i) {
min = Math.min(min, nums[i]);
}
return min;
}
}
``````

Solution 2: Use the pointers start and end to point to the beginning and the end of the array. If nums[start] <nums[end], it means that the array is an increasing array, and return nums[start] directly. Otherwise, proceed as follows.

Calculate the middle pointer mid:

If nums[start], nums[end], nums[mid] are equal to each other at this time, the dichotomy method cannot be used at this time, and the minimum value can only be obtained by traversing the interval [start, end);

If start and end are adjacent at this time, it means that the element pointed to by end is the minimum value, and nums[end] is returned;

If nums[mid] >= nums[start] at this time, it means that mid is in the incrementing array on the left, and the minimum value is on the right. Therefore, point start to mid and keep start pointing to the incrementing sub-array on the left;

If nums[mid] <= nums[end] at this time, it means that mid is in the increasing array on the right, and the minimum value is on the left. Therefore, point end to mid, and keep end pointing to the increasing sub-array on the right.

``````/**
* @author bingo
* @since 2018/12/17
*/

class Solution {

/**
*
*
* @param nums
* @return
*/
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0, end = nums.length - 1;

if (nums[start] < nums[end]) {
//
return nums[start];
}
while (end - start > 1) {
int mid = start + ((end - start) >> 1);
if (nums[start] == nums[end] && nums[mid] == nums[start]) {
// [start, end)
return findMin(nums, start, end);
}
if (nums[mid] >= nums[start]) {
start = mid;
} else {
end = mid;
}
}
return nums[end];
}

private int findMin(int[] nums, int start, int end) {
int min = Integer.MAX_VALUE;
for (int i = start; i < end; ++i) {
min = Math.min(min, nums[i]);
}
return min;
}
}
``````

12 Path source in the matrix: AcWing

Title description Please design a function to determine whether there is a path that contains all the characters of a string in a matrix.

The path can start from any grid in the matrix, and each step can move one grid to the left, right, up, and down in the matrix.

If a path passes through a certain grid in the matrix, it cannot enter this grid again afterwards.

note:

The path entered is not empty;

All characters appearing are uppercase English letters.

Sample

matrix = [['A','B','C','E'], ['S','F','C','S'], ['A','D','E ','E']]

str="BCCE", return "true"

str="ASAE", return "false" solution backtracking method. 1. choose a grid as the starting point of the path. Assume that the character corresponding to the grid is ch, and it corresponds to the i-th character on the path. If they are equal, find the i+1th character on the path to the adjacent grid. Repeat this process.

``````class Solution {

/**
*
*
* @param matrix
* @param str
* @return
*/
public boolean hasPath(char[][] matrix, String str) {
if (matrix ==  null || matrix.length == 0 || str == null) {
return false;
}

int m = matrix.length, n = matrix.length;

boolean[][] visited = new boolean[m][n];
int pathLength = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (hasPath(matrix, str, i, j, visited, pathLength)) {
return true;
}
}
}
return false;
}

private boolean hasPath(char[][] matrix, String str, int i, int j, boolean[][] visited, int pathLength) {
if (pathLength == str.length()) {
return true;
}
boolean hasPath = false;
if (i >= 0 && i < matrix.length && j >= 0 && j < matrix.length
&& !visited[i][j] && matrix[i][j] == str.charAt(pathLength)) {
++pathLength;
visited[i][j] = true;
hasPath = hasPath(matrix, str, i + 1, j, visited, pathLength)
|| hasPath(matrix, str, i - 1, j, visited, pathLength)
|| hasPath(matrix, str, i, j + 1, visited, pathLength)
|| hasPath(matrix, str, i, j - 1, visited, pathLength);
if (!hasPath) {
--pathLength;
visited[i][j] = false;
}
}
return hasPath;
}
}
``````

Scan the QR code below to get more Internet job search skills , java , python , crawlers , big data and other technologies in time, and share massive data : reply " csdn " in the background of the official account to receive [csdn] and [Baidu Library] for free Download service; the official account backstage reply " data ": you can receive 5T high-quality learning materials , java interview test center and java face-to-face summary , as well as dozens of java and big data projects . The information is very complete, and almost everything you want to find