The first day
1. Lookup in a two-dimensional array
describe
In a two-dimensional array (each one-dimensional array is the same length), each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Complete a function that takes such a two-dimensional array and an integer and determines whether the integer is in the array. ,4,9,12,2,8,9 [[1], [2], [4,7,10,13], [6,8,11,15]] for a given target = 7, return true. Given target = 3, return false.
The last element in the first line is smaller than the left one and larger than the bottom one.
We can do binary search _
Time complexity: O (m+ N)
public boolean Find(int target, int[][] array) {
if (array == null) {
return false;
}
int row = array.length;
int col = array[0].length;
if (row == 0 || col == 0) {
return false;
}
int x = 0;
int y = col - 1;
while (x < row && y >= 0) {
if (array[x][y] == target) {
return true;
} else if (array[x][y] > target) {
y--;
} else{ x++; }}return false;
}
Copy the code2.Print the linked list from end to end
Description: Enter the first node of a linked list and return the value of each node in the order from the end of the list (as an array). www.nowcoder.com/practice/d0… 1. Use recursive space complexity O (n), time complexity O (n) Some interviewers may need to use a recursive approach to handle 2. O (n); o(n); O (n); o(n)
/** the recursive solution */
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> result = new ArrayList<>();
return recursive(listNode, result);
}
public ArrayList<Integer> recursive(ListNode node, ArrayList<Integer> list) {
if (node == null) {
return list;
}
recursive(node.next,list);
list.add(node.val);
return list;
}
/** Reverse linked list solution */
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> result = new ArrayList<>();
ListNode listNode1 = reverseList(listNode);
if (listNode1 == null) {
return result;
}
while(listNode1 ! =null) {
result.add(listNode1.val);
listNode1 = listNode1.next;
}
return result;
}
/** reverse linked list */
public ListNode reverseList(ListNode node) {
if (node == null || node.next == null) {
return node;
}
ListNode pre = null;
ListNode cur = node;
ListNode next;
while(cur ! =null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
/** Stack - based solutions are not described */
Copy the code3.Rebuild the binary tree
Description: Input the result of foreorder traversal and middle order traversal of a binary tree, please reconstruct the binary tree. It is assumed that the result of both the preceding and the middle traversal of the input does not contain duplicate numbers. For example, input preorder traversal sequence {1,2,4,7,3,5,6,8} and intermediate order traversal sequence {4,7,2,1,5,3,8,6}, then rebuild the binary tree and return.
Idea: recursive call, simulation
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
if (pre == null || in == null) {
return null;
}
int preLength = pre.length;
int inLength = in.length;
if (preLength == 0 || inLength == 0|| preLength ! = inLength) {return null;
}
return recursive(pre, in, 0, preLength - 1.0, inLength - 1);
}
public TreeNode recursive(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart < 0 || preStart > preEnd || inStart < 0 || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(pre[preStart]);
int leftCount = -1;
int rightCount = -1;
int inRootIndex = -1;
for (int i = inStart; i <= inEnd; i++) {
if (in[i] == pre[preStart]) {
inRootIndex = i;
}
}
leftCount = inRootIndex - inStart;
rightCount = inEnd - inRootIndex;
if (leftCount > 0) {
root.left = recursive(pre, in, preStart + 1, preStart + leftCount, inStart, inRootIndex - 1);
}
if (rightCount > 0) {
root.right = recursive(pre, in, preEnd - rightCount + 1, preEnd, inEnd - rightCount + 1, inEnd);
}
return root;
}
Copy the code4.Implement queues with two stacks
Describes the implementation of a queue with two stacks, respectively, to insert the integer at the end of the queue (push) and delete the integer at the head of the queue (pop) function. Elements in the queue are of type int. Ensure that the operation is valid, that is, ensure that there are elements in the queue when the POP operation is performed.
Example: Enter: [“PSH1″,”PSH2″,”POP”,”POP”]
Return: 1,2 parse: “PSH1”: insert 1 into the end of the queue “PSH2”: insert 2 into the end of the queue “POP “: delete an element, fifO => return 1
“POP “: deletes an element, first in, first out => returns 2
Example 1 Enter: [“PSH1″,”PSH2″,”POP”,”POP”] Returned value: 1,2
public class Solution {
private Stack<Integer> mInStack = new Stack<>();
private Stack<Integer> mOutStack = new Stack<>();
public int pop(a) {
if (mOutStack.isEmpty()) {
while (!mInStack.isEmpty()) {
mOutStack.push(mInStack.pop());
}
}
if (mOutStack.isEmpty()) {
throw new RuntimeException("Queue empty");
}
return mOutStack.pop();
}
public void push(int val) { mInStack.push(val); }}Copy the code5.Rotate the smallest element of the array
The difficulty with binary search is who arr[mid] is compared to.
Our goal is to make sure that when we do a comparison, the answer is on either side of mid. A comparison of ARR [mid] and who compared the problem. The general principles of comparison are:
- If there is a target value, then simply compare arR [mid] to target.
- If you don’t have a target value, you can generally consider endpoints
Here, we treat target as the right endpoint, and analyze the following three situations to see if the above objective can be achieved.
- Arr [mid] > target: 4, 5, 6, 1, 2, 3
- Arr [mid] = 6, target = 3, arr[mid] > target, arr[mid] >= target Mid +1 = mid+1 = mid+1 = mid+1
- Arr [mid] < target:5, 6, 1, 2, 3, 4
- [mid] = 1 and [mid] = 1 and [mid] = 1 and [mid] = 1 and [mid] = 1 and [mid] = 1 So last = mid;
- Case 3, arr[mid] == target:
- If it’s 1, 0, 1, 1, 1, arr[mid] = target = 1, obviously the answer is on the left
- If it’s 1, 1, 1, 0, 1, arr[mid] = target = 1, obviously the answer is on the right
So in this case, you can’t decide if the answer is on the left or the right, so last = last-1; Narrow it down slowly and don’t miss the answer.
public int minNumberInRotateArray(int[] array) {
int left = 0;
int right = array.length - 1;
int mid;
while (left < right) {
mid = left + (right - left) / 2;
if (array[left] < array[right]) {
return array[left];
}
if (array[mid] > array[left]) {
left = mid + 1;
} else if (array[mid] < array[left]) {
right = mid;
} else{ left++; }}return array[left];
}
Copy the code6.Fibonacci numbers
We all know the Fibonacci sequence, and now we’re asking for an integer n, so please print the NTH term of the Fibonacci sequence (starting at 0, the 0th term is 0, and the first term is 1).
N \leq 39_n_≤39 1. Recursive solution 2. Dynamic programming 3. Optimization of dynamic programming (remember the median)
// Recursion time is 2 to the n
public int Fibonacci(int n) {
if(n<=1) {return n;
}
return Fibonacci(n-1)+Fibonacci(n-2);
}
// Dynamic planning time o(n) space O (n)
public int Fibonacci(int n) {
int[] dp = new int[n+1];
if (n <= 1) {
return n;
}
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
/ / optimization
public int Fibonacci(int n) {
if (n <= 1) {
return n;
}
int x = 0;
int y = 1;
for (int i = 2; i <= n; i++) {
int t = y;
y = x+y;
x = t;
/ / or
//y += x;
//x = y-x;
}
return y;
}
Copy the code7.Dance steps
A frog can jump up one step or two at a time. Find out how many ways the frog can jump up a n step (different order counts different results). f(n) = f(n-1)+f(n-2); The solution is the same as problem 6
8.Jump step extension problem
A frog can jump up one step at a time, or two… It can also jump up n levels. Find the total number of ways the frog can jump up an n step (n is a positive integer). F (n) = f(n-1)+f(n-2)+……. + 1; f(n-1) = f(n-2)+f(n-3)+…. + 1; So f(n) = 2f(n-1);
public int JumpFloorII(int target) {
if(target==1) {return 1; }if(target==2) {return 2; }int x = 2;
for(int i=3; i<=target; i++){ x=x<<1;
}
return x;
}
Copy the code9.The rectangle cover
We can cover a larger rectangle with a smaller rectangle of 21 horizontal or vertical. How many different ways are there in the same direction to cover a 2 by N rectangle with n small rectangles of 21 without overlapping?
Answer key with6and7
Copy the code