刷题笔记7-暴力搜索

DFS/回溯算法

回溯的核心思想在于：

  • 做出选择
  • （DFS递归）
  • 撤销选择

但是面对不同的题目：做什么选择，在哪做选择都是需要考虑的问题。

大致的框架

1
2
3
4
5
6
7
8
9
10
结果集 = []
def backtrace(路径, 选择列表):
    if 满足结束的条件:
        结果集.add(路径)
        return
    
    for 选择 in 选择列表:
        做出选择
        backtrace(路径, 选择列表)
        撤销选择

例子

【全排列】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
List<List<Integer>> res;

public List<List<Integer>> permute(int[] nums) {
    res = new ArrayList<>();
    
    List<Integer> path = new ArrayList<>();
    backtrace(nums, path);
}


void backtrace(int[] nums, List<Integer> path){
    // 结束条件
    if(path.size() == nums.length){
        res.add(new ArrayList<>(path));
        return;
    }
    
    for(int i = 0; i < nums.length; i++){
        if(path.contains(nums[i])) continue; // 筛除不在选择列表中的元素
        path.add(nums[i]); // 做出选择
        backtrace(nums, path);
        path.remove(new Integer(nums[i])); // 撤销x
    }
}

【N皇后】

在 n\(\times\)n 的棋盘上放置 n 个皇后，使得 n 个皇后不能相互攻击

1
2
3
public List<List<String>> solveNQueens(int n){
    List<Integer> board = new ArrayList<>();
}

子集划分

给定一个数组nums和一个正整数k，返回其是否能被分成k个子集，且每个子集的元素和相同

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
class Solution {
    // 1. 以数字的视角：每一个数都是去k个桶中的一个桶
    // O(k^n)
    // 会超时!
    public boolean canPartitionKSubsets2(int[] nums, int k) {
        // 去掉一些特殊情况
        if(k > nums.length) return false;
        int sum = 0;
        for(int i : nums) sum += i;
        if(sum % k != 0) return false;

        int sub_sum = sum / k;
        int[] buckets = new int[k];
		
        
        // 给数组按降序排列，使得回溯的剪枝尽早发生
        Arrays.sort(nums);
        int i = 0, j = nums.length - 1;
        for(; i < j; i++, j--){
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }

        return backtrace(nums, 0, sub_sum, buckets);
    }

    private boolean backtrace(int[] nums, int index, int target, int[] buckets){
        if(index == nums.length){
            for(int i = 0; i < buckets.length; i++){
                if(buckets[i] != target) return false;
            }
            return true;
        }

        for(int i = 0; i < buckets.length; i++){
            if(buckets[i] + nums[index] > target) continue;
            buckets[i] += nums[index];
            // 向后继续走
            if( backtrace(nums, index + 1, target, buckets) ){
                return true;
            }
            // 后面的某个情况不满足条件，需要回溯
            buckets[i] -= nums[index];
        }

        return false;
    }
    /*
    回溯：不能没有尝试完就做决定，没做一次决定都要向后继续走，只有最后能走通，才算是正确的选择
    */

    // 2.以桶的视角：每个桶都要遍历所有元素
    // O(k*2^n)
    public boolean canPartitionKSubsets1(int[] nums, int k) {
        // 去掉一些特殊情况
        if(k > nums.length) return false;
        int sum = 0;
        for(int i : nums) sum += i;
        if(sum % k != 0) return false;

        int sub_sum = sum / k;
        int[] buckets = new int[k];

        visited = new boolean[nums.length];

        return backtrace(nums, 0, 0, buckets, sub_sum);
    }

    boolean[] visited;
    private boolean backtrace(int[] nums, int start, int index, int[] buckets, int target){
        if(index == buckets.length){
            return true;
        }

        if(buckets[index] == target) {
            return backtrace(nums, 0, index + 1, buckets, target);
        }

        for(int i = start; i < nums.length; i++){
            if(visited[i] || buckets[index] + nums[i] > target) continue;
            buckets[index] += nums[i];
            visited[i] = true;
            // 向后继续走
            if( backtrace(nums, i + 1, index, buckets, target) ){
                return true;
            }
            // 回溯
            visited[i] = false;
            buckets[index] -= nums[i];
        }

        return false;

    }

    // 3.状态数组+递归
    // 重点理解三个点:
    // 1. 为什么在刚进入dfs时就把 dp[s]设为false !!!
    // 2. 为什么 nums[i] + p > per 后就 break 返回 fasle
    // 3. 为什么 递归的dfs p = (nums[i] + p) % per

    int[] nums;
    int per, n;
    boolean[] dp;

    public boolean canPartitionKSubsets(int[] nums, int k) {
        this.nums = nums;
        int all = Arrays.stream(nums).sum();
        if (all % k != 0) {
            return false;
        }
        per = all / k;
        Arrays.sort(nums);
        n = nums.length;
        if (nums[n - 1] > per) {
            return false;
        }

        dp = new boolean[1 << n];
        Arrays.fill(dp, true);
        return dfs((1 << n) - 1, 0);
    }

    public boolean dfs(int s, int p) {
        if (s == 0) {
            return true;
        }
        if (!dp[s]) {
            return dp[s];
        }
        // 避免重复执行相同情况
        dp[s] = false; // dp[s] 到底代表了什么?
                       // s代表的是还有哪些位置的元素是可用的,dp[s]是代表在这种情况下的可行性? 为什么在一开始就把这种情况作为不可行.
                       // 如果这种某种情况可行的话,那么是不会再次被碰到的,会直接返回到主函数中
                       // 相反如果这种情况被再次碰到,那么上一次碰到这种情况的时候肯定是不可行,即false
                       // 下一次碰到的时候,尽管s是相同,p也相同吗? 是的
                       // 从p是如何迭代的可以看出,由于s是相同的,所以用掉的nums[i]是一样的,而p是用掉的nums[i]相加后模per得到的,所以当s是相同的时候,p也是相同的.
        for (int i = 0; i < n; i++) {
            // 因为nums是被排序过的，所有前面的要是加起来 > per 后面肯定也会 提前剪枝
            if (nums[i] + p > per) {
                break;
            }
            if (((s >> i) & 1) != 0) {
                // (p + nums[i]) % per 是为了重置当前的子集的值
                // 即当 p + nums[i] == per 后，重置为0
                if (dfs(s ^ (1 << i), (p + nums[i]) % per)) {
                    return true;
                }
            }
        }
        return false;
    }
}

回溯很重要的一个点：不能没有考虑后面情况就定死了前面的选择。回溯的本质在于先不断地做决定，如果成功那么之前的选择就是正确的并返回，如果出错了，在不断地撤回决定并且重新做决定

总结

总结回溯算法在子集、组合和排列三类问题上的处理

对于子集、组合和排列这三类问题，可以按照元素是是否可重、是否可复选两方面来划分。

子集问题和排列问题本质其实是同属一类问题，都是对顺序没有要求的选取部分序列...所以就将他们归类为一种问题

1、集合/组合问题

  1. 集合/组合问题是不存在顺序的，所以每次backtrace的过程中，不能都从下标0开始选择元素，所以每次进入backtrace时都应该指明下次从哪开始选。
  2. 集合/组合问题的要求主要有两种：1、选出指定元素个数的组合（即包含指定数量元素的子集）2、选出元素和等于指定值的组合
1.1、元素无重+不可复选

子集问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
List<List<Integer>> ans;
public List<List<Integer>> subsets(int[] nums) {
    ans = new ArrayList<>();
    List<Integer> node = new ArrayList<>();
    backtrace(nums, 0, node);
    return ans;
}

private void backtrace(int[] nums, int start, List<Integer> node){
	// 如果要返回指定数量元素的子集，在这里微调即可
    ans.add(new ArrayList<>(node));

    for(int i = start; i < nums.length; i++){
        node.add(nums[i]);
        backtrace(nums, i + 1, node);
        node.remove(new Integer(nums[i]));
    }
}
1.2、元素可重+不可复选

包含重复元素的集合，选出子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
List<List<Integer>> ans;
public List<List<Integer>> subsets(int[] nums) {
    ans = new ArrayList<>();
    List<Integer> node = new ArrayList<>();
    Arrays.sort(nums);
    backtrace(nums, 0, node);
    return ans;
}

private void backtrace(int[] nums, int start, List<Integer> node){

    ans.add(new ArrayList<>(node));

    for(int i = start; i < nums.length; i++){
        // 剪枝 如果当前元素和前一个相同 就跳过
        if( i > start && nums[i] == nums[i - 1] ) continue;
        node.add(nums[i]);
        backtrace(nums, i + 1, node);
        node.remove(new Integer(nums[i]));
    }
}
1.3、元素无重+可重复选

nums数组，指定 target，返回所有满足 元素和等于 target 的子序列

可以重复使用元素

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 {
    List<List<Integer>> res;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res = new ArrayList<>();
        List<Integer> one = new ArrayList<>();
        Arrays.sort(candidates);
        backtrace(candidates, 0, one, target, 0);
        return res;
    }

    /*
    	nums: 		元素集合
    	start: 		开始位置
    	one: 		子序列
    	target: 	目标值
    	cur_sum: 	当前元素和
    */
    private void backtrace(int[] nums, int start, List<Integer> one, int target, int cur_sum){
        if(cur_sum == target){
            res.add(new ArrayList<>(one));
            return;
        }

        for(int i = start; i < nums.length; i++){
            if(cur_sum + nums[i] > target) break;
            one.add(nums[i]);
            // 从 i 开始向后走，保证可以重复使用元素...
            backtrace(nums, i, one, target, cur_sum + nums[i]);
            one.remove(new Integer(nums[i]));
        }
    }
}

2、排列问题

排列问题一般不存在对子序列元素和的要求，所以框架上略有不同

  • 元素无重+不可复选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
List<List<Integer>> res;
public List<List<Integer>> solve(...){
    res = new ArrayList<>();
    List<Integer> one = new ArrayList<>();
    backtrace(nums, one);
    return res;
}
private void backtrace(int[] nums, List<Integer> one){
    // 结束条件: 包含了所有元素
    if(one.size() == nums.length){
        res.add(new ArrayList<>(one));
        return;
    }
    
    for(int i = 0; i < nums.length; i++){
        if( one.contains(nums[i]) ) continue; // 排除被选中的元素
        one.add(nums[i]);
        backtrace(nums, one);
        one.remove(new Integer(nums[i]));
    }
}
  • 元素有重+不可复选
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
// 需要排除一些情况
List<List<Integer>> res;
boolean[] visited;
public List<List<Integer>> solve(...){
    res = new ArrayList<>();
    List<Integer> one = new ArrayList<>();
    visited = new boolean[nums.length];
    backtrace(nums, one);
    return res;
}
private void backtrace(int[] nums, List<Integer> one){
    // 结束条件: 包含了所有元素
    if(one.size() == nums.length){
        res.add(new ArrayList<>(one));
        return;
    }
    
    for(int i = 0; i < nums.length; i++){
        /* 剪枝: 当前元素和前一个元素相同 且 前一个还没有遍历到的话 就跳过
        	因为这个情况在前一个元素遍历时已经经历了
        	例如: [1,2,1] 遍历第一个 1 的时候就已经 遍历出了 [1,1,2] 和 [1,2,1] 了
        	遍历到第二个 1 就可以跳过了
        */
        if( i > 0 && nums[i] == nums[i-1] && !visited[i-1] ) continue;
        if( visited[i] ) continue; // 排除被选中的元素
        visited[i] = true;
        one.add(nums[i]);
        backtrace(nums, one);
        visited[i] = false;
        //one.remove(new Integer(nums[i])); // remove(Object o) 是移除第一个出现的这个元素
        one.remove(one.size() - 1); // 使用下标移除
    }
}

岛屿问题

1、岛屿数量

200. 岛屿数量 - 力扣（LeetCode）

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
class Solution {
    public int numIslands(char[][] grid) {
        int cnt = 0;
        int m = grid.length; int n = grid[0].length;
        
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '0') continue;
                dfs(grid, i, j);
                cnt++;
            }
        }
        
        return cnt;
    }

    private void dfs(char[][] grid, int i, int j){
        int m = grid.length; int n = grid[0].length;
        /* 这种越界判断跟简洁 */
        if(i < 0 || i >= m || j < 0 || j >= n) return; // 越界返回
        if(grid[i][j] == '0') return;
        
        grid[i][j] = '0';
        
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    } 
}

2、封闭岛屿数量

封闭岛屿就是完全（上、下、左、右）被水包围的陆地

其实 封闭岛屿数量 = 200.岛屿数量 - 靠边岛屿数量

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
class Solution {
    // 把200.岛屿数量中求出来的岛屿数减去靠边的岛屿数就是本题结果
    public int closedIsland(int[][] grid) {
        int m = grid.length; int n = grid[0].length;
        // Attention: 得先将上下左右边上的岛屿给淹掉
        for(int j = 0; j < n; j++){
            if(grid[0][j] == 0) dfs(grid, 0, j);
            if(grid[m-1][j] == 0) dfs(grid, m-1, j);
        }
        for(int i = 0; i < m; i++){
            if(grid[i][0] == 0) dfs(grid, i, 0);
            if(grid[i][n-1] == 0) dfs(grid, i, n-1);
        }
        int cnt = 0;
        // 如果在这个主循环里排除靠边的岛屿的话，会出现错误
        // 因为存在遍历次序 中间的0 肯定比 最下面那条边的0 更早被遍历
        // 如果中间的0和下面那条边的0是相连通的，这个岛屿就是靠边岛屿
        // 但是这个岛屿会被算进答案中
        /**
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j ++){
                if(grid[i][j] == 1) continue;
                if(i == 0 || i == m - 1 || j == 0 || j == n - 1){
                    dfs(grid, i, j);
                } else {
                    dfs(grid, i, j);
                    cnt++;
                }
            }
        }
         */
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j ++){
                if(grid[i][j] == 1) continue;
                dfs(grid, i, j);
                cnt++;
            }
        }
        return cnt;
    }


    private void dfs(int[][] grid, int i, int j){
        int m = grid.length; int n = grid[0].length;
        if(i < 0 || i >= m || j < 0 || j >= n) return;
        if(grid[i][j] == 1) return;

        grid[i][j] = 1;

        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);

    }
}

3、统计子岛屿

1905. 统计子岛屿 - 力扣（LeetCode）

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 int countSubIslands(int[][] grid1, int[][] grid2) {
    int m = grid1.length; int n = grid1[0].length;
    
    // 先淹掉grid2中不是子岛屿的部分
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(grid1[i][j] == 0 && grid2[i][j] == 1){
                dfs(grid2, i, j);
            }
        }
    }
	
    // 统计子岛屿
    int cnt = 0;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(grid2[i][j] == 1){
                dfs(grid2, i, j);
                cnt++;
            }
        }
    }
    return cnt;
}

private void dfs(int[][] grid, int i, int j){
    int m = grid.length; int n = grid[0].length;
    if(i < 0 || i >= m || j < 0 || j >= n) return;
    if(grid[i][j] == 0) return;

    grid[i][j] = 0;

    dfs(grid, i-1, j);
    dfs(grid, i+1, j);
    dfs(grid, i, j-1);
    dfs(grid, i, j+1);
}

4、不同岛屿的数量

统计不同形状的岛屿数量

这就要求在dfs遍历的过程中用某种方法记录岛屿的形状：在dfs过程中用字符进行拼接形成字符串

由于dfs的顺序是一样的、固定的，所以如果岛屿形状相同，开始dfs的位置肯定是一样的，最后形成的字符串也是一样的，再通过HashMap记录即可。

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 int numDistinctIslands(int[][] grid) {
    int m = grid.length; int n = grid[0].length;

    Map<String, Integer> mapping = new HashMap<>();
    
    for (int i = 0; i < m; i ++){
        for (int j = 0; j < n; j++){
            if(grid[i][j] == 1){
                
                String shape = dfs(grid, i, j);
                System.out.println("(" + i + ", " + j + ")" + ": " + shape);
                
                if (!mapping.containsKey(shape)){
                    mapping.put(shape, 1);
                }
            }
        }
    }

    return mapping.size();
}


private String dfs(int[][] grid, int i, int j){
    int m = grid.length; int n = grid[0].length;
    // 非陆地的统一用'0'表示
    if(i < 0 || i >= m || j < 0 || j >= n) return "0";
    if (grid[i][j] == 0) return "0";

    grid[i][j] = 0;

    return "1"  +  dfs(grid, i - 1, j) +
                   dfs(grid, i + 1, j) +
                   dfs(grid, i, j - 1) +
                   dfs(grid, i, j + 1);
}

BFS算法

BFS算法是广度优先，遍历过程中，从开始节点到（第一次到）任一节点的的距离都是最小的

优点：BFS算法的普适性强，可以适用于所有情况

缺点：效率低，BFS的遍历由一个点等距离的向四周扩散

image-20221029210656103 
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
void bfs(Node root, Node target){
    // 队列: BFS遍历必备
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    // 记录已经走过的节点
    Set<Node> visited = new HashSet<>();
    visited.add(root);
    
    int step = 0; // 记录已走的步数
    
    while(!queue.isEmpty()){
        int size = queue.size();
        for(int i = 0; i < size; i++){
            Node cur = queue.poll();
            
            if(cur is target) return step;
            
            for(Node n : graph[n]){
                if(!visited.contains(n)){
                    queue.offer(n);
                    visited.add(n);
                }
            }
        }
        step ++;
    }
    
    return -1;
}

Dijkstra算法

Dijkstra算法就是在BFS算法上的一个改进，针对有权重的图，主要的区别就在于存放节点的数据结构从普通的队列（Queue）变成了优先级队列（PriorityQueue），而使用优先级队列就可以按照代价（这个代价是从开始节点到当前节点的代价，所以Dijkstra算法是可以求出开始节点到所有节点的最小距离的）对节点进行排序，使得每次取出的节点都是代价最小的，从而实现第一次到某节点时的代价就是最小的。

这个算法和Dijktra算法类似，但是这里所选取的代价是当前节点到target节点的理论代价。所以这个算法可以基本可以十分快速求出到达target节点的最小代价，特殊情况就是图中存在障碍物的情形，由于所用的代价是理论上的，并不是实际情况，所以会导致"走错路"的情况。

A*算法

Introduction to A*

A*算法有效地结合了Dijkstra算法和Greedy Best-First Search算法，综合了两方面的代价，使得既拥有了上述两个算法的优势。

代码框架

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
public Solution{

    class AStar{
        /*
            f: 综合代价 f = g + h
            g: 开始节点到当前节点的代价
            h: 当前节点到target节点的理论代价
        */
        int f, g, h; 
        Node cur; // 标识当前节点

        public AStar(Node cur, int g, Node target){
            this.cur = cur;
            this.h = getH(cur, target);
            this.g = g;
            this.f = this.g + this.h;
        }

        // 计算 h 值
        public int getH(Node cur, Node target){

        }
    }
    
    public int solve(Node start, Node target){
        Queue<AStar> queue = new PriorityQueue<>((a, b) -> {
            return a.f - b.f;
        });
        queue.offer(new AStar(start, 0, target));
        
        Set<Node> visited = new HashSet<>();
        visited.add(start);
        
        while(!queue.isEmpty()){
            AStar node = queue.poll();
            
            for(Node n : graph[node.cur]){
                if(!visited.contains(n)){
                    if(n == target){
                        return node.g + 1;
                    }
                    queue.offer(new AStar(n, node.g + 1, target));
                    visited(n);
                }
            }
        }
        
        return -1;
        
    }
    
    
}


应用

【773.滑动谜题】

773. 滑动谜题 - 力扣（LeetCode）

关键在于如何建模形成 graph 以及 node 是什么

在这道题中，就可以把\(2 \times 3\)的矩阵抽象成String作为节点，而每次移动之后形成的节点作为该节点的邻居，这样就形成了graph

leetcode刷题笔记
#leetcode
刷题笔记7-暴力搜索
http://example.com/2022/11/18/leetcode/刷题笔记7（暴力搜索）/
作者
zhc
发布于
2022年11月18日
许可协议