Problem: 1971. 寻找图中是否存在路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    int[] pa;
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        pa = new int[n];
        Arrays.setAll(pa, i -> i);
        for (int[] e : edges) {
           pa[find(e[0])] = find(e[1]);
        }
        return find(source) == find(destination);
    }
    private int find(int a) {
        return (pa[a] == a) ? a : (pa[a] = find(pa[a]));
    }
}

37解数独

Problem: 37. 解数独

思路:

利用row[i][val]表示第i行有没有val出现。

利用col[j][val]表示第j列有没有val出现。

利用block[i / 3][j / 3][val]表示第（i/3,j/3）个九宫格有没有val出现。

利用empCells存储尚未被填充的点。

首先取出empCells中的第一个点，digital从0~9填充，如果digital不在行，列，其所在九宫格中存在，则遍历下一个未被填充的点。直到填充结束。

注意点:

1、在digital遍历的时候，需要加上 !valid 条件。也就是(int digital = 0; digital < 9 && !valid; digital ++)。为什么？

因为如果不加这个条件，假设找到数独的解时，整个dfs还未完成。就要进行回溯，回溯的时候会将先前已经遍历过的digital设置为false。这样的话，当回溯到某个点时，该点的digital从k~9遍历（k是未被遍历过的第一个数字），而恰好在之前回溯过程中，k被设置为false，k在该点的行，列，所在九宫格中均为出现，那么k就会覆盖之前的解中的board[i][j]，使得解出错。

举个例子，如下图。dfs在最后的红色1处找到解。此时进行回溯。它一定会回溯到蓝色的1处。这时，由于1下方的7和有方的7都已经被释放了。那么这个时候蓝色的1处就可以填充7，然后接着遍历。就会覆盖正确解的数值。因为board[i][j]在回溯的时候，我们并没有进行对board[i][j]恢复现场。我们仅仅采用了覆盖之前值的方式来回溯。

img

2、不能使用队列来存储未被确定的点。因为频繁的出队、入队，相当耗时。

是的，自己看图吧。说多了都是泪。

img

img

Code

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
class Solution {
    private boolean[][] row = new boolean[9][9];
    private boolean[][] col = new boolean[9][9];
    private boolean[][][] block = new boolean[3][3][9];
    List<int[]> empCells = new ArrayList<int[]>(); 
    boolean valid;

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i ++) {
            for (int j = 0; j < 9; j ++) {
                if (board[i][j] == '.') {
                    empCells.add(new int[]{i, j});
                } else {
                    int digital = board[i][j] - '1';
                    row[i][digital] = col[j][digital] = block[i / 3][j / 3][digital] = true; 
                }
            }
        }
        dfs(board, 0);
    }

    private void dfs(char[][] board,int index) {
        if (index == empCells.size()) {
            valid = true;
            return ;
        }
        int[] e = empCells.get(index);
        int x = e[0], y = e[1];
        for (int i = 0; i < 9 && !valid; i ++) { //已经找到解，就不再遍历了，不然会覆盖掉解
            if (!row[x][i] && !col[y][i] && !block[x / 3][y / 3][i]) {
                row[x][i] = col[y][i] = block[x / 3][y / 3][i] = true;
                board[x][y] = (char) ('1' + i);
                dfs(board, index + 1);
                row[x][i] = col[y][i] = block[x / 3][y / 3][i] = false; 
            }
        }
    }
}