题目链接：36.有效的数独

题解：

数独游戏的到来，这道题判断是否有解，下一道题咱们来填数独！

题目简述：

给定一个9 X 9 的数独，判断当前状态是否有解！

题解：

判断是否有解，即判断行和列以及九个小九宫格是否会出现一个数多用的情况即可！

  • 判断行：直接遍历即可，每行进行一下数组清零
  • 判断列：将i, j调换一下即可！每列进行一下数组清零
  • 判断九宫格：可以使用i, j指向每个九宫格的第一个位置代表不同的九宫格，即i, j += 3
    • 然后再在个九宫格中使用两层循环遍历九个格子即可，每个九宫格进行数组清零，指向的位置即为i + x, j + y
  • 使用过直接返回false，全部遍历完都没问题，则返回true

注意：要将数独中的字符转变为数字进行！转换为了1 - 9

AC代码：

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 {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool s[10];
        for(int i = 0; i < 9; i ++){
            memset(s, 0, sizeof s);
            for(int j = 0; j < 9; j ++){
                if(board[i][j] != '.'){
                    int t = board[i][j] - '0';
                    if(s[t]) return false;
                    s[t] = true;
                }
            }
        }
        for(int i = 0; i < 9; i ++){
            memset(s, 0, sizeof s);
            for(int j = 0; j < 9; j ++){
                if(board[j][i] != '.'){
                    int t = board[j][i] - '0';
                    if(s[t]) return false;
                    s[t] = true;
                }
            }
        }
        for(int i = 0; i < 9; i += 3){
            for(int j = 0; j < 9; j += 3){
                memset(s, 0, sizeof s);
                for(int x = 0; x < 3; x ++){
                    for(int y = 0; y < 3; y ++){
                        if(board[i + x][j + y] != '.'){
                            int t = board[i + x][j + y] - '0';
                            if(s[t]) return false;
                            s[t] = true;
                        }
                    }
                }
            }
        }
        return true;
    }
};