Sword finger offer Second Edition
1. Duplicate numbers in the array (Offer-03)
Use both sets and dictionaries.
var findRepeatNumber = function(nums) {
let map = new Set()
for(let i = 0; i < nums.length; i++) {
const n = nums[i]
if(map.has(n)) {
return n
}
map.add(n)
}
};
2. Search in two-dimensional array (Offer-04)
The violent solution is relatively simple, and the optimization algorithm is considered below.
Solution:
-
Carefully look at the conditions of the topic. Each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom.
-
We need to make full use of the conditions of the topic.
-
Based on the subject conditions, we compare the size of the array element in the lower left corner with the target.
-
If the target is larger, the first column of the two-dimensional array can be excluded. (each column is sorted in ascending order from top to bottom)
-
Similarly, if the target is smaller, the last row of the two-dimensional array can be excluded. (each row is sorted in ascending order from left to right)
-
Finally, if an element equal to target is found, return true; otherwise, return false.
var findNumberIn2DArray = function(matrix, target) { let i = matrix.length - 1, j = 0 while(i >= 0 && j < matrix[0].length) { if(matrix[i][j] < target) { j++ }else if(matrix[i][j] > target){ i-- }else { return true } } return false };
3. Replace spaces (Offer-05)
My solution: I called the split() and join() methods
var replaceSpace = function(s) {
const res = s.split(" ")
return res.join("%20")
};
Solution 2: this solution is more efficient.
var replaceSpace = function(s) {
let re = ""
for(let i = 0; i < s.length; i++) {
if(s[i] === " ") {
re = re + "%20"
continue
}
re = re + s[i]
}
return re
};
4. Print the linked list from beginning to end (Offer-06)
The reverse() method of array can be used for this problem; You can also choose to use the stack method to solve.
Solution 1:
var reversePrint = function(head) {
const res = []
let p = head
while(p) {
res.push(p.val)
p = p.next
}
return res.reverse()
};
Solution 2:
var reversePrint = function(head) {
let p = head
let stack = []
while(p) {
stack.push(p.val)
p = p.next
}
let res = []
while(stack.length) {
res.push(stack.pop())
}
return res
};
5. Rebuild binary tree (!!! Offer-07)
Solution: the key point is how to write the parameters when recursively constructing the left and right subtrees.
-
Idea:
- Find out the value of the root node, and then recursively construct the left and right subtrees
- The first number of preorder traversal is the root node, and the last number of postorder traversal is the root node
- In the middle order traversal, the number on the left side of the root node is the left subtree, and the number on the right side of the root node is the right subtree, and then recursion
-
Steps:
- The root node obtained by preorder is located in inorder. The left side is the left subtree and the right side is the right subtree
- The index obtained in inorder can help us divide the preorder array
- So we can recursively get the leaf node by dividing the array,
- Then they are assembled through step-by-step backtracking, which is a complete tree
var buildTree = function(preorder, inorder) { if(preorder.length === 0) {return null} let root = new TreeNode(preorder[0]) let index = inorder.indexOf(preorder[0]) root.left = buildTree(preorder.slice(1, index + 1), inorder.slice(0, index)) root.right = buildTree(preorder.slice(index + 1), inorder.slice(index + 1)) return root };
6. Implement queue with two stacks (!! Offer-09)
The title requires two stacks, so you can't simply use the shift() method.
Solution:
1. Define two stacks A and B, which are queue in stack and queue out stack respectively (stack: first in first out; queue: first in first out)
2. The appendtail operation is put into the queue stack
3.deleteHead will be taken from the out of queue stack (provided that all items in the queue stack are cleared and put into the out of queue stack). If not, it will return - 1
var CQueue = function() {
this.stackA = []
this.stackB = []
};
/**
* @param {number} value
* @return {void}
*/
CQueue.prototype.appendTail = function(value) {
this.stackA.push(value)
};
/**
* @return {number}
*/
CQueue.prototype.deleteHead = function() {
if(this.stackB.length) {
return this.stackB.pop()
}else {
while(this.stackA.length) {
this.stackB.push(this.stackA.pop())
}
if(!this.stackB.length) {
return -1
}else{
return this.stackB.pop()
}
}
};
7. Fibonacci sequence (Offer-10)
Note that there are modules in this problem.
//Solution 1:
var fib = function(n) {
const dp = [0, 1]
for(let i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2]
if(dp[i] > (1e9+7)) {
dp[i] = dp[i] % (1e9+7)
}
}
return dp[n]
};
//Solution 2:
var fib = function(n) {
if(n === 0 || n === 1) {
return n
}
let dp0 = 0, dp1 = 1, mod = 1e9 + 7
for(let i = 2; i <= n; i++) {
const temp = dp1
dp1 += dp0
dp0 = temp
if(dp1 > mod) {
dp1 = dp1 % mod
}
}
return dp1
};
8. Frog jumping steps (Offer-10)
The idea of this question is the same as that of the previous question, which is the application of basic dynamic planning.
var numWays = function(n) {
if(n < 2) {
return 1
}
let dp0 = 1, dp1 = 1, mod = 1e9+7
for(let i = 2; i <= n; i++) {
const temp = dp1
dp1 += dp0
dp0 = temp
if(dp1 > mod) {
dp1 = dp1 % mod
}
}
return dp1
};
9. Minimum number of rotation array (Offer-11)
var minArray = function(numbers) {
let low = 0, high = numbers.length - 1
while(low < high) {
const mid = low + Math.floor((high - low) / 2)
if(numbers[mid] < numbers[high]) {
high = mid
}else if(numbers[mid] > numbers[high]) {
low = mid + 1
}else {
high--
}
}
return numbers[low]
};