回溯Backtracking Algorithm

1) 入门例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 回溯
 * 
 * 程序在运行过程中分成了多个阶段
 * 通过某些手段,将数据恢复到之前某一阶段,这就称之为回溯
 * 手段包括
 *      方法栈
 *      自定义栈
 */
public class Backtracking {
    public static void main(String[] args) {
        rec(1);
    }
 
    private static void rec(int n) {
        if(n==3){
            return ;
        }
        System.out.println(n);
        rec(n+1);
        System.out.println(n);
    }
}

如果是集合又有什么样的效果呢?

1
如果用的是可变的集合或者数组必须手动的恢复集合状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Backtracking {
    public static void main(String[] args) {
        rec(1, new LinkedList<>());
    }
 
    static void rec(int n, LinkedList<String> list) {
        if (n == 3) {
            return;
        }
        System.out.println("before:" + list);
        list.push("a");
        rec(n + 1, list);
        list.pop();
        System.out.println("after:" + list);
    }
}
1
2
3
4
5
6
7
8
9
10
rec(1, [])
├── before: []
├── push "a" → rec(2, ["a"])
│   ├── before: [a]
│   ├── push "a" → rec(3, [a, a])
│   │   └── n == 3 → return
│   ├── pop → [a]
│   └── after: [a]
├── pop → []
└── after: []
1
2
3
4
before:[]
before:[a]
after:[a]
after:[]

这段代码虽然简单，但完整地展示了回溯的三步：

选择 → 递归 → 撤销，最终输出是：

2) 全排列-Leetcode 46

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 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]]

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[]
├── 1
│   ├── 1,2
│   │   └── 1,2,3
│   └── 1,3
│       └── 1,3,2
├── 2
│   ├── 2,1
│   │   └── 2,1,3
│   └── 2,3
│       └── 2,3,1
└── 3
    ├── 3,1
    │   └── 3,1,2
    └── 3,2
        └── 3,2,1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class PermuteLeetcode46 {
    static List<List<Integer>> permute(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        LinkedList<Integer> stack = new LinkedList<>();
        List<List<Integer>> r = new ArrayList<>();
        rec(nums, visited, stack, r);
        return r;
    }
 
    static void rec(int[] nums, boolean[] visited, LinkedList<Integer> stack, List<List<Integer>> r) {
        if (stack.size() == nums.length) {
            r.add(new ArrayList<>(stack));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(visited[i]){
                continue;
            }
            stack.push(nums[i]);
            visited[i] = true;
            rec(nums, visited, stack, r);
            stack.pop();
            visited[i] = false;
        }
    }
 
    public static void main(String[] args) {
        List<List<Integer>> permute = permute(new int[]{1, 2, 3});
        for (List<Integer> s : permute) {
            System.out.println(s);
        }
    }
}

3) 全排列II-Leetcode 47

47. 全排列 II - 力扣（LeetCode）

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

示例 1：

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

示例 2：

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
1
2
3
4
5
6
7
        []
       / \
      1   3
   /    \   \
  11'    13  31
 / \     |    \
11'3   131'   311'
  1. 根节点：[] 表示空排列，即还没有选择任何数字。
  2. 第一层：从根节点开始，我们有两个选择：1 和 3。这是因为数组中有两个不同的数字。
  3. 第二层：
    • 选择 1 后，我们再次面临选择：1'（表示另一个 1）和 3。
    • 选择 3 后，我们只有选择 1 和 1'。
  4. 第三层：
    • 从 1 和 1'，我们可以得到排列 11'3 和 131'。
    • 从 3 和 1，我们可以得到排列 31 和 311'。
  5. 叶节点：这些叶节点表示完整的排列，如 11'3，131'，31，311'。

避免重复排列：

  • 在选择下一个数字时，我们使用了一个技巧来避免重复。例如，当我们已经选择了 1，我们不会再次选择 1，直到我们已经选择了 3。这样可以确保每个排列都是唯一的。
  • 在代码实现中，这通常通过在递归调用前检查当前数字是否已经被选择来实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class PermuteLeetcode47 {
 
    static List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        dfs(nums, new boolean[nums.length], new LinkedList<>(), result);
        return result;
    }
 
    static void dfs(int[] nums, boolean[] visited, LinkedList<Integer> stack, List<List<Integer>> result) {
        if (stack.size() == nums.length) {
            result.add(new ArrayList<>(stack));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i-1]) { // 找出重复数字
                continue;
            }
            if (!visited[i]) {
                stack.push(nums[i]);
                visited[i] = true;
                dfs(nums, visited, stack, result);
                visited[i] = false;
                stack.pop();
            }
        }
    }
 
    public static void main(String[] args) {
        int[] nums = {1, 1, 3};        
        List<List<Integer>> permute = permuteUnique(nums);
        for (List<Integer> list : permute) {
            System.out.println(list);
        }
    }
}

排好序，这样重复的数字会相邻

定好规则：必须 1 固定之后才能固定 1’，即 1 的 visited = true 才能继续处理 1’

在遍历时，遇到了 nums[i] == nums[i - 1]（即 1 和 1‘ 这种情况），进一步检查 i-1 位置的数字有没有 visited，没有，则不处理（剪枝）
也可以看我CSDN博客

原文链接：https://blog.csdn.net/2301_79602614/article/details/138347128

4) 组合-Leetcode 77

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

1
2
输入：n = 1, k = 1
输出：[[1]]

提示：

  • 1 <= n <= 20
  • 1 <= k <= n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>>result = new ArrayList<>();
        LinkedList<Integer>stack = new LinkedList<>();
        dfs(1,n,k,stack,result);
        return result;
    }
 
    public void dfs(int start,int n,int k,LinkedList<Integer>stack,List<List<Integer>>result){
        if(stack.size()==k){
            result.add(new ArrayList<>(stack));
            return;
        }
 
        for(int i = start;i<=n;i++){
            stack.push(i);
            dfs(i+1,n,k,stack,result);
            stack.pop();
            
        }
    }
}

dfs(i+1,n,k,stack,result); 如果改为：dfs(1,n,k,stack,result);

改为：dfs(i,n,k,stack,result); 情况都不同 可以自行体悟一下

减枝

如果缺的数字大于备用数字 那么就要剪枝剪掉

k- stack.length 还差几个能凑满

n - i +1 还剩下几个备用数字 if(k-stack.length >n-i+1) continue;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>>result = new ArrayList<>();
        LinkedList<Integer>stack = new LinkedList<>();
        dfs(1,n,k,stack,result);
        return result;
    }
 
    public void dfs(int start,int n,int k,LinkedList<Integer>stack,List<List<Integer>>result){
        if(stack.size()==k){
            result.add(new ArrayList<>(stack));
            return;
        }
 
        for(int i = start;i<=n;i++){
            if(k - stack.size() > n-i+1){
                continue;
            }
            stack.push(i);
            dfs(i+1,n,k,stack,result);
            stack.pop();
 
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class CombinationLeetcode77 {
    static List<List<Integer>> combinationSum(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(n, k, 1, new LinkedList<>(), result);
        return result;
    }
    static int count = 0;
 
    static void dfs(int n, int k, int start, LinkedList<Integer> stack, List<List<Integer>> result) {
        count++;
        if (k == 0) {
            result.add(new ArrayList<>(stack));
            System.out.println(stack);
            return;
        }
//      if (k > n - start + 1) { return; }
        for (int i = start; i <= n; i++) {
//            System.out.printf("k-1=%d n=%d i=%d %n", k - 1, n, i);
            if (k > n - i + 1) {
                continue;
            }
            stack.push(i);
            dfs(n, k - 1, i + 1, stack, result);
            stack.pop();
        }
    }
 
    public static void main(String[] args) {
        List<List<Integer>> lists = combinationSum(5, 4);
//        for (List<Integer> list : lists) {
//            System.out.println(list);
//        }
        System.out.println(count);
    }
}

k 代表剩余要组合的个数

n - i + 1 代表剩余可用数字

剪枝条件是：剩余可用数字要大于剩余组合数

为啥放在外面不行？即这行代码：if (k > n - start + 1) { return; }

因为它只考虑了 start 一种情况，而实际在循环内要处理的是 start，start+1 … n 这多种情况

似乎 ArrayList 作为 stack 性能高一些，见下面代码，但是这道题在 leetcode 上执行时间不稳定，相同代码都会有较大时间差异（15ms vs 9ms）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<Integer>> combine(int n, int k) {        
        List<List<Integer>> result = new ArrayList<>();
        if(k == 0 || n < k) return result;
        dfs(n, k, 1, new ArrayList<>(), result);
        return result;
    }
 
    static void dfs(int n, int k, int start, ArrayList<Integer> stack, List<List<Integer>> result) {
        if (k == 0) {
            result.add(new ArrayList<>(stack));
            return;
        }
        for (int i = start; i <= n; i++) {
            if (k-1 > n - i) {
                continue;
            }
            stack.add(i);
            dfs(n, k - 1, i + 1, stack, result);
            stack.remove(stack.size()-1);
        }
    }
}

5) 组合总和-Leetcode 39

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>>result = new ArrayList<>();
        LinkedList<Integer> stack= new LinkedList<>();
        dfs(0,candidates,target,stack,result);
        return result;
    }
 
    public void dfs(int start,int[] candidates,int target,LinkedList<Integer>stack,List<List<Integer>>result){
        if(target<0)
            return ;
        if(target==0){
            result.add(new ArrayList<>(stack));
            return;
        }
        for(int i = start;i<candidates.length;i++){
            int candidate = candidates[i];
            stack.push(candidate);
            dfs(i,candidates,target-candidate,stack,result);
            stack.pop();
        }
    }
}

与之前的零钱兑换问题其实是一样的，只是

  • 本题求的是：所有组合的具体信息
  • 零钱兑换问题求的是：所有组合中数字最少的、所有组合个数… [动态规划]

6) 组合总和 II-Leetcode 40

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

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

**注意：**解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class CombinationLeetcode40 {
    static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        dfs(target, 0, candidates, new boolean[candidates.length], new LinkedList<>(), result);
        return result;
    }
 
    static void dfs(int target, int start, int[] candidates, boolean[] visited, LinkedList<Integer> stack, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(stack));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            int candidate = candidates[i];
            if (target < candidate) {
                continue;
            }
            if (i > 0 && candidate == candidates[i - 1] && !visited[i - 1]) {
                continue;
            }
            visited[i] = true;
            stack.push(candidate);
            dfs(target - candidate, i + 1, candidates, visited, stack, result);
            stack.pop();
            visited[i] = false;
        }
    }
 
    public static void main(String[] args) {
        int[] candidates = {10, 1, 2, 7, 6, 1, 5};        
        List<List<Integer>> lists = combinationSum2(candidates, 8);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }
}

7) 组合总和 III-Leetcode 216

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

1
2
3
4
5
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

1
2
3
4
5
6
7
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

1
2
3
4
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

  • 2 <= k <= 9
  • 1 <= n <= 60
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public List<List<Integer>> combinationSum3(int k, int target ) {
        List<List<Integer>>result = new ArrayList<>();
        dfs(1,target,k,new ArrayList<>(),result);
        return result;
    }
    //static int count = 0;
    static void dfs(int start,int target,int k,ArrayList<Integer>stack,List<List<Integer>>result){
       // count++;
        if(target==0&&stack.size()==k){
            result.add(new ArrayList<>(stack));
            return;
        }
        for(int i = start;i<=9;i++){
            // 还差几个数字       剩余可用数字
          //  if(k-stack.size() > 9-i+1){
            //    continue;
            //} 这个减枝效率较低 设置一个count变量即可查看
            if(target<i){
                continue;
            
            }
            if(stack.size()==k){
                continue;
            }
            stack.addLast(i);
            dfs(i+1,target-i,k,stack,result);
            stack.removeLast();
        }
 
    }
}

8) N 皇后Leetcode 51

Eight queens 高斯认为有76种方案。实际上解有92种。

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

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

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

示例 1：

img

1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

1
2
输入：n = 1
输出：[["Q"]]

提示：

  • 1 <= n <= 9

左斜线处理i+j

右斜线i-j = n-1-（i-j）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class NQueenLeetcode51 {
    static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] table = new char[n][n];//'.' 'Q'
        boolean[] va = new boolean[n];//列冲突
        boolean[] vb = new boolean[2 * n - 1];//左斜线冲突
        boolean[] vc = new boolean[2 * n - 1];//右斜线冲突
        for (int i = 0; i < n; i++) {
            Arrays.fill(table[i], '.');
        }
        dfs(0, n, table, result, va, vb, vc);
        return result;
    }
 
    static void dfs(int i, int n, char[][] table, List<List<String>> result, boolean[] va, boolean[] vb, boolean[] vc) {
        if (i == n) {
            ArrayList<String> list = new ArrayList<>();
            for (char[] chars : table) {
                list.add(String.valueOf(chars));
            }
            result.add(list);
            return;
        }
        for (int j = 0; j < n; j++) {
            if (va[j] || vb[i + j] || vc[n - 1-(i-j)]) {
                continue;
            }
            va[j] = true;
            vb[i + j] = true;
            vc[n-1-(i-j)] = true;
            table[i][j] = 'Q';
            dfs(i + 1, n, table, result, va, vb, vc);
            table[i][j] = '.';
            va[j] = false;
            vb[i + j] = false;
            vc[i - j + n - 1] = false;
        }
    }
 
    public static void main(String[] args) {
        int count = 0;
        for (List<String> table : solveNQueens(4)) {
            for (String row : table) {
                System.out.println(row);
            }
            count++;
            System.out.println("--------------------- " + count);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class NQueenLeetcode51 {
    static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] table = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(table[i], '.');
        }
        dfs(0, n, table, result);
        return result;
    }
 
    static void dfs(int i, int n, char[][] table, List<List<String>> result) {
        if (i == n) {
            ArrayList<String> list = new ArrayList<>();
            for (char[] chars : table) {
                list.add(String.valueOf(chars));
            }
            result.add(list);
            return;
        }
        for (int j = 0; j < n; j++) {
            if (notValid(table, i, j)) {
                continue;
            }
            table[i][j] = 'Q';
            dfs(i + 1, n, table, result);
            table[i][j] = '.';
        }
    }
    /*
        .   .   .   .
        .   .   .   .
        .   ?   .   .
        .   .   .   .
     */
 
    static boolean notValid(char[][] table, int row, int col) {
        int n = table.length;
        for (int i = 0; i < n; i++) {
            if (table[i][col] == 'Q') { // 上
                return true;
            }
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (table[i][j] == 'Q') {
                return true;
            }
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (table[i][j] == 'Q') {
                return true;
            }
        }
        return false;
    }
 
    public static void main(String[] args) {
        int count = 0;
        for (List<String> table : solveNQueens(8)) {
            for (String row : table) {
                System.out.println(row);
            }
            count++;
            System.out.println("--------------------- " + count);
        }
    }
}

9) 解数独-Leetcode37

编写一个程序，通过填充空格来解决数独问题。

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

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

img

1
2
3
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 '.'
  • 题目数据 保证 输入数独仅有一个解

判断在那个九宫格 ==> i/3*3+j/3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public void solveSudoku(char[][] board) {
       /*
       1.不断遍历每个未填的空格
           逐一尝试1~9 若行,列,九宫格内没有冲突,则填入
       2.一旦1~9 都尝试失败,回溯到上一次状态,换数字填入
       3.关键还是要记录冲突状态
       */

       // 行冲突状态
       boolean[][] ca =new boolean[9][9];
       // ca[i] = {false,false,true,true,true,true...}
       // 列冲突状态
       boolean[][] cb = new boolean[9][9];
       // cb[j] = {false,true,true....}
       // 九宫格冲突状态
       //i/3*3+j/3 = ..在几号九宫格
       boolean[][] cc = new boolean[9][9];
       //cc[i/3*3+j/3] = {...}
       for(int i =0;i<9;i++){
           for(int j=0;j<9;j++){
               char ch = table[i][j];
               if(ch!='.'){//初始化冲突状态
                   ca[i][ch-'1']=true;     //'5'- '1' --> 4
                   cb[j][ch-'1']=true;
                   cc[i/3*3+j/3][ch-'1'] =true;

               }
           }
       }
       dfs(0,0,table,ca,cb,cc);

   }
   static boolean dfs(int i,int j,char[][] table,boolean[][] ca,boolean[][] cb,boolean[][] cc){
       while(table[i][j]!='.'){ //查找下一个空格
           if(++j>=9){
               j=0;
               i++;//到下一行
           }
           if(i>=9){
               return true; //找到解了
           }
       }
       //填空
       for(int x = 1;x<=9;x++){
           //检查冲突
           if(ca[i][x-1]||cb[j][x-1]||cc[i/3*3+j/3][x-1]){
               continue;
           }
           table[i][j] =(char)x+'0';   //1 -> '1'
           //ca[0][0] = true;  第0行不能存储'1'
           //cb[2][0] = true;  第2列不能存储'1'
           //cc[0][0] = true;  第0个九宫格不能存储'1'
           ca[i][x-1] = true;
           cb[j][x-1] = true;
           cc[i/3*3+j/3][x-1]=true;
           if(dfs(i,j,table,ca,cb,cc)){
               return true;
           }
           table[i][j] = '.';
           ca[i][x-1] = false;
           cb[j][x-1] = false;
           cc[i/3*3+j/3][x-1]=false;

       }
       return false;
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
public class SudokuLeetcode37 {
 
    static void solveSudoku(char[][] table) {
        int n = 9;
        boolean[][] va = new boolean[n][n];//行冲突
        boolean[][] vb = new boolean[n][n];//列冲突
        boolean[][][] vc = new boolean[3][3][n];//九宫格冲突
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (table[i][j] != '.') {
                    int x = table[i][j] - '0' - 1;
                    va[i][x] = true;
                    vb[j][x] = true;
                    vc[i / 3][j / 3][x] = true;
                }
            }
        }
        dfs(table, va, vb, vc, 0, 0);
    }
 
    static boolean dfs(char[][] table, boolean[][] va, boolean[][] vb, boolean[][][] vc, int i, int j) {
        while (table[i][j] != '.') {
            if (++j >= 9) {
                j = 0;
                i++;
            }
            if (i >= 9) {
                return true;
            }
        }
        int n = table.length;
        for (int d = 0; d < n; d++) {
            if (va[i][d] || vb[j][d] || vc[i / 3][j / 3][d]) {
                continue;
            }
            char ch = (char) (d + '0' + 1);
            table[i][j] = ch;
            va[i][d] = true;
            vb[j][d] = true;
            vc[i / 3][j / 3][d] = true;
            boolean dfs = dfs(table, va, vb, vc, i, j);
            if (dfs) {
                return true;
            }
            table[i][j] = '.';
            va[i][d] = false;
            vb[j][d] = false;
            vc[i / 3][j / 3][d] = false;
 
        }
        return false;
    }
 
    public static void main(String[] args) {
        char[][] table = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        solveSudoku(table);
 
        print(table);
    }
 
    static char[][] solved = {
            {'5', '3', '4', '6', '7', '8', '9', '1', '2'},
            {'6', '7', '2', '1', '9', '5', '3', '4', '8'},
            {'1', '9', '8', '3', '4', '2', '5', '6', '7'},
            {'8', '5', '9', '7', '6', '1', '4', '2', '3'},
            {'4', '2', '6', '8', '5', '3', '7', '9', '1'},
            {'7', '1', '3', '9', '2', '4', '8', '5', '6'},
            {'9', '6', '1', '5', '3', '7', '2', '8', '4'},
            {'2', '8', '7', '4', '1', '9', '6', '3', '5'},
            {'3', '4', '5', '2', '8', '6', '1', '7', '9'}
    };
 
    static void print(char[][] table) {
        for (char[] chars : table) {
            System.out.println(new String(chars));
        }
        System.out.println(Arrays.deepEquals(table, solved));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
public class SudokuLeetcode37 {
    record Pair(int i, int j) {
 
    }
 
    static void solveSudoku(char[][] table) {
        int n = 9;
        boolean[][] va = new boolean[n][n];
        boolean[][] vb = new boolean[n][n];
        boolean[][][] vc = new boolean[3][3][n];
        List<Pair> blanks = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (table[i][j] != '.') {
                    int x = table[i][j] - '0' - 1;
                    va[i][x] = true;
                    vb[j][x] = true;
                    vc[i / 3][j / 3][x] = true;
                } else {
                    blanks.add(new Pair(i, j));
                }
            }
        }
        dfs(0, blanks, table, va, vb, vc);
    }
 
    static boolean dfs(int p, List<Pair> blanks, char[][] table, boolean[][] va, boolean[][] vb, boolean[][][] vc) {
        if (p == blanks.size()) {
            print(table);
            return true;
        }
        int n = table.length;
        for (int d = 0; d < n; d++) {
            Pair pair = blanks.get(p);
            if (va[pair.i][d] || vb[pair.j][d] || vc[pair.i / 3][pair.j / 3][d]) {
                continue;
            }
            char ch = (char) (d + '0' + 1);
            table[pair.i][pair.j] = ch;
            va[pair.i][d] = true;
            vb[pair.j][d] = true;
            vc[pair.i / 3][pair.j / 3][d] = true;
            boolean dfs = dfs(p + 1, blanks, table, va, vb, vc);
            if (dfs) {
                return true;
            }
            table[pair.i][pair.j] = '.';
            va[pair.i][d] = false;
            vb[pair.j][d] = false;
            vc[pair.i / 3][pair.j / 3][d] = false;
 
        }
        return false;
    }
 
    public static void main(String[] args) {
        char[][] table = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
 
        solveSudoku(table);
 
        print(table);
    }
 
    static char[][] solved = {
            {'5', '3', '4', '6', '7', '8', '9', '1', '2'},
            {'6', '7', '2', '1', '9', '5', '3', '4', '8'},
            {'1', '9', '8', '3', '4', '2', '5', '6', '7'},
            {'8', '5', '9', '7', '6', '1', '4', '2', '3'},
            {'4', '2', '6', '8', '5', '3', '7', '9', '1'},
            {'7', '1', '3', '9', '2', '4', '8', '5', '6'},
            {'9', '6', '1', '5', '3', '7', '2', '8', '4'},
            {'2', '8', '7', '4', '1', '9', '6', '3', '5'},
            {'3', '4', '5', '2', '8', '6', '1', '7', '9'}
    };
 
    static void print(char[][] table) {
        for (char[] chars : table) {
            System.out.println(new String(chars));
        }
        System.out.println(Arrays.deepEquals(table, solved));
    }
}

10) 黄金矿工-Leetcode1219

1219. 黄金矿工 - 力扣（LeetCode）

你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。

为了使收益最大化，矿工需要按以下规则来开采黄金：

  • 每当矿工进入一个单元，就会收集该单元格中的所有黄金。
  • 矿工每次可以从当前位置向上下左右四个方向走。
  • 每个单元格只能被开采（进入）一次。
  • 不得开采（进入）黄金数目为 0 的单元格。
  • 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。

示例 1：

1
2
3
4
5
6
7
输入：grid = [[0,6,0],[5,8,7],[0,9,0]]
输出：24
解释：
[[0,6,0],
 [5,8,7],
 [0,9,0]]
一种收集最多黄金的路线是：9 -> 8 -> 7。

示例 2：

1
2
3
4
5
6
7
8
9
输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
输出：28
解释：
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
一种收集最多黄金的路线是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。

提示：

  • 1 <= grid.length, grid[i].length <= 15
  • 0 <= grid[i][j] <= 100
  • 最多 25 个单元格中有黄金。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    int[][] g;
    boolean[][] vis;
    int m,n;
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    public int getMaximumGold(int[][] grid) {
        g = grid;
        m = g.length;n = g[0].length;
        vis= new boolean[m][n];
        int ans = 0;
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(g[i][j]!=0){
                    vis[i][j] = true;
                    ans = Math.max(ans,dfs(i,j));
                    vis[i][j] = false;
                }
            }
        }
        return ans;
    }
 
    int dfs(int x,int y){
        int ans = g[x][y];
        for(int[] d:dirs){
            int nx = x+d[0],ny = y+d[1];
            if(nx<0||nx>=m||ny<0||ny>=n)continue;
            if(g[nx][ny]==0)continue;
            if(vis[nx][ny]) continue;
            vis[nx][ny] = true;
            ans = Math.max(ans,g[x][y] + dfs(nx,ny));
            vis[nx][ny] =false;
        }
        return ans;
    }
}

LeetCode 543

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

示例 1：

img

1
2
3
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

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

提示：

  • 树中节点数目在范围 [1, 104] 内
  • -100 <= Node.val <= 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int ans = 0;
 
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode u){
        if(u==null) return 0;
        int l = dfs(u.left),r=dfs(u.right);
        ans = Math.max(ans,l+r);
//返回最大深度
        return Math.max(l,r)+1;
    }
}

LeetCode433

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

  • 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

示例 1：

1
2
输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1

示例 2：

1
2
输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2

示例 3：

1
2
输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出：3

提示：

  • start.length == 8
  • end.length == 8
  • 0 <= bank.length <= 10
  • bank[i].length == 8
  • start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

这道题目是一个典型的最短路径问题，但是它在基因序列的背景下进行。题目要求我们找到从基因序列 start 变化到 end 的最少变化次数。这里的“变化”指的是基因序列中的一个字符发生了变化。题目中还提供了一个基因库 bank，只有基因库中的基因序列才是有效的，即变化后的基因序列必须出现在基因库中。

题目详解

  1. 基因序列：由8个字符组成，每个字符可以是 ‘A’、‘C’、‘G’ 或 ‘T’。
  2. 基因变化：指的是基因序列中的一个字符发生了变化，例如 “AACCGGTT” 变为 “AACCGGTA”。
  3. 基因库 bank：记录了所有有效的基因变化，只有出现在 bank 中的基因序列才是有效的。
  4. 目标：找到从 start 变化到 end 所需的最少变化次数。如果无法完成变化，返回 -1。
  5. 输入：
    • start：起始基因序列。
    • end：目标基因序列。
    • bank：有效的基因序列列表。
  6. 输出：最少变化次数，如果无法完成变化，则返回 -1。

示例解释

  • 示例 1：从 “AACCGGTT” 到 “AACCGGTA” 只需要一次变化，因为 “AACCGGTA” 在基因库中。
  • 示例 2：从 “AACCGGTT” 到 “AAACGGTA” 需要两次变化，可能的路径是 “AACCGGTT” → “AACCGCTA” → “AAACGGTA”，这两个中间基因序列都在基因库中。
  • 示例 3：从 “AAAAACCC” 到 “AACCCCCC” 需要三次变化，可能的路径是 “AAAAACCC” → “AAAACCCC” → “AAACCCCC” → “AACCCCCC”，这三个中间基因序列都在基因库中。

解题思路

题目中提供的代码使用了回溯法来解决这个问题。以下是代码的逻辑解释：

  1. 初始化：ans 用于存储最少变化次数，初始值为 Integer.MAX_VALUE。
  2. 递归函数 backtrack：
    • 参数 start：当前基因序列。
    • 参数 end：目标基因序列。
    • 参数 bank：基因库。
    • 参数 used：一个布尔数组，用于标记基因库中的哪些基因序列已经被使用过。
    • 参数 t：当前的变化次数。
  3. 递归终止条件：
    • 如果当前变化次数 t 已经大于等于 ans，则直接返回，因为不可能找到更短的路径。
    • 如果当前基因序列 start 等于目标基因序列 end，则更新 ans 为当前的最小变化次数。
  4. 递归搜索：
    • 遍历基因库 bank，对于每个基因序列，检查它是否与当前基因序列 start 只有一个字符不同（即变化次数为1）。
    • 如果找到这样的基因序列，标记为已使用，递归调用 backtrack 函数，尝试找到从这个基因序列变化到 end 的最少变化次数。
    • 递归完成后，取消标记（回溯），以便其他路径可以使用这个基因序列。
  5. 返回结果：
    • 如果 ans 仍然是 Integer.MAX_VALUE，说明无法从 start 变化到 end，返回 -1。
    • 否则，返回 ans。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    // 定义一个全局变量ans来存储从start到end的最少变化次数
    int ans = Integer.MAX_VALUE;
 
    // 主函数，接收起始基因序列start，目标基因序列end和基因库bank作为参数
    public int minMutation(String start, String end, String[] bank) {
        // 调用回溯函数，从start开始寻找到end的最少变化次数
        backtrack(start, end, bank, new boolean[bank.length], 0);
        // 如果ans仍然是初始值，说明没有找到从start到end的路径，返回-1
        // 否则返回找到的最少变化次数
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
 
    // 回溯函数，用于递归地寻找从start到end的最少变化次数
    public void backtrack(String start, String end, String[] bank, boolean[] used, int t) {
        // 如果当前的步数t已经大于等于已知的最少步数ans，则直接返回，避免重复计算
        if (t >= ans) return;
        // 如果当前的基因序列start已经等于目标基因序列end，更新ans为当前步数t
        if (start.equals(end)) {
            ans = Math.min(ans, t);
        } else {
            // 遍历基因库bank中的每一个基因序列
            for (int i = 0, diff = 0; i < bank.length; i++, diff = 0) {
                // 如果当前基因序列已经被使用过，则跳过
                if (used[i]) continue;
                // 计算当前基因序列与start的差异，如果差异为1，则表示可以通过一次变化从start变为当前基因序列
                for (int j = 0; j < start.length(); j++) 
                    diff += start.charAt(j) != bank[i].charAt(j) ? 1 : 0;
                // 如果差异为1，表示可以通过一次变化从start变为当前基因序列
                if (diff == 1) {
                    // 标记当前基因序列为已使用
                    used[i] = true;
                    // 递归调用回溯函数，尝试从当前基因序列变化到end
                    backtrack(bank[i], end, bank, used, t + 1);
                    // 回溯，取消当前基因序列的已使用标记，以便其他路径可以使用
                    used[i] = false;
                }
            }
        }
    }
}

代码解释

  1. diff 的作用：
    • diff 用于计算当前基因序列 start 和基因库中的某个基因序列 bank[i] 之间的差异。
    • 具体来说，diff 计算的是两个序列中对应位置上不同字符的个数。
    • 如果 diff 等于 1，表示两个序列之间只有一个字符不同，即可以通过一次变化从 start 变为 bank[i]。
  2. bank 的使用：
    • bank 是一个数组，包含了所有有效的基因序列。
    • 在回溯过程中，我们遍历 bank 中的每个基因序列，检查它是否可以作为从 start 到 end 的一个中间步骤。
    • 只有当 bank[i] 与 start 的差异为 1 时，bank[i] 才会被考虑作为下一步。

举例说明

假设我们有以下输入：

  • start = "AACCGGTT"
  • end = "AAACGGTA"
  • bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

步骤 1：初始化

  • ans = Integer.MAX_VALUE（初始的最少变化次数设为最大整数值）

步骤 2：第一次调用 backtrack

  • backtrack("AACCGGTT", "AAACGGTA", bank, new boolean[bank.length], 0)

步骤 3：遍历 bank

  • 计算 start 和每个 bank[i] 的差异 diff：
    • diff("AACCGGTT", "AACCGGTA") = 2（两个字符不同）
    • diff("AACCGGTT", "AACCGCTA") = 1（一个字符不同）
    • diff("AACCGGTT", "AAACGGTA") = 2（两个字符不同）
  • 只有 "AACCGCTA" 的 diff 为 1，因此我们选择它作为下一步。

步骤 4：递归调用 backtrack

  • used[1] = true（标记 “AACCGCTA” 为已使用）
  • backtrack("AACCGCTA", "AAACGGTA", bank, used, 1)

步骤 5：再次遍历 bank

  • 计算 "AACCGCTA" 和每个 bank[i] 的差异 diff：
    • diff("AACCGCTA", "AACCGGTA") = 2
    • diff("AACCGCTA", "AAACGGTA") = 1
  • 只有 "AAACGGTA" 的 diff 为 1，因此我们选择它作为下一步。

步骤 6：再次递归调用 backtrack

  • used[2] = true（标记 “AAACGGTA” 为已使用）
  • backtrack("AAACGGTA", "AAACGGTA", bank, used, 2)

步骤 7：达到目标

  • start.equals(end) 为 true，更新 ans = 2

步骤 8：回溯

  • 取消标记 used[2] = false，used[1] = false
  • 返回到上一级递归

最终，我们找到了从 "AACCGGTT" 到 "AAACGGTA" 的最少变化次数为 2。

总结

通过这个例子，我们可以看到 diff 是如何计算两个序列之间的差异，并且 bank 是如何被用来找到有效的中间步骤。代码通过递归和回溯，尝试所有可能的路径，直到找到最短的路径或确定不存在这样的路径。