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

2023-01-09 08:59:27 浏览数 (1)

前言

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

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

下一个 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)
代码语言：javascript复制
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)
代码语言：javascript复制
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 形成对比

参考视频：传送门

代码语言：javascript复制
 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 的，表示不可以重复取上一次哪一个值
代码语言：javascript复制
 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. 组合总和 的特殊情况，只是判定条件有出入
代码语言：javascript复制
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. 然后超时了 */
代码语言：javascript复制
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. dpi 表示值为 i 的时候存在的组合数量
  2. 状态转移方程 dpi = sum(dp[i-numsk])
  3. base case dp0 = 1
代码语言：javascript复制
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)
代码语言：javascript复制
 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)
代码语言：javascript复制
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. 然后在回溯过程中，如果下一次迭代的值和当前值一样，则跳过，达到去重的效果
代码语言：javascript复制
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. 回文子串的判定可以简单的用左右双指针来实现
代码语言：javascript复制
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. 这里的判定条件也多，只需要将合乎要求的条件算上，就能砍掉不少的分支
代码语言：javascript复制
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)
代码语言：javascript复制
 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)
代码语言：javascript复制
 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)
代码语言：javascript复制
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 大部分，回溯的方式遍历树，找出符合要求的节点 chessboardrow, 将符合要求的二维数组转换成符合要求的字符串数组
  3. 时间复杂度 O(n∗logn)
代码语言：javascript复制
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. 所以第三部分转换可以直接删除，然后直接拷贝过来即可
代码语言：javascript复制
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. 所以
代码语言：javascript复制
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;
};
编程算法leetcode javascript

0 人点赞