07回溯算法/代码随想录

• 回溯完结
  

8.5分列

• 全分列（力扣46）
  都可以基于前面组合的思绪，只是不必要树枝去重和树层去重。但是一个元素不能在雷同元素中利用，可以利用used数组来生存利用过的数字，在添加数字到效果（path数组）中的时间判断有没有出现过。固然由于没有重复元素，以是也可以直接利用效果集（path数组）判断有没有重复数字。思绪很简朴
  1. class Solution {
  2.     List<List<Integer>> res = new ArrayList<>();
  3.     List<Integer> path = new ArrayList<>();
  5.     public void backTracking(int[] nums) {
  6.         if (nums.length == path.size()) {
  7.             res.add(new ArrayList<>(path));
  8.         }
  9.         for (int i = 0; i < nums.length; ++i) {
  10.             if (path.contains(nums[i])) continue;
  11.             path.add(nums[i]);
  12.             backTracking(nums);
  13.             path.remove(path.size() - 1);
  14.         }
  15.     }
  17.     public List<List<Integer>> permute(int[] nums) {
  18.         backTracking(nums);
  19.         return res;
  20.     }
  21. }

  复制代码
• 全分列II（力扣47）
  与全分列的区别是，由于有重复，以是我别的一个1就不能利用。又是树枝去重，直接模板，固然也可以排序好后，举行set，也能得到终极效果，但是如许的时间和空间复杂度都会变高。这里不能利用startIndex，由于是分列，不是组合，就不能利用9.2组合第五题的那种简介写法。只有每层的开始遍历节点不一样，才可以使得倒霉用used数组直接制止树枝去重。
  1. class Solution {
  2.     List<List<Integer>> res = new ArrayList<>();
  3.     List<Integer> path = new ArrayList<>();
  4.     boolean[] used;
  6.     public void backTracking(int[] nums) {
  7.         if (nums.length == path.size()) {
  8.             res.add(new ArrayList<>(path));
  9.         }
  10.         for (int i = 0; i < nums.length; ++i) {
  11.             // 跳过重复的元素，确保我们不在同一层递归中使用相同的元素  used[i-1]为false是树层上的去重，因为数层上会回溯，前一个一定是false，相反树枝是就是true
  12.             if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
  13.             // 跳过已经使用过的元素                                                         
  14.             if (used[i]) continue;
  15.             
  16.             // 做选择
  17.             used[i] = true;
  18.             path.add(nums[i]);
  19.             
  20.             // 递归调用
  21.             backTracking(nums);
  22.             
  23.             // 撤销选择
  24.             path.remove(path.size() - 1);
  25.             used[i] = false;
  26.         }
  27.     }
  29.     public List<List<Integer>> permuteUnique(int[] nums) {
  30.         Arrays.sort(nums); // 排序是为了避免重复的排列
  31.         used = new boolean[nums.length];
  32.         backTracking(nums);
  33.         return res;
  34.     }
  35. }

  复制代码

8.6棋盘

• n皇后(力扣51)，没什么特点，只是多了一些独有的条件判断。由于一行一列只能一个元素，以是这里是一维递归，和下一题二维递归不一样。决定一维递归和二维递归的因素是什么呢，起始就是构造树的过程，假如第一层一次遍历就能竣事就是一维，反之不可就不是。
  1. class Solution {
  2.     List<List<String>> res = new ArrayList<>();
  3.     List<String> path = new ArrayList<>();
  5.     public boolean isValid(int s, int n, int col) {
  6.         // 列合法判断
  7.         for (int i = 0; i < s; ++i) {
  8.             if (path.get(i).charAt(col) == 'Q') {
  9.                 return false;
  10.             }
  11.         }
  13.         // 判断是否45°合法
  14.         for (int i = s - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
  15.             if (path.get(i).charAt(j) == 'Q') {
  16.                 return false;
  17.             }
  18.         }
  20.         // 判断是否135°合法
  21.         for (int i = s - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
  22.             if (path.get(i).charAt(j) == 'Q') {
  23.                 return false;
  24.             }
  25.         }
  27.         return true;
  28.     }
  30.     public void backTracking(int s, int n) {
  31.         if (s == n) {
  32.             res.add(new ArrayList<>(path));
  33.             return;
  34.         }
  36.         for (int i = 0; i < n; ++i) {
  37.             if (isValid(s, n, i)) {
  38.                 // 放置皇后
  39.                 char[] rowArray = path.get(s).toCharArray();
  40.                 rowArray[i] = 'Q';
  41.                 path.set(s, new String(rowArray));
  43.                 // 递归到下一行
  44.                 backTracking(s + 1, n);
  46.                 // 回溯，移除皇后
  47.                 rowArray[i] = '.';
  48.                 path.set(s, new String(rowArray));
  49.             }
  50.         }
  51.     }
  53.     public List<List<String>> solveNQueens(int n) {
  54.         // 初始化棋盘
  55.         for (int i = 0; i < n; ++i) {
  56.             char[] row = new char[n];
  57.             Arrays.fill(row, '.');
  58.             path.add(new String(row));
  59.         }
  61.         // 开始回溯
  62.         backTracking(0, n);
  63.         return res;
  64.     }
  65. }

  复制代码
  这里以是最直观的for循环来举行条件判断，固然你也可以利用雷同上面的used数组来表明哪些被占用过了。
  先容下代码逻辑，制止条件和参数，不必要转达返回值以是void。参数呢，必要当前皇后放在几行几列，固然也要知道这个n*n的各自有多大。
  单层循环，满足条件的就举行存放，不满足不要（也就相当于剪枝了），留意要回溯。
  这里有一个留意点：举行条件判断为什么没有写行判断，是由于我们就是在一行一行摆，已经确定了一行只有一个元素。以是你也可以一列一列摆，如许可以少些列的判断，写一个行的判断
  
• 解数独（37）
  和n皇后的差别是，每行每列不愿定只有一个元素。但是头脑是划一的，满足条件的举行迭代回溯，不满足的就先容了。以是单层循环的结构是划一的，只是具体的判断满足条件的方法以及数据的维度不一样(这里是二位递归，必要对每一个元素举行判断和递归，而n皇后由于行上也有限定，以是只必要一位递归)。先上代码，再讲思绪。
  1. class Solution {
  2.     public void solveSudoku(char[][] board) {
  3.         backTracking(board);
  4.     }
  6.     boolean backTracking(char[][] board) {
  7.         for (int i = 0; i < 9; ++i) {
  8.             for (int j = 0; j < 9; ++j) {
  9.                 if (board[i][j] != '.') continue;  // 如果当前不是空格，跳过
  11.                 for (char k = '1'; k <= '9'; ++k) {
  12.                     if (isValid(i, j, k, board)) {
  13.                         board[i][j] = k;  // 尝试放置 k
  14.                         if (backTracking(board)) {  // 如果成功则返回 true
  15.                             return true;
  16.                         }
  17.                         board[i][j] = '.';  // 回溯，移除 k
  18.                     }
  19.                 }
  20.                 return false;  // 如果 1-9 都不能放入该位置，则返回 false
  21.             }
  22.         }
  23.         return true;  // 如果没有空位了，则返回 true，表示成功
  24.     }
  26.     private boolean isValid(int row, int col, char val, char[][] board) {
  27.         // 同行是否重复
  28.         for (int i = 0; i < 9; i++) {
  29.             if (board[row][i] == val) {
  30.                 return false;
  31.             }
  32.         }
  33.         // 同列是否重复
  34.         for (int j = 0; j < 9; j++) {
  35.             if (board[j][col] == val) {
  36.                 return false;
  37.             }
  38.         }
  39.         // 9宫格里是否重复
  40.         int startRow = (row / 3) * 3;  // 余数的思想
  41.         int startCol = (col / 3) * 3;
  42.         for (int i = startRow; i < startRow + 3; i++) {
  43.             for (int j = startCol; j < startCol + 3; j++) {
  44.                 if (board[i][j] == val) {
  45.                     return false;
  46.                 }
  47.             }
  48.         }
  49.         return true;
  50.     }
  51. }

  复制代码
  参数和返回值，由于大概有很多效果，但是只要有一种方案就直接竣事，以是我很依赖与子树告诉父节点是否满足，以是返回值为boolean（到底满不满足）。参数的话，这题留意是在原先给的数组上举行修改！！（这里记着，反面写单层递归是关键点逻辑），以是直接传数组即可。
  制止条件完全不必要，由于我们利用了boolean转作为返回值，可以很轻松的判断出效果，要是有一个地方什么数字都填不了，直接就false。别的的可以的话，就递归转达，满足就制止树层上的迭代和循环，逻辑写在if (backTracking(board)) {return true};，末了没有标题就return true
  单层循环呢，起始就是先判断是否正当，正当就继承，有人会问为什么这里回溯要加if判断。这里我踩了坑，没有写，末了每次都是false。缘故因由是全部的利用都是直接在返答复案的数组中利用的。假如我加上判断，符合的就不绝递归下去，末了直接返答复案，也就是我刚刚说的逻辑，不可的话，就false再回到一开始分岔的地方。当假如不写判断呢，那么一开始照旧按照逻辑走，走完一个精确满足的环境了，它会继承走到分岔路重新开始重新修改，也就是没有纵然的剪枝和制止。（前面的标题不必要是由于末了返回的效果不是在同一个数据结构上修改，而是新建的互不影响，固然这不是本题的关键，关键照旧回溯头脑，这只是标题标一个小tips）
  

8.7别的

• 递增子序列（491）
  大抵的去重方法与之前无太大区别，紧张的是思绪。这里紧张的是怎样做到树层和树枝去重，先上代码
  1. class Solution {
  2.     List<List<Integer>> res = new ArrayList<>();
  3.     List<Integer> path = new ArrayList<>();
  5.     public void backTracking(int[] nums, int startIndex) {
  6.         if (path.size() >= 2) {
  7.             res.add(new ArrayList<>(path));
  8.         }
  9.         Set<Integer> used = new HashSet<>();
  10.         for (int i = startIndex; i < nums.length; ++i) {
  11.             if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) || used.contains(nums[i])) continue;
  12.             path.add(nums[i]); // 添加当前数字到路径
  13.             used.add(nums[i]); // 记录当前数字已用过
  14.             backTracking(nums, i + 1); // 递归
  15.             path.remove(path.size() - 1); // 回溯，移除最后一个数字
  16.         }
  17.     }
  19.     public List<List<Integer>> findSubsequences(int[] nums) {
  20.         backTracking(nums, 0);
  21.         return res;
  22.     }
  23. }

  复制代码
  
  
  • 前一项大于后一项要直接删除，以是判断条件写了这个continue，这相当于树枝去重（但严格意义上不是去重，由于这个是标题条件要求的。剪枝是在满足要求的环境下镌汰重复盘算）。
    
  • 树层去重，由于是取全部节点数大于即是2的节点。数组内恣意数不重复的随意组合，会使得在同一层的数枝（右边重复的）肯定会被靠左的树枝包罗重复，随意加上used.contains(nums)往复重
    附上条记草稿
    在这里插入图片形貌
    
  
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金