Chapter II basic knowledge required for interview
1. Array
Sword finger Offer 03 Duplicate number in array
Find duplicate numbers in the array. All numbers in an array num of length n 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, or how many times each number is repeated. Please find any duplicate number in the array.
Input: [2, 3, 1, 0, 2, 5, 3] Output: 2 or 3
-
Scan complexity after sorting O(nlogn)
-
Hash table, space complexity O(n), time complexity O(n)
In situ hashing: some elements repeat many times, and some elements do. In situ hashing is used, and a correct element must be in the appropriate position. During traversal, each time compare whether the current element repeats with the appropriate position. If there is no repetition, put it in the appropriate position.
Time complexity O(n), space complexity O(1)
int findRepeatNumber(vector<int>& nums) {
for(int i = 0;i < nums.size(); ++i){//Scan from beginning to end
if(nums[i] == i) continue;//If nums[i] is in the right position, continue to scan forward
else{//If not in place
if(nums[i] == nums[ nums[i] ]) return nums[i];//Compare whether the current element repeats with the element in the appropriate position
else swap(nums[i],nums[nums[i]]);//If not repeated, put the current element in the appropriate position
}
}
return 0;
}
Deformation problem: find out duplicate numbers without modifying the array
- Create an auxiliary array with a length of n+1, and copy the element M of the original array to the position corresponding to the subscript m of the new array one by one. If the position has been modified, the number is repeated. Spatial complexity O(n).
- Dichotomy: Taking the midpoint m of 0n-1 as the boundary, if the number less than m exceeds m, it indicates that there is repetition in the first m, on the contrary, it proves that there is repetition in the last M. Then take 0m-1 as the boundary, continue to narrow the range, continue to narrow the range, and the repeated number can be found. The space complexity is O(1) and the time complexity is O(nlogn). Trade time for space.
Sword finger Offer 04 Find in 2D array
In an n * m two-dimensional array, each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Please complete an efficient function, input such a two-dimensional array and an integer, and judge whether the array contains the integer.
Existing matrix matrix As follows: [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] given target = 5，return true. given target = 20，return false.
**To solve a complex problem, we try to find the general law by analyzing simple and specific examples** It is found that the analysis starts from the upper right corner as a breakthrough.
//Traverse from the upper right corner. If it is smaller than the target, go down. If it is larger than the target, go left
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if(matrix.empty()) return false;
int n = matrix.size(),m = matrix[0].size();
int i = 0,j = m-1;
while(i < n && j >= 0){
if(matrix[i][j] == target) return true;
else if(matrix[i][j] < target){
++i;
}else{
--j;
}
}
return false;
}
2. String
Each string ends with the character '\ 0', so pay attention to out of bounds.
Sword finger Offer 05 Replace spaces
Please implement a function to replace each space in the string s with "% 20".
Input: s = "We are happy." Output:"We%20are%20happy."
- The first one: modify the original character, then it is possible to overwrite the content after the modified character. Therefore, all characters after the space need to be moved back by 2 bytes. Because all characters after each space have to move, the time complexity is O(n^2)
- Second: create a new enough string and copy it on the new string. Create a double pointer. From back to front, the old pointer points to the end of the old string and the new pointer points to the end of the new string. When encountering a space, the old pointer - 1 and the new pointer - 3; When a character is encountered, copy the corresponding character to the new string.
Are you highly alert to memory overwrite
string replaceSpace(string str) {
if(str.empty()) return "";
int count = 0;//Count the number of spaces
for(auto & s:str){
if(s == ' ') ++count;
}
int last = str.size()-1,newlast = str.size()+2*count-1;//last points to the end of the original array and newlast points to the end of the new array
string res(newlast+1,'0');
while(last >= 0){
if(str[last] == ' '){//If spaces are encountered, replace with "% 20"
--last;
res[newlast--] = '0';
res[newlast--] = '2';
res[newlast--] = '%';
continue;
}
res[newlast] = str[last];
--last;
--newlast;
}
return res;
}
3. Linked list
Sword finger Offer 06 Print linked list from end to end
Enter the head node of a linked list, and return the value of each node from tail to head (returned by array).
Input: head = [1,3,2] Output:[2,3,1]
- The first reaction of this problem is to reverse the linked list and modify the pointer, but this will change the structure of the original linked list.
If you intend to modify the input data during the interview, be sure to ask the interviewer in advance whether it is allowed to modify it.
-
Considering that the original linked list structure can not be modified, the traversal is adopted from beginning to end, and the results of each traversal are stored in the stack, and finally out of the stack.
-
It is realized by recursion. When accessing a node, first recursively output the node behind it, and then output the node itself. In this way, the output result of the linked list is reversed. When the linked list is very long, it will lead to the deep level of function call, which may lead to the overflow of function call stack. The code explicitly implemented by stack based on loop is more robust.
vector<int> reversePrint(ListNode* head) {
vector<int> res;
stack<int> sk;
if(!head) return res;
while(head){
sk.push(head->val);
head = head->next;
}
while(!sk.empty()){
res.emplace_back(sk.top());
sk.pop();
}
return res;
}
4. Trees
Sword finger Offer 07 Binary tree reconstruction
Enter the results of preorder traversal and inorder traversal of a binary tree, please rebuild the binary tree. It is assumed that the input pre order traversal and middle order traversal results do not contain duplicate numbers.
Preorder traversal preorder = [3,9,20,15,7]
Middle order traversal inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
The first value 3 of the preamble traversal is the root node, and this node is new. Quickly find the coordinates of 3 in the middle order traversal. Then 3 is the node of the left subtree before 3 and the node of the right subtree after 3. Recurse the front order and middle order array range of the left subtree and right subtree respectively. In order to quickly find the position of an element in the middle order traversal, establish the relationship between hashmap mapping elements and coordinates.
I've done this question many times, but I still make mistakes when I return the range of the subtree around.
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.empty() || inorder.empty() ) return nullptr;
unordered_map<int,int> hash;
for(int i = 0;i < inorder.size(); ++i){
hash[ inorder[i] ] = i;
}
return rebuildTree(preorder, hash, 0, preorder.size()-1, 0, inorder.size()-1 );
}
TreeNode* rebuildTree(vector<int>& preorder, unordered_map<int,int> &hash, int preStart, int preLast, int inStart, int inLast){
if(preStart > preLast || inStart > inLast) return nullptr;
int val = preorder[preStart];//The value of the root node
TreeNode * node = new TreeNode(val);
int inIndex = hash[val];//Coordinates of the root node in the middle order traversal
int leftlength = inIndex - inStart;//Left subtree length
node->left = rebuildTree(preorder, hash, preStart + 1, preStart + leftlength, inStart, inIndex-1);
node->right = rebuildTree(preorder, hash,preStart + leftlength + 1, preLast, inIndex + 1, inLast);
return node;
}
5. Stack and queue
Sword finger Offer 09 Queue with two stacks
Two stacks: one stack input, as the main storage, is always push ed. When delete is required, another stack is used as auxiliary output. If the output stack is not empty, the top element of the stack is deleted; If the output stack is empty, all the input stacks will be out of the stack to the output stack, and then the top element of the stack will be deleted. Note that every time the output stack is deleted, a new round of elements of the input stack are pressed on the stack.
class CQueue {
private:
stack<int> input,output;
public:
CQueue() {}
void appendTail(int value) {
input.push(value);
}
int deleteHead() {
in2out();
if(output.empty()) return -1;//Note that you need to judge here. output is empty and return-1
int res = output.top();
output.pop();
return res;
}
//Pop up all the data of the input stack at one time and press it into the output stack, so that the order of the sub output stack is the order of the queue
void in2out(){
if(output.empty()){
while(!input.empty()){
int temp = input.top();
input.pop();
output.push(temp);
}
}
}
};
Deformation problem: using two queues to realize stack
- Each time you want to store an element, first enter team 1, then all the elements in team 2 are out of the team, and enter team 1. Finally, exchange queue 1 and queue 2. In this way, the first element in queue 2 is always the latest stored element. So as to realize first in first out.
6. Recursion and loop
Sword finger Offer 10- I. Fibonacci sequence
Write a function, enter n, and find the nth term of Fibonacci sequence (i.e. F(N)). Fibonacci sequence is defined as follows:
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), among N > 1.
The Fibonacci sequence starts with 0 and 1, and the subsequent Fibonacci numbers are obtained by adding the previous two numbers. If the answer is 1000000007, please return the initial result of 1000000007.
-
The recursive solution will be considered at the beginning. As shown in the figure below, many nodes in this tree are duplicate, and the number of duplicate nodes will increase sharply with the increase of n.
[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-gjCwLS6Q-1621498837164)(images/image-20210519145352047.png)]
-
So it's best to save the middle term of the obtained sequence and look it up the next time. Similar to space compression in dynamic programming.
int fib(int n) { if(n < 2) return n; long long f0 = 0;//Values of the first two states long long f1 = 1;//Value of the previous state long long fN = 0;//Current status value for(int i = 2;i <= n; ++i){ fN = (f1 + f0)%1000000007;//The current state value is only related to the first two states f0 = f1; f1 = fN; } return fN; }
Sword finger Offer 10- II Frog jumping steps
A frog can jump up one step or two steps at a time. Find out the total number of jumping methods for the frog to jump up an n-step step. If the answer is 1000000007, please return the initial result of 1000000007.
Input: n = 7 Output: 21
There are two ways to reach the current step. The first is to jump one step from the previous step or two steps from the previous two steps. Therefore, the jump method of the current step is the sum of the jump methods of the previous step and the previous two steps dp[i] = dp[i-1] + dp[i-2]
/*
int numWays(int n) {
if(n < 2) return 1;
vector<int> dp(n+1,0);//dp[i]Indicates the total number of jumping methods for the i-th step
dp[0] = 1;//0 There is one jumping method for steps
dp[1] = 1;//1 There is a jumping method for steps
for(int i = 2;i <= n;++i){
dp[i] = (dp[i-1] + dp[i-2])%1000000007;
}
return dp[n];
}
*/
//Similar to Fibonacci, the space is reduced and compressed
int numWays(int n){
if(n < 2) return 1;
int step0 = 1,step1 = 1,stepN = 0;
for(int i = 2;i <= n; ++i){
stepN = (step0 + step1)%1000000007;
step0 = step1;
step1 = stepN;
}
return stepN;
}
Sword finger Offer 11 Minimum number of rotation array
Moving the first elements of an array to the end of the array is called array rotation. Enter a rotation of an incrementally sorted array and output the smallest element of the rotation array. For example, if the array [3,4,5,1,2] is a rotation of [1,2,3,4,5], the minimum value of the array is 1.
Input:[3,4,5,1,2] Output: 1
Find the minimum value in the rotation array. The minimum value should be the boundary of rotation. Using dichotomy: if the value of the current midpoint is less than or equal to the right end, the right interval is in good order; On the contrary, it shows that the left interval is in good order.
The difficulty of this problem is: if there are duplicate elements in the array, it is possible that when the median value = = the right end value, it is impossible to judge which interval is in good order, so it is necessary to separate right -. Equivalent to interval traversal.
int minArray(vector<int>& numbers) {
int left = 0, right = numbers.size()-1;
int minNum = numbers[right];
while(left <= right){
int mid = (left + right)/2;
minNum = min(minNum,numbers[mid]);
if(numbers[mid] < numbers[right]){//The right half is in normal order, and the minimum value may be in the left half
right = mid-1;
}else if(numbers[mid] > numbers[right]){//The left half is in normal order, and the minimum value may be in the right half
minNum = min(minNum,numbers[left]);
left = mid+1;
}else{//If equal, it is not possible to determine which half is in the normal order
--right;
}
}
return minNum;
}
7. Backtracking method
Sword finger offer12 Path in matrix
Given an m x n two-dimensional character grid board and a string word word. If word exists in the grid, return true; Otherwise, false is returned.
Words must be formed alphabetically by letters in adjacent cells, where "adjacent" cells are those horizontally or vertically adjacent. Letters in the same cell cannot be reused.
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true
bool exist(vector<vector<char>>& board, string word) {
if(word.empty()) return true;
if(board.empty() || board[0].empty()) return false;
int m = board.size(),n = board[0].size();
vector<vector<bool>> visited(m, vector<bool>(n,false));//falg indicates whether each character is part of a word
bool isFind = false;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
traceBack(board, word, visited, 0, i, j, isFind);
if(isFind) return true;
}
}
return false;
}
void traceBack(vector<vector<char>>& board, string &word, vector<vector<bool>> &visited, int pos, int i, int j, bool & isFind){
if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) return;//If you cross the line, return
if(visited[i][j] || isFind || board[i][j] != word[pos]) return;//Accessed, or found, or the current search does not match, return
if(pos == word.size()-1){//The current search character is just the last match, indicating that the word is found
isFind = true;
return;
}
visited[i][j] = true;
traceBack(board, word, visited, pos + 1, i - 1, j, isFind);//upper
traceBack(board, word, visited, pos + 1, i + 1, j, isFind);//lower
traceBack(board, word, visited, pos + 1, i, j - 1, isFind);//Left
traceBack(board, word, visited, pos + 1, i, j + 1, isFind);//right
visited[i][j] = false;//Backtracking modification status
}
Sword finger Offer 13 Range of motion of robot
The grid has a row of coordinates [0-m] from n-0 to [1-m]. A robot starts to move from the grid of coordinates [0,0]. It can move left, right, up and down one grid at a time (it can't move outside the grid), and it can't enter the grid where the sum of digits of row coordinates and column coordinates is greater than k. For example, when k is 18, the robot can enter the grid [35, 37], because 3 + 5 + 3 + 7 = 18. But it cannot enter the grid [35, 38], because 3 + 5 + 3 + 8 = 19. How many grids can the robot reach?
Input: m = 2, n = 3, k = 1 Output: 3
According to the digit and increment formula, the digit and increment change once every carry. According to this feature, the geometric shape formed by the solution satisfying the sum of digits in the matrix is like multiple isosceles right triangles. Because the robot can only take one step at a time, and the triangles are not necessarily connected, the robot may not be able to reach all the points satisfying the sum of digits. Due to the existence of unreachable solution, it is impossible to directly traverse and count the area of multiple triangles.
The robot starts from the coordinates (0, 0). When it is ready to enter the coordinates (i, j), it first judges whether it has crossed the boundary, has been visited, or does not meet the digits. If it cannot enter, it returns to 0 and the area does not change; If you can enter, modify the point that has been accessed, and search the other four adjacent directions, and the area is + 1.
int movingCount(int m, int n, int k) {
if(!k) return 1;
vector<vector<bool>> visited(m,vector<bool>(n,false));//Has it arrived
return traceBack(visited, 0, 0, k);
}
int traceBack(vector<vector<bool>> & visited, int i, int j, int &k){
if(i < 0 || i >= visited.size() || j < 0 || j >= visited[0].size() || visited[i][j] || getSum(i) + getSum(j) > k) return 0;
//Out of bounds, visited, and greater than k, return 0
visited[i][j] = true;//Change the accessed to true
return 1 + traceBack(visited, i - 1, j, k) + traceBack(visited, i + 1, j, k) + traceBack(visited, i, j - 1, k) + traceBack(visited, i, j + 1, k);
}
int getSum(int num){//Calculate the sum of the bits of a number
int sum = 0;
while(num){
sum += num%10;
num /= 10;
}
return sum;
}
8. Dynamic programming and greedy algorithm
Sword finger Offer 14- I. cut the rope
Here is a rope with length n. please cut the rope into m segments of integer length (M and N are integers, n > 1 and M > 1). The length of each segment of rope is recorded as k[0],k[1]... k[m-1]. What is the possible maximum product of k[0]k[1]... * k[m-1]? For example, when the length of the rope is 8, we cut it into three sections with lengths of 2, 3 and 3 respectively. At this time, the maximum product is 18.
input: 2 output: 1 explain: 2 = 1 + 1, 1 × 1 = 1
DP [1], DP [2] and DP [4] here are not the optimal solutions cut after the real length is 1, 2 and 3. Because they are products, multiplying by 1 is equivalent to invalid, so the initial values are stored in advance for the first three states. DP [4] = max (1 * 3, 2 * 2, 3 * 1) = 4 ` ` DP [5] = max (1 * 4, 2 * 3 = = 6, that is, dp[n] = max(dp[i] * dp[n-i])
int cuttingRope(int n) {
if(n < 2) return 0;//If the rope length is 0,1, the maximum product is 0
if(n <= 3) return n-1;//If the rope length is 2, the product is 1; The length is 3 and the product is 2
vector<int> dp(n+1,0);//The optimal solution of the rope with length i after being cut
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
for(int i = 4; i <= n; ++i){
for(int j = 1; j <= i/2; ++j){
dp[i] = max(dp[i], dp[j] * dp[i-j]);
}
}
return dp[n];
}
Sword finger Offer 14- II Cut rope II
Use greedy algorithm to solve the above problem: when the rope length > = 5, cut it into each small segment with length of 3; Rope length = = 4, cut into two small sections with length of 2.
int cuttingRope(int n) {
if(n < 2) return 0;
if(n <= 3) return n-1;
long res = 1;
while(n>4){//When the length of the rope is more than 4, it will be cut into 3d
res = ( res * 3 )%1000000007;
n -= 3;
}
return ( res*n) %1000000007;
}
9. Bit operation
Sword finger Offer 15 Number of 1 in binary
Please implement a function to input an integer (in the form of binary string) and output the number of 1 in the binary representation of the number. For example, representing 9 as binary is 1001, and 2 bits are 1. Therefore, if you enter 9, the function outputs 2.
Input: 0000000000000000000000001011 Output: 3
Shift right operation. If the number is unsigned, fill the high order with 0; If it is a signed number, the high bit is filled with sign bits. For example, if the number was originally negative, move it to the right and fill in n zeros on the left.
/*Note: shifting n to the right and doing & operation with 1 may lead to an endless loop, because unsigned numbers are shifted to the right and the high position is supplemented by 0, but if it is a negative number, the high position is supplemented by 1 after shifting to the right;
Method 1: so this question should be to move 1 left until it becomes 0 after moving left 32 times
int hammingWeight(uint32_t n) {
int count = 0;
uint32_t flag = 1;
while(flag){
if( n&flag ) ++count;
flag <<= 1;
}
return count;
}*/
/*No matter how many 1s there are in method 1, it needs to be run 32 times.
Method 2: run several times when there are several 1s in the integer.
Subtracting an integer by 1, and then doing the sum operation with the original integer, will turn the rightmost 1 of the original integer into 0, so a binary number with several 1s can do this operation several times.
*/
int hammingWeight(uint32_t n) {
int count = 0;
while(n){
++count;
n = (n-1)&n;
}
return count;
}