经典题

# 36. 有效的数独 (opens new window)

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] cols = new int[9][9];
        int[][][] sub = new int[3][3][9];
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                char c = board[i][j];
                if(c!='.'){
                    int idx = c-'0'-1;
                    rows[i][idx]++;
                    cols[j][idx]++;
                    sub[i/3][j/3][idx]++;
                    if(rows[i][idx]>1 || cols[j][idx]>1 || sub[i/3][j/3][idx]>1){
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 37. 解数独 (opens new window)

class Solution {
    boolean[][] rows = new boolean[9][9];
    boolean[][] cols = new boolean[9][9];
    boolean[][][] sub = new boolean[3][3][9];
    boolean isValid = false;
    List<int[]> spaces = new ArrayList<>();
    public void solveSudoku(char[][] board) {
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                char c = board[i][j];
                if(c=='.'){
                    spaces.add(new int[]{i,j});
                }else{
                    int idx = c-'0'-1;
                    rows[i][idx] = cols[j][idx] = sub[i/3][j/3][idx] = true;
                }
            }
        }
        dfs(board,0);
    }
    void dfs(char[][] board,int pos){
        if(pos == spaces.size()){
            isValid = true;
            return ;
        }
        int[] space = spaces.get(pos);
        int i = space[0];
        int j = space[1];
        for(int k=0;k<9&&!isValid;k++){
            if(!rows[i][k] && !cols[j][k] && !sub[i/3][j/3][k]){
                rows[i][k] = cols[j][k] = sub[i/3][j/3][k] = true;
                board[i][j] = (char)(k+'0'+1);
                dfs(board,pos+1);
                rows[i][k] = cols[j][k] = sub[i/3][j/3][k] = 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

# 51. N 皇后 (opens new window)

class Solution {
    int[] cols;
    int n;
    List<List<String>> ret = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        this.cols = new int[n];
        dfs(0);
        return ret;
    }
    void dfs(int i){
        if(i==n){
            List<String> item = new ArrayList<>();
            for(int col:cols){
                char[] row = new char[n];
                Arrays.fill(row,'.');
                row[col] = 'Q';
                item.add(new String(row));
            }
            ret.add(item);
            return ;
        }
        for(int j=0;j<cols.length;j++){
            if(f(i,j)){
                cols[i] = j;
                dfs(i+1);
            }
        }
    }
    boolean f(int r,int c){
        for(int i=0;i<r;i++){
            int j=cols[i];
            if(c==j || (i+j)==(r+c) || (i-j)==(r-c)){
                return false;
            }
        }
        return true;
    }
}

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

# 52. N 皇后 II (opens new window)

← 树回溯遍历dfs→