JS刷题之路-递归回溯（上篇）

递归与回溯的题就不像栈的题那么好刷了，差点就鸽了，看到有催更，这不我啪的一下赶出了递归与回溯的JS上篇；递归与回溯是基础，有了基础才好在下一篇刷二叉树~

思维导图

获取高清PDF，请在微信公众号【小狮子前端】回复【LeetCode】，一起刷题或者交流学习可以加Q群【666151691】

思维导图相较于上篇我在递归与回溯上加了分类，获得原作者的许可了；在这一篇呢讲的相对于简单一些，后续持续加更下一篇，递归与回溯（下）进阶~~

先搞几道开胃小菜，热热身

一、热身题

16.11.跳水板

题目描述

你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。

返回的长度需要从小到大排列。

示例 1

输入：
shorter = 1
longer = 2
k = 3
输出： [3,4,5,6]
解释：
可以使用 3 次 shorter，得到结果 3；使用 2 次 shorter 和 1 次 longer，得到结果 4 。以此类推，得到最终结果。

提示：

0 < shorter <= longer
0 <= k <= 100000

解题思路

总有k+1个结果，结果就是短板长度*k-i+长版长度i
以题目示例shorter = 1 longer= 2 k = 3

  
k=3   res[i]  =  结果计算
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

挺简单的：只需要注意这个特殊情况：
1
1
100000

代码如下（示例）：

/**
 * @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;
};

1291.顺次数

题目描述

我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。

请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表（从小到大排序）。

示例 1：

输出：low = 100, high = 300
输出：[123,234]

示例 2：

输出：low = 1000, high = 13000
输出：[1234,2345,3456,4567,5678,6789,12345]

提示：

10 <= low <= high <= 10^9

解题思路

方法一：穷举
注意：出来的结果是要排序的
代码如下（示例）：

/**
 * @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){return a-b;});
};

方法二：
来自Chocolate：上面的方法虽然说也没有遍历太多数但是还是太耗时了，并且有很多没有必要遍历，可以剪枝

先求出最小值和最大值对应字符串的长度，即求出我们能枚举的数字的长度范围。

然后我们的起点的最小值从 1 开始，起点的最大值从 10-len 开始。

为什么是 10-len？举例说明，示例1给的是 [100,300]范围的值，那么可枚举的长度 len 为 3，起点的最大值就位 10 - 3 = 7。那么此时顺次数为 789 但是不在我们区间范围内，舍弃。然后8、9开头的数字就不需要枚举了。 这样，我们就能剪掉一部门数据了。

代码如下（示例）：

/**
 * @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(let i=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    
};

二、矩阵

59. 螺旋矩阵 II

题目描述

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3
输出:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

解题思路

解题关键：边界思想
首先定义上下左右四个边界

从左边界往右边界走（123）上边界下移（up++）

然后从上往下走（45）（此时没有3是因为up加后变成1了）右边界左移（right- -）

然后从右往左走（67）（没5因为right- -了）下边界上移（down- -）

然后从下往上走（8）（没7没1因为上下边界）左边界右移（left++）

最后跳出循环条件：值小于等于n*n

代码如下（示例）：

/**
 * @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(2,0) 6(2,1) 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++) { //左到右 最上添加一行数据->  上边界改变
            res[up][i] = cur++;
        }
        up++;
        for (let i = up; i <= down; i++) { //从上到下 -> 改变右边界
            res[i][right] = cur++;
        }
        right--;
        for (let i = right; i >= left; i--) { //从右到左 -> 改变下边界
            res[down][i] = cur++;
        }
        down--;
        for (let i = down; i >= up; i--) { //从上到下 -> 改变左边界
            res[i][left] = cur++;
        }
        left++;
    }
    return res;
};

54. 螺旋矩阵

题目描述

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

解题思路

看懂上一题之后，这道题就很简单了

按上题的方法遍历，用res储存值。

注意的是：m与n不相等可能造成它会多走，分析一下为什么，以示例2为例：

走到7是可以的（此时up为1，right为2，down为1，而left为1），接着还会走到6，可以想象一下边界走向，7往左碰壁，往下碰壁往右遍历到6，往上碰壁，然后跳出循环

为了解决这个问题可以有很多解决方法（这里写两个）：

  1. 暴力—-我直接把多的在最终时去除
  2. 在循环里加if条件语句：if(res.length === n*m) break 可以在每个位置都加，也可以找到关键位置加，由于最后一项都是多的一行或者一列，所以加在第二段之后

代码如下（示例）：

/**
 * @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);
};
// console.log("return:"+spiralOrder([[1,2,3,4],[5,6,7,8],[9,10,11,12]]));

73. 矩阵置零

题目描述

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:

输入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

进阶:

一个直接的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？

解题思路

解题关键：希望你使用原地算法使用常数空间解决问题

用常数空间解决意味着不能使用额外空间

首先看一下使用额外空间的代码
首先找到0的行列，再将其行列置零。这并不是一个好方法，因为这意味着你必须用一个额外的空间去存0，不管是用什么数据结构。

代码如下（示例）：

/**
 * @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();
    var vertical = new Set();
    // 遍历每一行
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (matrix[i][j] === 0) { //找到0
                across.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) {
        //竖轴置零
        for (let j = 0; j < n; j++) {
            matrix[j][k] = 0;
        }
    }
    return matrix;
};

符合题目要求的原地算法：

友情提示：Object.is不会对NaN，-0和进行类型转换，也不会进行特殊处理+0（使其具有与===那些特殊数值相同的行为）

代码如下（示例）：

/**
 * @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)) {
                // 对行进行操作
                for (let k = 0; k < matrix.length; k++)
                    if (!Object.is(matrix[k][j], 0) && k !== i) matrix[k][j] = -0
                // 对列进行操作
                for (let k = 0; k < matrix[0].length; k++)
                    if (!Object.is(matrix[i][k], 0) && k !== j) matrix[i][k] = -0
            }
        }
    }
    return matrix
};

三、排列

784.字母大小写全排列

题目描述

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例：

输入：S = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]

输入：S = "3z4"
输出：["3z4", "3Z4"]

输入：S = "12345"
输出：["12345"]

提示：

S 的长度不超过12。
S 仅由数字和字母组成。

解题思路

一图胜千言，以a1b2为例图解：

代码如下（示例）：

/**
 * @param {string} S
 * @return {string[]}
 */
var letterCasePermutation = function (S) {
    let res = [];
    let dfs = (t, str) => { //t是字母之前字符串，str是之后的
        if (str === '') return res.push(t); //结束条件为遍历到最后一个字符，最后一个字符的str为''
        let ch = str[0]; //保存一下当前值
        let nextStr = str.substr(1); //传一个值，表示当前值的右边字符串
        if (isNaN(ch)) {
            //为字母   分为两个分支  大写  小写
            dfs(t + ch.toLowerCase(), nextStr); //小写
            dfs(t + ch.toUpperCase(), nextStr); //大写
        } else {//为数字  拼接一下就好了
            dfs(t + ch, nextStr)
        }
    }
    dfs('', S); //刚开始 t='' str=S
    return res;
};

46. 全排列

题目描述

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解题思路

经典的全排列问题，首先介绍经典解法，这里是另外一道题的全排列状态树，换汤不换药：

递归分析：
• 用一个数组a[n]来保存1~ n之间的n个自然数，对于i=1~ n，每次用a[1]与a[i]交换后，对a[2]~a[n]中的n-1个元素进行全排列，然后再交换a[1]与a[i]的值，使它恢复到此次排列前的状态
• 对于a[3]~a[n]区间内的n-2个元素进行全排列，然后再把交换的元素交换回来；
• 依次类推，直到对a[n]进行全排列时，输出整个数组的值，即得到一种排列结果。

还不懂的话可以看LeetCode官方题解，不想跳过去看的我把关键的图拿过来了：

代码如下（示例）：

/**
 * @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;
};

解法二：
来自LeetCode作者liweiwei1419

  • 先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列（注意：递归结构体现在这里）；
  • 再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列；
  • 最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。
  • 注意需要保存状态，已经选择的数字在 当前 要选择的数字中不能出现。

图解：

/**
 * @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;
};

47. 全排列 II

题目描述

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

解题思路

一图胜千言：

代码如下（示例）：

/**
 * @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; //访问过
            if (!visited[i - 1] && i > 0 && nums[i] === nums[i - 1]) continue; //上一个没访问，且上一个值等于当前值
            t.push(nums[i]);
            visited[i] = true;
            dfs(t.slice());
            t.pop();
            visited[i] = false;
        }
    }
    dfs([]);
    return res;
};
console.log(permuteUnique([1, 2, 1]));

四、子集

78. 子集

题目描述

  • 题目链接：78. 子集
    给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解题思路

子集树如图所示：

这道题可以巧妙的运用选与不选构造一个更深的递归树，这是我们想要看到的

代码如下（示例）：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
    let res = [];
    let t=[];
    let dfs = (cur) => { //当前层数
        if (cur === nums.length){
            // console.log(t);
            return res.push(t.slice()); //当前层数等于数组长度
        } 
        t.push(nums[cur]); //选当前层数的数字
        dfs(cur + 1);
        t.pop(); //不选当前层数的数字
        dfs(cur + 1);
    }
    dfs(0);
    return res;
};
console.log(subsets([1, 2, 3]))

代码如下（示例）：

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]))

90. 子集 II

题目描述

  • 题目链接：90. 子集 II
    给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

解题思路

上一道题可以用讨巧的方法来回溯，但是这道题就不可以了。而这道题的解决方法与思路是可以解决上一道题的。话不多说，来分析题目：

不同于上题，很明显需要剪枝，但是刚看完题目不知道怎么剪，那么我们先画一个子集树，理清思路：


代码思路：
注意：巧妙使用sort，可以使相等元素相邻

关键：

  1. 使用i指向当前元素，判断当前元素与前一元素是否相等，及判断num[i - 1]===num[i]
  2. 剪枝不能将不同层的剪枝，如图中的[1,2,2] i=start是不同层重复(start相当于第几层），应该剪枝[1,2]i=2,start=1·不同层

代码如下（示例）：

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++) {
            // 同层重复，跳过
            if (i != start && nums[i - 1] == nums[i]) continue;
            t.push(nums[i]);
            dfs(t.slice(), i + 1);
            t.pop();
        }
    }
    dfs([], 0);
    return res;
};
// console.log(subsetsWithDup([4,4,4,1,4]))

总结

每个人的解题方式都是不太一样的， 但是解题思路是可以相互借鉴的，这篇文章还是画了不少图的，也没有那么多文字，应该还是比较好理解的，最后希望这篇文章对你有用~

如果对某题还有疑问LeetCode上基本也有不错的解答哦

后续文章会持续更新，下一篇：递归与回溯（下），和我一起刷题吧~

点个赞再走吧 ~ 求求了 ❀❀❀ 能一键三连的话那就更好啦~，你的支持是我继续写作的动力⭐️