LeetCode——Backtracking

末蓝、 2023-06-19 09:38 117阅读 0赞

Backtracking

目录

  1. Backtracking
  2. 数字键盘组合
  3. IP 地址划分
  4. 在矩阵中寻找字符串
  5. 输出二叉树中所有从根到叶子的路径
  6. 排列
  7. 含有相同元素求排列
  8. 组合
  9. 组合求和
  10. 含有相同元素的组合求和
  11. 1-9 数字的组合求和
  12. 子集
  13. 含有相同元素求子集
  14. 分割字符串使得每个部分都是回文数
  15. 数独
  16. N皇后

1. Backtracking

Backtracking（回溯）属于 DFS。
普通 DFS 主要用在可达性问题，这种问题只需要执行到特点的位置然后返回即可。

而 Backtracking 主要用于求解 排列组合 问题，例如有 { ‘a’,‘b’,‘c’ } 三个字符，求解所有由这三个字符排列得到的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。

因为 Backtracking 不是立即返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：
在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；

但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。

2. 数字键盘组合

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
在这里插入图片描述

  1. private static final String[] KEYS = {
  2.     "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
  4.     public List<String> letterCombinations(String digits){
  6.         List<String> combinations = new ArrayList<>();
  7.         if (digits==null||digits.length()==0){
  9.             return combinations;
  10.         }
  11.         doCombination(new StringBuilder(),combinations,digits);
  12.         return combinations;
  13.     }
  15.     private void doCombination(StringBuilder prefix, List<String> combinations, final String digits) {
  17.         if (prefix.length()==digits.length()){
  19.             combinations.add(prefix.toString());
  20.             return;
  21.         }
  22.         int num = digits.charAt(prefix.length()) - '0';
  23.         String key = KEYS[num];
  24.         for (char c : key.toCharArray()) {
  26.             prefix.append(c);
  27.             doCombination(prefix,combinations,digits);
  28.             prefix.deleteCharAt(prefix.length()-1);
  29.         }
  30.     }

3. IP 地址划分

https://leetcode-cn.com/problems/restore-ip-addresses

在这里插入图片描述

  1. public List<String> restoreIpAddresses(String s) {
  3.         List<String> addresses = new ArrayList<>();
  4.         StringBuilder tempAddress = new StringBuilder();
  5.         doRestore(0, tempAddress, addresses, s);
  6.         return addresses;
  7.     }
  9.     private void doRestore(int k, StringBuilder tempAddress, List<String> addresses, String s) {
  11.         //整体分成4个段
  12.         if (k == 4 || s.length() == 0) {
  14.             if (k == 4 && s.length() == 0) {
  16.                 addresses.add(tempAddress.toString());
  17.             }
  18.             return;
  19.         }
  20.         //每个段的判断
  21.         for (int i = 0; i < s.length() && i <= 2; i++) {
  23.             if (i != 0 && s.charAt(0) == '0') {
  25.                 break;
  26.             }
  27.             String part = s.substring(0, i + 1);
  28.             if (Integer.valueOf(part) <= 255) {
  30.                 if (tempAddress.length() != 0) {
  32.                     part = "." + part;
  33.                 }
  34.                 tempAddress.append(part);
  35.                 doRestore(k + 1, tempAddress, addresses, s.substring(i + 1));
  36.                 tempAddress.delete(tempAddress.length() - part.length(), tempAddress.length());
  37.             }
  38.         }
  39.     }

4. 在矩阵中寻找字符串

https://leetcode-cn.com/problems/word-search

在这里插入图片描述
题目描述：给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

  1. private final static int[][] direction = {
  2.     {
  3.     1, 0}, {
  4.     -1, 0}, {
  5.     0, 1}, {
  6.     0, -1}};
  7.     private int m, n;
  9.     public boolean exist(char[][] board, String word) {
  11.         if (word == null || word.length() == 0) {
  13.             return true;
  14.         }
  15.         if (board == null || board.length == 0 || board[0].length == 0) {
  17.             return false;
  18.         }
  19.         m = board.length;
  20.         n = board[0].length;
  21.         boolean[][] visited = new boolean[m][n];
  22.         for (int r = 0; r < m; r++) {
  24.             for (int c = 0; c < n; c++) {
  26.                 if (backtracking(0, r, c, visited, board, word)) {
  28.                     return true;
  29.                 }
  30.             }
  31.         }
  32.         return false;
  33.     }
  35.     private boolean backtracking(int curLen, int r, int c, boolean[][] visited, final char[][] board, final String word) {
  37.         if (curLen == word.length()) {
  39.             return true;
  40.         }
  42.         if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(curLen) || visited[r][c]) {
  44.             return false;
  45.         }
  47.         visited[r][c] = true;
  48.         for (int[] d : direction) {
  50.             if (backtracking(curLen + 1, r + d[0], c + d[1], visited, board, word)) {
  52.                 return true;
  53.             }
  54.         }
  55.         visited[r][c] = false;
  56.         return false;
  57.     }

5. 输出二叉树中所有从根到叶子的路径

https://leetcode.com/problems/binary-tree-paths
在这里插入图片描述

  1. public static class TreeNode {
  3.         int val = 0;
  4.         TreeNode left = null;
  5.         TreeNode right = null;
  7.         public TreeNode(int val) {
  9.             this.val = val;
  10.         }
  11.     }
  13.     public List<String> binaryTreePaths(TreeNode root) {
  15.         List<String> paths = new ArrayList<>();
  16.         if (root == null) {
  18.             return paths;
  19.         }
  20.         List<Integer> values = new ArrayList<>();
  21.         backtracking(root, values, paths);
  22.         return paths;
  23.     }
  25.     private void backtracking(TreeNode node, List<Integer> values, List<String> paths) {
  27.         if (node == null) {
  29.             return;
  30.         }
  31.         values.add(node.val);
  32.         if (isLeaf(node)) {
  34.             paths.add(buildPath(values));
  35.         } else {
  37.             backtracking(node.left, values, paths);
  38.             backtracking(node.right, values, paths);
  39.         }
  40.         values.remove(values.size() - 1);
  41.     }
  43.     private String buildPath(List<Integer> values) {
  45.         StringBuilder str = new StringBuilder();
  46.         for (int i = 0; i < values.size(); i++) {
  48.             str.append(values.get(i));
  49.             if (i != values.size() - 1) {
  51.                 str.append("->");
  52.             }
  53.         }
  54.         return str.toString();
  55.     }
  57.     private boolean isLeaf(TreeNode node) {
  59.         return node.left == null && node.right == null;
  60.     }

6. 排列

在这里插入图片描述
题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。

  1. public List<List<Integer>> permute(int[] nums) {
  3.         List<List<Integer>> permutes = new ArrayList<>();
  4.         List<Integer> permuteList = new ArrayList<>();
  5.         boolean[] hasVisited = new boolean[nums.length];
  6.         backtracking(permuteList, permutes, hasVisited, nums);
  7.         return permutes;
  8.     }
  10.     private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, int[] nums) {
  12.         if (permuteList.size() == nums.length) {
  14.             permutes.add(new ArrayList<>(permuteList)); //重新构造一个 List
  15.             return;
  16.         }
  17.         for (int i = 0; i < visited.length; i++) {
  19.             if (visited[i]) {
  21.                 continue;
  22.             }
  23.             visited[i] = true;
  24.             permuteList.add(nums[i]);
  25.             backtracking(permuteList, permutes, visited, nums);
  26.             permuteList.remove(permuteList.size() - 1);
  27.             visited[i] = false;
  28.         }
  29.     }

7. 含有相同元素求排列

在这里插入图片描述
题目描述：数组元素可能含有相同的元素，进行排列时就有可能出现重复的排列，要求重复的排列只返回一个。

在实现上，和 Permutations 不同的是要先排序，然后在添加一个元素时，判断这个元素是否等于前一个元素，如果等于，并且前一个元素还未访问，那么就跳过这个元素。

  1. public List<List<Integer>> permuteUnique(int[] nums) {
  3.         List<List<Integer>> permutes = new ArrayList<>();
  4.         List<Integer> permuteList = new ArrayList<>();
  5.         Arrays.sort(nums);
  6.         boolean[] hasVisited = new boolean[nums.length];
  7.         backtracking(permuteList, permutes, hasVisited, nums);
  8.         return permutes;
  9.     }
  11.     private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, int[] nums) {
  13.         if (permuteList.size() == nums.length) {
  15.             permutes.add(new ArrayList<>(permuteList));
  16.             return;
  17.         }
  19.         for (int i = 0; i < visited.length; i++) {
  21.             if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
  23.                 continue; //防止重复
  24.             }
  25.             if (visited[i]) {
  27.                 continue;
  28.             }
  29.             visited[i] = true;
  30.             permuteList.add(nums[i]);
  31.             backtracking(permuteList, permutes, visited, nums);
  32.             permuteList.remove(permuteList.size() - 1);
  33.             visited[i] = false;
  34.         }
  35.     }

8. 组合

https://leetcode-cn.com/problems/combinations
在这里插入图片描述

  1. public List<List<Integer>> combine(int n, int k) {
  3.         List<List<Integer>> combinations = new ArrayList<>();
  4.         List<Integer> combineList = new ArrayList<>();
  5.         backtracking(combineList, combinations, 1, k, n);
  6.         return combinations;
  7.     }
  9.     private void backtracking(List<Integer> combineList, List<List<Integer>> combinations, int start, int k, int n) {
  11.         if (k == 0) {
  13.             combinations.add(new ArrayList<>(combineList));
  14.             return;
  15.         }
  16.         for (int i = start; i <= n - k + 1; i++) {
  18.             combineList.add(i);
  19.             backtracking(combineList, combinations, i + 1, k - 1, n);
  20.             combineList.remove(combineList.size() - 1);
  21.         }
  22.     }

9. 组合求和

https://leetcode.com/problems/combination-sum/description/
在这里插入图片描述
题目描述：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

  • 所有数字（包括 target）都是正整数。

  • 解集不能包含重复的组合。

    public List> combiationSum(int[] candidates, int target) {

    1.     List<List<Integer>> combinations = new ArrayList<>();
    2.     backtracking(new ArrayList<>(), combinations, 0, target, candidates);
    3.     return combinations;
    5. }
    7. private void backtracking(ArrayList<Integer> tempCombination, List<List<Integer>> combinations, int start, int target, int[] candidates) {
    9.     if (target == 0) {
    11.         combinations.add(new ArrayList<>(tempCombination));
    12.         return;
    13.     }
    15.     for (int i = start; i < candidates.length; i++) {
    17.         if (candidates[i] <= target) {
    19.             tempCombination.add(candidates[i]);
    20.             backtracking(tempCombination, combinations, i, target - candidates[i], candidates);
    21.             tempCombination.remove(tempCombination.size() - 1);
    22.         }
    23.     }
    24. }

10. 含有相同元素的组合求和

https://leetcode.com/problems/combination-sum-ii/description/
在这里插入图片描述
题目描述：给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

  • 所有数字（包括目标数）都是正整数。

  • 解集不能包含重复的组合。

    public List> combinationSum2(int[] candidates, int target) {

    1.     List<List<Integer>> combinations = new ArrayList<>();
    2.     Arrays.sort(candidates);
    3.     backtracking(combinations, new ArrayList<>(), new boolean[candidates.length], 0, target, candidates);
    4.     return combinations;
    5. }
    7. private void backtracking(List<List<Integer>> combinations, List<Integer> combinationList, boolean[] visited, int start, int target, int[] candidates) {
    9.     if (target == 0) {
    11.         combinations.add(new ArrayList<>(combinationList));
    12.         return;
    13.     }
    15.     for (int i = start; i < candidates.length; i++) {
    17.         if (i != 0 && candidates[i] == candidates[i - 1] && !visited[i - 1]) {
    19.             continue;
    20.         }
    21.         if (candidates[i] <= target) {
    23.             combinationList.add(candidates[i]);
    24.             visited[i] = true;
    25.             backtracking(combinations, combinationList, visited, i + 1, target - candidates[i], candidates);
    26.             visited[i] = false;
    27.             combinationList.remove(combinationList.size() - 1);
    28.         }
    29.     }
    30. }

11. 1-9 数字的组合求和

https://leetcode.com/problems/combination-sum-iii/description/
在这里插入图片描述
题目描述：找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

  • 所有数字都是正整数。

  • 解集不能包含重复的组合。

    public List> combinationSum3(int k, int n) {

    1.     List<List<Integer>> combinations = new ArrayList<>();
    2.     List<Integer> combinationList = new ArrayList<>();
    3.     backtracking(combinationList, combinations, 1, k, n);
    4.     return combinations;
    5. }
    7. private void backtracking(List<Integer> combinationList, List<List<Integer>> combinations, int start, int k, int target) {
    9.     if (k == 0 && target == 0) {
    11.         combinations.add(new ArrayList<>(combinationList));
    12.         return;
    13.     }
    14.     if (k == 0 || target == 0) {
    16.         return;
    17.     }
    18.     for (int i = start; i <= 9; i++) {
    20.         combinationList.add(i);
    21.         backtracking(combinationList, combinations, i + 1, k - 1, target - i);
    22.         combinationList.remove(combinationList.size() - 1);
    23.     }
    24. }

12. 子集

https://leetcode.com/problems/subsets-ii/description/
在这里插入图片描述
题目描述：找出集合的所有子集，子集不能重复，[1, 2] 和 [2, 1] 这种子集算重复

  1. public List<List<Integer>> subsets(int[] nums) {
  3.         List<List<Integer>> subsets = new ArrayList<>();
  4.         List<Integer> tempSubset = new ArrayList<>();
  5.         for (int size = 0; size <= nums.length; size++) {
  7.             backtracking(subsets, tempSubset, size, 0, nums);
  8.         }
  9.         return subsets;
  10.     }
  12.     private void backtracking(List<List<Integer>> subsets, List<Integer> tempSubset, int size, int start, int[] nums) {
  14.         if (size == 0) {
  16.             subsets.add(new ArrayList<>(tempSubset));
  17.         }
  19.         for (int i = start; i < nums.length; i++) {
  21.             tempSubset.add(nums[i]);
  22.             backtracking(subsets, tempSubset, size - 1, i + 1, nums);
  23.             tempSubset.remove(tempSubset.size() - 1);
  24.         }
  25.     }

13. 含有相同元素求子集

在这里插入图片描述
题目描述：给定一个可能包含重复数的整数集合，返回所有可能的子集(幂集)。

注意:解决方案集不能包含重复的子集。

  1. public List<List<Integer>> subsets(int[] nums) {
  3.         List<List<Integer>> subsets = new ArrayList<>();
  4.         List<Integer> tempSubset = new ArrayList<>();
  5.         for (int size = 0; size <= nums.length; size++) {
  7.             backtracking(subsets, tempSubset, size, 0, nums);
  8.         }
  9.         return subsets;
  10.     }
  12.     private void backtracking(List<List<Integer>> subsets, List<Integer> tempSubset, int size, int start, int[] nums) {
  14.         if (size == 0) {
  16.             subsets.add(new ArrayList<>(tempSubset));
  17.         }
  19.         for (int i = start; i < nums.length; i++) {
  21.             tempSubset.add(nums[i]);
  22.             backtracking(subsets, tempSubset, size - 1, i + 1, nums);
  23.             tempSubset.remove(tempSubset.size() - 1);
  24.         }
  25.     }

14. 分割字符串使得每个部分都是回文数

https://leetcode-cn.com/problems/palindrome-partitioning
在这里插入图片描述
题目描述：给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

  1. public List<List<String>> partition(String s) {
  3.         List<List<String>> partitions = new ArrayList<>();
  4.         List<String> tempPartition = new ArrayList<>();
  5.         doPartition(s, partitions, tempPartition);
  6.         return partitions;
  7.     }
  9.     private void doPartition(String s, List<List<String>> partitions, List<String> tempPartition) {
  12.         if (s.length() == 0) {
  14.             partitions.add(new ArrayList<>(tempPartition));
  15.             return;
  16.         }
  17.         for (int i = 0; i < s.length(); i++) {
  19.             if (isPalindrome(s, 0, i)) {
  21.                 tempPartition.add(s.substring(0, i + 1));
  22.                 doPartition(s.substring(i + 1), partitions, tempPartition);
  23.                 tempPartition.remove(tempPartition.size() - 1);
  24.             }
  25.         }
  26.     }
  28.     private boolean isPalindrome(String s, int begin, int end) {
  30.         while (begin < end) {
  32.             if (s.charAt(begin++) != s.charAt(end--)) {
  34.                 return false;
  35.             }
  36.         }
  37.         return true;
  38.     }

15. 数独

https://leetcode-cn.com/problems/sudoku-solver/solution/jie-shu-du-by-leetcode/
在这里插入图片描述
在这里插入图片描述
题目描述：编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

  • 空白格用 ‘.’ 表示。

    private boolean[][] rowsUsed = new boolean[9][10];

    1. private boolean[][] colsUsed = new boolean[9][10];
    2. private boolean[][] cubesUsed = new boolean[9][10];
    3. private char[][] board;
    5. public void solveSudoku(char[][] board) {
    7.     this.board = board;
    8.     for (int i = 0; i < 9; i++) {
    10.         for (int j = 0; j < 9; j++) {
    12.             if (board[i][j] == '.') {
    14.                 continue;
    15.             }
    16.             int num = board[i][j] - '0';
    17.             rowsUsed[i][num] = true;
    18.             colsUsed[j][num] = true;
    19.             cubesUsed[cubes(i, j)][num] = true;
    20.         }
    21.         backtracking(0, 0);
    22.     }
    23. }
    25. private boolean backtracking(int row, int col) {
    27.     while (row < 9 && board[row][col] != '.') {
    29.         row = col == 8 ? row + 1 : row;
    30.         col = col == 8 ? 0 : col + 1;
    31.     }
    32.     if (row == 9) {
    34.         return true;
    35.     }
    36.     for (int num = 1; num <= 9; num++) {
    38.         if (rowsUsed[row][num] || colsUsed[col][num] || cubesUsed[cubes(row, col)][num]) {
    40.             continue;
    41.         }
    42.         rowsUsed[row][num] = colsUsed[col][num] = cubesUsed[cubes(row, col)][num] == true;
    43.         board[row][col] = (char) (num + '0');
    44.         if (backtracking(row, col)) {
    46.             return true;
    47.         }
    48.         board[row][col] = '.';
    49.         rowsUsed[row][num] = colsUsed[col][num] = cubesUsed[cubes(row, col)][num] == false;
    50.     }
    51.     return false;
    52. }
    54. private int cubes(int i, int j) {
    56.     int r = i / 3;
    57.     int c = j / 3;
    58.     return r * 3 + c;
    59. }

16. N皇后

https://leetcode-cn.com/problems/n-queens/solution/nhuang-hou-by-leetcode/在这里插入图片描述
题目描述：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

在这里插入图片描述

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

  1. private List<List<String>> solutions;
  2.     private char[][] nQueues;
  3.     private boolean[] colUsed;
  4.     private boolean[] diagonals45Used;
  5.     private boolean[] diagonals135Used;
  6.     private int n;
  8.     public List<List<String>> solveNQueues(int n) {
  10.         solutions = new ArrayList<>();
  11.         nQueues = new char[n][n];
  12.         for (int i = 0; i < n; i++) {
  14.             Arrays.fill(nQueues[i], '.');
  15.         }
  16.         colUsed = new boolean[n];
  17.         diagonals45Used = new boolean[2 * n - 1];
  18.         diagonals135Used = new boolean[2 * n - 1];
  19.         this.n = n;
  20.         backtracking(0);
  21.         return solutions;
  22.     }
  24.     private void backtracking(int row) {
  26.         if (row == n) {
  28.             List<String> list = new ArrayList<>();
  29.             for (char[] chars : nQueues) {
  31.                 list.add(new String(chars));
  32.             }
  33.             solutions.add(list);
  34.             return;
  35.         }
  37.         for (int col = 0; col < n; col++) {
  39.             int diagonals45Idx = row + col;
  40.             int diagonals135Idx = n - 1 - (row - col);
  41.             if (colUsed[col] || diagonals45Used[diagonals45Idx] || diagonals135Used[diagonals135Idx]) {
  43.                 continue;
  44.             }
  45.             nQueues[row][col] = 'Q';
  46.             colUsed[col] = diagonals45Used[diagonals45Idx] = diagonals135Used[diagonals135Idx] = true;
  47.             backtracking(row + 1);
  48.             colUsed[col] = diagonals45Used[diagonals45Idx] = diagonals135Used[diagonals135Idx] = false;
  49.             nQueues[row][col] = '.';
  50.         }
  51.     }

发表评论

表情：
评论列表 （有 0 条评论，117人围观）

还没有评论，来说两句吧...

相关阅读