JS brush the way – recursive backtracking (Part I)
Recursion and backtracking is not as good as the stack of questions brush, almost dove, see there is urging more, this I pa out of the recursion and backtracking JS; Recursion and backtracking is the foundation, with the foundation of the next good brush binary tree ~
Mind mapping
To obtain hd PDF, please reply to [LeetCode] on wechat public account [Little Lion front End]. You can add Q group [666151691] together.
Compared with the previous part, I added classification to recursion and backtracking in mind mapping, which obtained the permission of the original author. In this chapter, it is relatively simple, and then continue to add the next chapter, recursion and backtracking (below) advanced ~~
Let’s warm up with some hors d ‘oeuvres
1. Warm-up exercises
16.11. The diving board
Topic describes
- Title link:16.11. The diving board
You’re building a diving board out of a pile of planks. There are two types of boards, with shorter boards and longer boards. You have to use exactly k boards. Write a method that generates all possible lengths for a diving board.
The returned length needs to be sorted from smallest to largest.
Example 1
Input: shorter = 1 longer = 2 k = 3 Output: [3,4,5,6] Use shorter 2 times and longer 1 time, and get result 4. And so on, to get the final result.Copy the codeTip:
0 < shorter <= longer
0 <= k <= 100000
Copy the codeTheir thinking
There are always k+1 results, and the result is shorter = 1 longer = 2 k = 3
k=3Res [I] = result calculation1 1 1 0 1*3 + 2*0 3
1 1 2 1 1*2 + 2*1 4
1 2 2 2 1*1 + 2*2 5
2 2 2 4 1*0 + 2*3 6
Copy the codeIt’s pretty simple: just notice this special case: 1, 1, 100000
The code is as follows (example) :
/ * * *@param {number} shorter
* @param {number} longer
* @param {number} k
* @return {number[]}* /
var divingBoard = function (shorter, longer, k) {
/** * k=3 res * 1 1 1 0 1*3 + 2*0 3 * 1 1 2 1 1*2 + 2*1 4 * 1 2 2 2 1*1 + 2*2 5 * 2 2 2 4 1*0 + 2*3 6 */
let res = [];
if (shorter === longer && k) {
res[0] = k * shorter;
} else if (k) {
for (let i = 0; i <= k; i++) { res[i] = shorter * (k - i) + longer * i; }}return res;
};
Copy the code1291. The number
Topic describes
- Title link:1291. The number
We define the order as an integer in which the digit in each digit is 1 greater than the digit in the preceding digit.
Return an ordered list of all sequential degrees in the range [low, high] (in descending order).
Example 1:
Output: low = 100, high = 300Copy the codeExample 2:
Output: low = 1000, high = 13000 output: [45] 1234234 5345 6456 7567 8678 9123Copy the codeTip:
10 <= low <= high <= 10^9
Copy the codeTheir thinking
Note: The result is the following code to sort (example) :
/ * * *@param {number} low
* @param {number} high
* @return {number[]}* /
var sequentialDigits = function (low, high) {
// return low.toString().split('');
/** * 10 <= low <= high <= 10^9 */
let res = [],
index = 0;
for (let i = 1; i <= 9; i++) {
let n = i;
for (let j = i + 1; j <= 9; j++) {
n = n * 10 + j;
if(n >= low && n <= high) { res[index++] = n; }}}return res.sort(function(a,b){returna-b; }); };Copy the codeMethod 2: from Chocolate: The above method does not traverse too much, but it is still too time-consuming, and there is no need to traverse a lot of branches, can be pruned
Find the length of the string corresponding to the minimum and maximum, that is, find the range of numbers we can enumerate.
And then our minimum starting point is 1, and our maximum starting point is 10-len.
Why 10-len? For example, if example 1 gives a value in the range [100,300], then the enumerable length len is 3 and the maximum starting point is in place 10-3 = 7. So the order is 789, but it’s not in our interval. Then the numbers starting with 8 and 9 do not need to be enumerated. That way, we can cut out a section of data.
The code is as follows (example) :
/ * * *@param {number} low
* @param {number} high
* @return {number[]}* /
var sequentialDigits = function(low, high) {
let res = []
let lowLen = low.toString().length
let highLen = high.toString().length
for(leti=lowLen; i<=highLen; i++){for(let j=1; j<=10-i; j++){let str = ' '
let num = j
str += num
let k = i-1
while(k--){
num++
str += num
}
let ans = parseInt(str)
if(ans>=low && ans<=high){
res.push(ans)
}
}
}
return res
};
Copy the codeSecond, the matrix
59. Spiral matrix II
Topic describes
- Title link:59. Spiral matrix II
Given a positive integer n, generate a square matrix containing all elements from 1 to n2 in a clockwise spiral order.
Example:
Input: 3 output: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]Copy the codeTheir thinking
Key to solve the problem: the boundary idea first defines four boundaries: upper, lower, left and right
You go from the left boundary to the right boundary (123) and you move the top boundary down (up++)
And then we go down from the top (45).
And then we go from the right to the left and we move down the bottom boundary.
And then I’m going to go from the bottom up (8) (no 7, no 1 because the upper and lower bounds) and the left bounds move to the right (left++)
Finally, the loop condition is broken out: the value is less than or equal to n*n
The code is as follows (example) :
/ * * *@param {number} n
* @return {number[][]}* /
var generateMatrix = function (n) {
/ * * * * 0 1 (0, 0) 2 (0, 1) 3 (0, 2) * 1 8 (1, 0), 9 (1, 1) 4 (1, 2) * 2, 7 6 (2, 1) (2, 0) 5 (2, 2) * * /
let res = [];
let up = 0,
down = n - 1,
left = 0,
right = n - 1;
for (let i = 0; i < n; i++) {
res[i] = [];
}
let cur = 1;
while (cur <= n * n) {
for (let i = left; i <= right; i++) { // Add a row of data from left to right -> change the upper boundary
res[up][i] = cur++;
}
up++;
for (let i = up; i <= down; i++) { // From top to bottom -> change the right border
res[i][right] = cur++;
}
right--;
for (let i = right; i >= left; i--) { // From right to left -> change the bottom boundary
res[down][i] = cur++;
}
down--;
for (let i = down; i >= up; i--) { // From top to bottom -> change the left border
res[i][left] = cur++;
}
left++;
}
return res;
};
Copy the code54. Spiral matrix
Topic describes
- Title link:54. Spiral matrix
Given a matrix containing m x n elements (m rows, n columns), return all elements in the matrix in a clockwise spiral order.
Example 1:
Input: [[1, 2, 3], [4, 5, 6], [7, 8, 9]] output:,2,3,6,9,8,7,4,5 [1]Copy the codeExample 2:
Input: [[1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12]] output:,2,3,4,8,12,11,10,9,5,6,7 [1]Copy the codeTheir thinking
This problem is easy after you understand the last one
Iterate as above, storing values in res.
Note that m and n are not equal and may cause it to go too far. Let’s see why, using example 2:
It’s ok to go to 7 (up is 1, right is 2, down is 1, and left is 1), and then you can go to 6, and you can imagine the boundary goes, 7 hits the wall left, 7 hits the wall down and you go right up to 6, you hit the wall up, and then you break out of the loop
There are many solutions to this problem (write two here) :
- Violence —- I directly remove the more at the end
- If (res.length === n*m) break can be added at every position, or it can be found at key positions, because the last item is one more row or column, so it is added after the second paragraph
The code is as follows (example) :
/ * * *@param {number[][]} matrix
* @return {number[]}* /
var spiralOrder = function (matrix) {
let res = [],
index = 0;
let n = matrix.length,
m = matrix[0].length;
let up = 0,
down = n - 1,
left = 0,
right = m - 1;
while (index < n * m) {
for (let i = left; i <= right; i++) {
res[index++] = matrix[up][i];
}
up++;
for (let i = up; i <= down; i++) {
res[index++] = matrix[i][right];
}
right--;
// if(res.length === n*m) break
for (let i = right; i >= left; i--) {
res[index++] = matrix[down][i];
}
down--;
for (let i = down; i >= up; i--) {
res[index++] = matrix[i][left];
}
left++;
}
// console.log("res:"+res);
return res.splice(0, n * m);
};
/ / the console. The log (" return: "+ spiralOrder ([[1, 2, 3, 4], [5,6,7,8], [9,10,11,12]]));
Copy the code73. Set the matrix to zero
Topic describes
- Title link:54. Spiral matrix
Given an m x n matrix, if one element is 0, set all elements in its row and column to 0. Please use the in place algorithm.
Example 1:
,1,1 input: [[1], [1, 1], [1,1,1]] output: [[1, 1], [0, 0], [1, 1]]Copy the codeExample 2:
,1,2,0 input: [[0], [3,4,5,2], [1,3,1,5]] output: [,0,0,0 [0], [0,4,5,0], [0,3,1,0]]Copy the codeAdvanced:
An immediate solution is to use O(MN) extra space, but this is not a good solution. A simple improvement would be to use O(m + N) extra space, but this is still not the best solution. Can you think of a solution for constant space?Copy the codeTheir thinking
Key to the solution: I want you to use the in place algorithm to solve the problem using constant space
Using constant space means you can’t use extra space
Let’s take a look at the code that uses extra space and find the rows and columns of 0 and set them to zero. This is not a good idea, because it means you have to use an extra space to store 0, no matter what data structure you use.
The code is as follows (example) :
/ * * *@param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function (matrix) {
let n = matrix.length;
let m = matrix[0].length;
var across = new Set(a);var vertical = new Set(a);// Iterate over each line
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (matrix[i][j] === 0) { / / find 0across.add(i); vertical.add(j); }}}for (let k of across) {
for (let j = 0; j < m; j++) {
matrix[k][j] = 0; }}for (let k of vertical) {
// set the vertical axis to zero
for (let j = 0; j < n; j++) {
matrix[j][k] = 0; }}return matrix;
};
Copy the codeIn situ algorithm that meets the requirements of the topic:
Note: Object.is does not cast NaN, -0, nor does it treat +0 specially (to have the same behavior as the special values ===)
The code is as follows (example) :
/ * * *@param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function (matrix) {
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[0].length; j++) {
if (Object.is(matrix[i][j], 0)) {
// Perform operations on rows
for (let k = 0; k < matrix.length; k++)
if (!Object.is(matrix[k][j], 0) && k ! == i) matrix[k][j] = -0
// Perform operations on columns
for (let k = 0; k < matrix[0].length; k++)
if (!Object.is(matrix[i][k], 0) && k ! == j) matrix[i][k] = -0}}}return matrix
};
Copy the codeThree,
784. Letters are arranged in all case
Topic describes
- Title link:784. Letters are arranged in all case
Given a string S, we get a new string by caseshifting each letter in string S. Returns a collection of all possible strings.
Example:
Input: S = "a1b2" output: [" a1b2 ", "a1b2", "a1b2", "a1b2"] input: S = "3 z4" output: [" 3 z4 ", "3 z4"] input: S = "12345" output: [" 12345 "]Copy the codeTip:
The length of S is not more than 12. S consists of only numbers and letters.Copy the codeTheir thinking
A picture is worth a thousand words.
The code is as follows (example) :
/ * * *@param {string} S
* @return {string[]}* /
var letterCasePermutation = function (S) {
let res = [];
let dfs = (t, str) = > { //t is the string before the letter, and STR is the string after
if (str === ' ') return res.push(t); // The end condition is traversal to the last character, the last character of STR is ""
let ch = str[0]; // Save the current value
let nextStr = str.substr(1); // Pass a value representing the string to the right of the current value
if (isNaN(ch)) {
// Divide letters into two branches, uppercase and lowercase
dfs(t + ch.toLowerCase(), nextStr); / / lowercase
dfs(t + ch.toUpperCase(), nextStr); / / the capital
} else {// Add the numbers together
dfs(t + ch, nextStr)
}
}
dfs(' ', S); // start with t= "STR =S"
return res;
};
Copy the code46. The whole arrangement
Topic describes
- Title link:46. The whole arrangement
Given a sequence without repeating digits, return all possible permutations.
Example:
Input: [1, 2, 3] output: [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]Copy the codeTheir thinking
The classical permutation problem, first introduced the classical solution, here is the full permutation state tree of another problem, change the same:
1~ nBetween thenNumber of natural numbers, for I =1 to n, each timeA [1] swaps with a[I]Later, thea[2]~a[n]In then-1I’m going to arrange all the elements, and thenSwap a[1] with a[I]The value of make itrestoreTo the state before this permutation • fora[3]~a[n]Within the rangen-2Permutation of the elements, and then swap the elementsback; • And so on, until the full permutation of A [n], the value of the entire array is printed, that is, a permutation result.
You can read it if you don’t understand itLeetCode official solutionI’ve got the key picture here:
The code is as follows (example) :
/ * * *@param {number[]} nums
* @return {number[][]}* /
var permute = function (nums) {
let swp = (str, i, j) = > {
let t = str[i];
str[i] = str[j];
str[j] = t;
} //swp
let res = [];
let dfs = (str, cur) = > {
if (cur === str.length - 1) {
return res.push(str.slice());
}
for (let i = cur; i < str.length; i++) {
swp(str, cur, i);
dfs(str, cur + 1);
swp(str, cur, i);
}
}
dfs(nums, 0);
return res;
};
Copy the codeSolution 2: From LeetCode author Liweiwei1419
- Write the full permutations starting with 1. They are: [1, 2, 3], [1, 3, 2], i.e., the full permutations of 1 + [2, 3] (note: the recursive structure is shown here).
- [2, 1, 3], [2, 3, 1], that is, 2 + [1, 3];
- Finally, write all permutations beginning with 3. They are: [3, 1, 2], [3, 2, 1], i.e., all permutations of 3 + [1, 2].
- Notice You need to save the status. The selected number cannot appear in the current number.
Illustration:
/ * * *@param {number[]} nums
* @return {number[][]}* /
var permute = function (nums) {
let res = [];
let vis = {};
let dfs = (t) = > {
if (t.length == nums.length) {
res.push(t);
}
for (let i = 0; i < nums.length; i++) {
if (vis[i]) continue;
vis[i] = true;
t.push(nums[i]);
dfs(t.slice());
t.pop();
vis[i] = false;
}
}
dfs([]);
return res;
};
Copy the code47. Full permutation II
Topic describes
- Title link:47. Full permutation II
Given a sequence nums that can contain repeating digits, return all non-repeating full permutations in any order.
Example 1:
Input: nums = [1,1,2] output: [[1,1,2], [2,1]]Copy the codeExample 2:
Output: input: nums = [1, 2, 3], [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]Copy the codeTip:
1 <= nums.length <= 8
-10 <= nums[i] <= 10
Copy the codeTheir thinking
A picture is worth a thousand words:
The code is as follows (example) :
/ * * *@param {number[]} nums
* @return {number[][]}* /
var permuteUnique = function (nums) {
nums.sort((a, b) = > {
return a - b
});
let res = [];
let visited = [];
let dfs = (t) = > {
if (t.length === nums.length) return res.push(t);
for (let i = 0; i < nums.length; i++) {
if (visited[i]) continue; / / visit
if(! visited[i -1] && i > 0 && nums[i] === nums[i - 1]) continue; // The previous value is not accessed and the previous value is equal to the current value
t.push(nums[i]);
visited[i] = true;
dfs(t.slice());
t.pop();
visited[i] = false;
}
}
dfs([]);
return res;
};
console.log(permuteUnique([1.2.1]));
Copy the codeFour, subset
78. The subset
Topic describes
- Title link:78. The subset
Given an array of integers with no repeating elements, nums returns all possible subsets (power sets) of the array.
Note: The solution set cannot contain duplicate subsets.
Example:
Output: input: nums = [1, 2, 3], [[3], [1], [2], [1, 2, 3], [1, 3], [2, 3], [1, 2], []]Copy the codeTheir thinking
The subset tree is shown in the figure:
This problem can be cleverly used to construct a deeper recursion tree, which is what we want to see
The code is as follows (example) :
/ * * *@param {number[]} nums
* @return {number[][]}* /
var subsets = function (nums) {
let res = [];
let t=[];
let dfs = (cur) = > { // Current number of layers
if (cur === nums.length){
// console.log(t);
return res.push(t.slice()); // The current level is equal to the array length
}
t.push(nums[cur]); // Select the current number of layers
dfs(cur + 1);
t.pop(); // Do not select the current number of layers
dfs(cur + 1);
}
dfs(0);
return res;
};
console.log(subsets([1.2.3]))
Copy the codeThe code is as follows (example) :
var subsets = function (nums) {
let res = [];
let dfs = (t, start) = > {
res.push(t);
for (let i = start; i < nums.length; i++) {
t.push(nums[i]);
dfs(t.slice(), i + 1);
t.pop();
}
}
dfs([], 0);
return res;
};
console.log(subsets([1.2.3]))
Copy the code90. The subset II
Topic describes
- Title link:90. The subset II
Given an integer array nums that may contain repeating elements, return all possible subsets (power sets) of that array.
Note: The solution set cannot contain duplicate subsets.
Example:
,2,2 input: [1] output: [[2], [1],,2,2 [1], [2], [1, 2], []]Copy the codeTheir thinking
The last problem can be backtracked in a clever way, but not this one. The solution and thinking of this problem can solve the previous problem. Without further ado, let’s analyze the title:
Different from the previous problem, it is obvious that pruning needs to be done, but I don’t know how to do it after reading the problem. So let’s draw a subset tree.
Key:
- Use I to refer to the current element, determine whether the current element is equal to the previous element, and determine
num[i - 1]===num[i] - Prune cannot prune different layers as shown in figure [1,2,2]
i=startIs repeated for different layers (start corresponds to what layer), should be pruned [1,2]I = 2, start = 1Different layers
The code is as follows (example) :
var subsetsWithDup = function (nums) {
let res = [];
nums.sort((a, b) = > a - b);
let dfs = (t, start) = > {
res.push(t);
for (let i = start; i < nums.length; i++) {
// Repeat the same layer, skip
if(i ! = start && nums[i -1] == nums[i]) continue;
t.push(nums[i]);
dfs(t.slice(), i + 1);
t.pop();
}
}
dfs([], 0);
return res;
};
/ / the console. The log (subsetsWithDup (,4,4,1,4 [4]))
Copy the codeconclusion
Everyone’s way of solving the problem is not quite the same, but the idea of solving the problem can be borrowed from each other, this article or draw a lot of pictures, there is not so much text, should be relatively easy to understand, finally, I hope this article is useful for you ~
If you still have questions about something, LeetCode has a pretty good answer for itCopy the codeI will keep you updated in the next post: Recursion and backtracking (part 2)
Point a praise to go ~ please ❀ ❀ ❀ better three even if it is a key ~, your support is my motivation to continue writing ⭐ ️