写点什么

前端 leetcde 算法面试套路之回溯

作者:js2030code
  • 2022-11-02
    浙江
  • 本文字数:8063 字

    阅读完需:约 26 分钟

前言

回溯,就是无脑冲,碰壁之后就回撤一步继续搞,属于一种暴力解题的思路;


实际上也是如此,当我们在遇到一些分类讨论的问题,无法想到比较精妙的解决方案,我们第一时间考虑到的就是暴力枚举所有情况,然后再做处理,而 回溯 就是这样的一个暴力法


下一个 tab 学习一下常规的排序算法

正文

在做回溯题 的过程中,会发现很迷茫,因为很多题好像不需要返回,在执行下一步的过程中,我就做好判定,然后将可能的失败遏制住了,这个时候,一般能继续往下走的,都属于还行的操作,我们其实可以把这种方式叫做 剪枝


我一度陷入深思,是不是回溯就没用了呢,是不是只要脑瓜还行,其实剪枝就好了,还回溯啥,直到想起回溯的核心思想,它其实是一种暴力解法, 也就是如果你能用其他方法,其实不用回溯,是比较好的思路,一般情况下,回溯的复杂度会比较高


那么到底什么时候用回溯呢?那种你没法子预设结局,或者说你的选择不单单关联相邻层的选择,而是会对更深层都有影响,比方说 51. N 皇后


我们需要求的是完整的棋盘,每一层的选择,都会影响整个棋盘的的布局,这个时候想在下棋那一刻就将全部可能情况想出来,太难了,这时候用回溯 就是很好的选择


而对于一些只与上层有影响,这个时候剪枝 也不失是一个好的选择;


其实在做系列总结的时候,会尽可能用系列的方法去解答,但是一题多解也是我们追求的,而且我们最后想要实现的,肯定是不局限与某写法,而是只要看到了,就能 a 出来;


所以努力将大部分常规的 tab 复习一遍,然后再慢慢填补,总结属于自己的解题方案,才是做总结的目的吧;


与大家一起努力呀

题目汇总

46. 全排列

分析


  1. 不含重复数字,要求的是全排列,所以不同顺序的排列都得算上,这样在枚举过程中要知道自己曾经获取过哪些值

  2. 在枚举过程中缓存两个数组 arr,getIndex, arr 是枚举过程中的数组, getIndex 是走过值状态,如果当前 arr 走过对应的下标的值为 1,没有走过就是 0

  3. 在每一层给临时数组 arr 添加值的时候,需要保证不会重复添加,可以在每一次遇到的时候再遍历 arr,由于值是唯一的,也是可以的;

  4. 在这里是用空间换时间,用 getIndex 数组缓存对应的状态,每一次查找的复杂度是 O(1)

  5. 每一次需要枚举完整的数组,需要枚举 n 次所以时间复杂度为 O(n2),空间复杂度 O(n)


参考视频:传送门


var permute = function (nums) {  let ret = [];
const dfs = (arr, getIndex) => { if (arr.length === nums.length) { ret.push(arr); return; } for (let i = 0; i < nums.length; i++) { const num = nums[i]; if (!!getIndex[i]) continue; // 如果存在,则代表已经有这个值了 getIndex[i] = 1; dfs([...arr, num], getIndex); getIndex[i] = 0; } }; const getIndexArr = new Array(nums.length) dfs([], getIndexArr); return ret;};

复制代码

47. 全排列 II

分析


  1. 由于这个时候包含了重复的数字了,且不能有重复值,所以可以考虑到先排序

  2. 整理思路和题 1 一直,都是缓存两个数组,而且由于值有重复,所以不能用值是否相同来判断,只能用下标判断了

  3. 区别在于,每一次回溯回来,需要判断下一次的值是否和当前回溯值一样,如果一样就需要跳过,防止出现重复排列

  4. 时间复杂度 O(n2),空间复杂度 O(n)


var permuteUnique = function(nums) {    const ret = []    const len = nums.length    nums.sort((a,b)=>a-b) // 排序    const dfs = (arr,indexArr) => {        if(arr.length === len ){            ret.push(arr)            return         }        for(let i = 0;i<len;i++){            if(!!indexArr[i]) continue            const num = nums[i]            indexArr[i] = 1            dfs([...arr,num],indexArr)            indexArr[i] = 0            // 回溯回来,如果下一个值一样,那么就是要重复走之前的老路了,所以还是直接跳过的好            while(nums[i+1]=== nums[i]) {                i++            }        }    }    dfs([],[])    return ret}
console.log(permuteUnique([1,1,2]))
复制代码

39. 组合总和

分析


  1. candidates 是无重复,正整数数组

  2. 可以重复取值,但是由于和排列无关,不能倒退取,所以需要维护一个初始的下标值;与 [组合总和 IV] 形成对比


 var combinationSum = function(candidates, target) {    const ret = []
const dfs = (start,arr,sum) => { if(sum === target){ ret.push(arr) return } if(sum>target) return
for(let i = start;i<candidates.length;i++){ // 因为允许重复取,所以每一次都是从 start 这个节点开始取的 dfs(i,[...arr,candidates[i]],sum+candidates[i]) } }
dfs(0,[],0) return ret}
复制代码

40. 组合总和 II

分析


  1. candidates 是有无重复,正整数数组

  2. 数组中的每一个值只能取一次;不可以重复取值,但是对于重复的值是可以取的,即 [1,1,2,3] -> 可以取 [1,1,2],[1,3] -> 4

  3. 为了不取到重复的值,就得跳过相同值,这个时候需要对数组排序

  4. 在每一层进行枚举的时候,循环中出现重复值的时候,剪掉这部分的枚举,因为肯定有相同的一部分

  5. 由于不可以重复取,所以 dfs 第一个入参的下标是要 +1 的,表示不可以重复取上一次哪一个值


 var combinationSum2 = function (candidates, target) {    candidates.sort((a,b)=>a-b)    const ret= []
const dfs = (start,arr,sum) => { if(sum === target) { ret.push(arr) return } if(sum>target || start>= candidates.length) return for(let i = start;i<candidates.length;i++){ // 将重复的剪掉 if(i > start && candidates[i] === candidates[i-1]) continue // 这里的 start 是启动枚举的下标,但是插入到临时数组的值是当前下标的值 dfs(i+1,[...arr,candidates[i]],sum+candidates[i]) } } dfs(0,[],0) return ret}
复制代码

216. 组合总和 III

分析


  1. 给定的不是具体的数组,而是长度限制 k, 和目标值 target -- 等同于 candidates 是无重复,1-9 的正整数数组

  2. 所以可以看做是 39. 组合总和 的特殊情况,只是判定条件有出入


var combinationSum3 = function (k, n) {  const ret = [];
const dfs = (start, arr, sum) => { if (arr.length === k && sum === n) { ret.push(arr); return; } if (arr.length > k || sum > n) { return; }
for (let i = start + 1; i < 10; i++) { dfs(i, [...arr, i], sum + i); } }; dfs(0, [], 0); return ret};
复制代码

377. 组合总和 Ⅳ

分析 -- 回溯


  1. candidates 是无重复,正整数数组,可以重复取值且要取排列不同的组合

  2. 这道题和组合总和很像,区别在于本题求的是排列的数量,而题 1 求的是不重复的组合

  3. 所以这里不需要限制组合起始枚举的下标了,每一次都从 0 开始即可

  4. 然后超时了*/


var combinationSum4 = function (nums, target) {  let ret = 0;  const dfs = (sum) => {    if (sum === target) {      ret++;      return;    }    if (sum > target) return;    for (let i = 0; i < nums.length; i++) {      dfs(sum + nums[i]);    }  };  dfs(0);  return ret;};
复制代码


分析 -- dp


  1. dp[i] 表示值为 i 的时候存在的组合数量

  2. 状态转移方程 dp[i] = sum(dp[i-nums[k]])

  3. base case dp[0] = 1


var combinationSum4 = function (nums, target) {    const dp = new Array(target+1)    dp[0]= 1  // 如果刚好得到的值是0,那么就有 1,因为不取也是一种取法    for(let i = 1;i<target+1;i++){        dp[i] = 0        for(let j =0;j<nums.length;j++){            if(i>=nums[j]){                dp[i]+=dp[i-nums[j]]            }        }    }    return dp[target]}
复制代码

78. 子集

分析 -- 找规律


  1. 数组元素不相同,返回值不包含重复的子集,也就是不考虑位置排列情况

  2. 由于跟排列无关,所以只需要遍历一遍 nums 即可,没遍历一次获取到的值,都可以和现有的 ret 组合成新的一批数组,然后和旧的 item 组合成新的枚举数组

  3. 时间复杂度 O(n2)


 var subsets = function (nums) {    let ret = [[]]    for(let num of nums ){        ret = [...ret,...ret.map(item => item.concat(num))]    }    return ret}
复制代码


分析 -- 迭代回溯


  1. 使用迭代的方法枚举所有的情况出来, 和多叉树遍历没啥区别

  2. 时间复杂度 O(N2)


var subsets = function (nums) {    const ret = []    const dfs = (start,arr) => {        ret.push(arr)        if(arr.length === nums.length || start=== arr.length) return         for(let i = start;i<nums.length;i++){            dfs(i+1,[...arr,nums[i]])        }    }    dfs(0,[])    return ret}
复制代码

90. 子集 II

分析 -- 有重复值


  1. 和 78. 子集相比,就是多了重复值,且不允许重复值出现在返回数组中,所以明显要先排序了

  2. 然后在回溯过程中,如果下一次迭代的值和当前值一样,则跳过,达到去重的效果


var subsetsWithDup = function (nums) {    nums.sort((a,b)=> a-b)    const ret = []    const dfs = (start,arr) => {        ret.push(arr)        if(start === nums.length ) return // start 超出下标,就是取到了最大下标值的时候了        for(let i = start;i<nums.length;i++){            dfs(i+1,[...arr,nums[i]])            while(nums[i] === nums[i+1]){                i++ // 去重            }        }    }    dfs(0,[])    return ret}
复制代码

131. 分割回文串

分析


  1. 这是一个变种的组合问题,因为排列顺序已经确定好了只要切割就好

  2. 所以在遍历过程中,只有当符合回文要求的子串,才能切割,然后往下走,否则剪掉较好

  3. 回文子串的判定可以简单的用左右双指针来实现


var partition = function(s) {    const ret = []    // 判断是否是回文子串    function isValid(s) {        if(s.length === 1) return true // 只有一个字符        let l = 0,r = s.length-1        while(l<r){            if(s[l] !== s[r]) return false            l++            r--        }        return true
} const dfs = (start,arr) => { if(start === s.length){ ret.push(arr) return } let temp ='' for(let i =start;i<s.length;i++){ temp+=s[i] if(isValid(temp)){ dfs(i+1,[...arr,temp]) } } } dfs(0,[]) return ret};
复制代码

93. 复原 IP 地址

分析


  1. 这道题和 131. 分割回文串 类似

  2. 这里也是切分字符串,只是判定条件变成了每一分段都要符合有效的 IP 地址,但是架子是一样的

  3. 这里的判定条件也多,只需要将合乎要求的条件算上,就能砍掉不少的分支


var restoreIpAddresses = function (s) {  const ret = [];
function isValid(s) { if (s.length > 1 && s[0] == 0) return false; // 不能以 0 起头 if (s >= 1 << 8) return false; // 要在 [0,255] 之间 return true; }
const dfs = (start, arr) => { if (arr.length === 4 && start !== s.length) return; // 已经分成4分,但是还没分完 if (start === s.length) { if (arr.length === 4) { ret.push(arr.join(".")); } // 无论是否分成四份,都离开了 return; }
let str = ""; for (let i = start; i < s.length && i < start + 3; i++) { str += s[i]; if (isValid(str)) { dfs(i + 1, [...arr, str]); } } }; dfs(0, []); return ret;};

复制代码

112. 路径总和

分析


  1. 路径是 root-leaf 完整路线上的和为 target

  2. dfs 中序遍历走下去即可

  3. 时间复杂度 O(n)


 var hasPathSum = function(root, targetSum) {    let ret = false    const dfs = (root,sum) => {        if(ret || !root) return  // 只要一条路走通了,其他都不用走了        sum += root.val        if(!root.left && !root.right && sum  === targetSum) {                ret = true                return         }        if(root.left) dfs(root.left,sum)        if(root.right) dfs(root.right,sum)    }    dfs(root,0)    return ret};
复制代码

113. 路径总和 II

分析


  1. 找的还是 root - leaf 的路径,但是这一次要把找的所有符合要求的路径都保存起来

  2. 时间复杂度 O(n)


 var pathSum = function(root, targetSum) {    const ret = []    const dfs = (root,arr,sum) => {        if(!root) return         sum+=root.val        arr = [...arr,root.val]        if(!root.left && !root.right && sum == targetSum){            ret.push(arr)        }        if(root.left) dfs(root.left,[...arr],sum)        if(root.right) dfs(root.right,[...arr],sum)    }    dfs(root,[],0)    return ret};
复制代码

437. 路径总和 III

分析


  1. 这次找的路径可以是树中任意 起始-结束 节点,;

  2. 但是路径必须是向下的,也就是不能是 a.left - a - a.right 的样子,这其实是减轻难度的限制条件

  3. 所以还是一样的自顶向下遍历就好,但是遇到满足需求的路径,还是要继续遍历到叶子节点位置

  4. 和 112. 路径总和 与 113. 路径总和 II 最大不同是,这一次的路径是不限制起始点和终点的;

  5. 不限制终点,那么我可以在遍历过程中,只要满足 targetSum, 就记录一次,一直到叶子节点位置,不需要到了叶子节点再判断

  6. 而不限制起始点是根节点,那么就是可以以任意节点为起始点,也就是需要遍历整一棵树作为起始点时候,往下去找路径了;

  7. 时间复杂度 O(nlogn)


var pathSum = function (root, targetSum) {  let ret = 0;  // 这是以任意 root 节点找路径和的 dfs  const dfs = (root, sum) => {    if (!root) return;    sum += root.val;    if (sum === targetSum) ret++;    if (!root.left && !root.right) return; // 叶子节点了,结束    if (root.left) dfs(root.left, sum);    if (root.right) dfs(root.right, sum);  };
// 这是遍历整棵树,然后继续往下走 const outer = (root) => { if (!root) return; dfs(root, 0); outer(root.left); outer(root.right); }; outer(root); return ret;};

复制代码

51. N 皇后

参考: leetcode-cn.com/problems/n-…


分析 -- 直接求符合要求的 chessboard


  1. 行就是树递归的深度,列就是每一层的宽度,使用回溯的办法进行树的 dfs 遍历

  2. 整个过程需要 3 大部分,回溯的方式遍历树,找出符合要求的节点 chessboard[row][col], 将符合要求的二维数组转换成符合要求的字符串数组

  3. 时间复杂度 O(n∗logn)


var solveNQueens = function (n) {  const ret = [];  // 1. N 皇后实际走的过程 -- 回溯树  const dfs = (row, chessboard) => {    if (row === n) {      // 已经到了叶子结点下 null 了 --      //   但是 chessboard 是一个二维数组,不能随便就push 进去的,需要深拷贝一下      ret.push(getStrChessboad(chessboard));      return;    }    // 每一行都是从 0 - n-1 , 然后不符合要求的就回溯回去    for (let col = 0; col < n; col++) {      if (isValid(row, col, chessboard)) {        // 如果 chessboard[row][col] 符合要求,则算一条路        chessboard[row][col] = "Q";        dfs(row + 1, chessboard);        chessboard[row][col] = "."; // 回溯回来      }    }  };
// 判断当前节点是否符合 N 皇后的要求 -- 需要注意,这里 [0,n-1] 是从左往右算 function isValid(row, col, chessboard) { // 同一列 for (let i = 0; i < row; i++) { if (chessboard[i][col] === "Q") { return false; } } // 从左往右 45` 倾斜 for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (chessboard[i][j] === "Q") { return false; } } // 从右往左 135` 倾斜 for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (chessboard[i][j] === "Q") { return false; } } // 如果不是同一列或者左右斜线,则满足要求 return true; }
// 将二维数组的 N 皇后转成一维数组字符串形式 function getStrChessboad(chessboard) { const ret = []; chessboard.forEach((row) => { let str = ""; row.forEach((item) => { str += item; }); ret.push(str); }); return ret; }
const chessboard = new Array(n).fill([]).map(() => new Array(n).fill(".")); dfs(0, chessboard); return ret;};
复制代码

52. N 皇后 II

分析


  1. 问题和 51. N 皇后 基本一样,只是求的值从完整的 N 皇后方案,变成了只要知道有几个就可以了

  2. 所以第三部分转换可以直接删除,然后直接拷贝过来即可


var totalNQueens = function (n) {  let ret = 0;
const dfs = (row, chessboard) => { if (row === n) { ret++; return; }
for (let col = 0; col < n; col++) { if (isValid(row, col, chessboard)) { chessboard[row][col] = "Q"; dfs(row + 1, chessboard); chessboard[row][col] = "."; } }
function isValid(row, col, chessboard) { for (let i = 0; i < row; i++) { if (chessboard[i][col] === "Q") return false; }
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (chessboard[i][j] === "Q") return false; }
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (chessboard[i][j] === "Q") return false; } return true; } }; const chessboard = new Array(n).fill([]).map(() => new Array(n).fill(".")); dfs(0, chessboard); return ret;};

复制代码


@分析


  1. 回溯过程以及很简单了,但是判定条件 isValid 有没有更好的办法来处理呢

  2. 我们在第一题的时候是为了要创建一个实例 N 皇后,所以需要用到数组,而现在不需要具体的 N 皇后,所以不用数组的形式也可以用其他的形式来展示 N 皇后

  3. 用 3 个二进制的位 col, dlr, drl 分别表示 列上的值,从左启动 45 的值, 从右启动的 135 的值

  4. 这里 col 是很容易理解的,因为在每一行的 i 值,当了需要判断的 row ,对应的 i 的值是不会发生变化的

  5. 对于 dlr 来说,二进制对应的位是倾斜的,只有这样的值才符合 45` 倾斜;同理, drl 也是一样的 Q . . . . .. Q . . . . .. Q . . . . .. Q . . . . .. Q . . . . .

  6. 所以


var totalNQueens = function (n) {  let ret = 0;  const dfs = (r, col, dlr, drl) => {    if (r === n) {      ret++;      return;    }    for (let i = 0; i < n; i++) {      // 当前坐标转成二进制位对应的值      const _col = 1 << i;      const _dlr = 1 << (r + i); // 这里表示在其他行 的 i 值,到了当前 r,对应的值就应该是  1 << (r+i), 所以我们设置这么一个值去试其他的值,看看是否满足要求      const _drl = 1 << (n - i + r);      if ((col & _col) || (dlr & _dlr) || (drl & _drl)) continue; // 只要有一个为 true,      dfs(r + 1, col | _col, dlr | _dlr, drl | _drl);    }  };  dfs(0, 0, 0, 0);  return ret;};

复制代码


用户头像

js2030code

关注

还未添加个人签名 2022-09-14 加入

还未添加个人简介

评论

发布
暂无评论
前端leetcde算法面试套路之回溯_JavaScript_js2030code_InfoQ写作社区