36. 有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

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

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 '.' 表示。

示例 1：

输入：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"]]
输出：true

示例 2：

输入：board = 
[["8","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"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字（1-9）或者 '.'

方法一：采用hash表存储每行/每列/每个3*3宫格的数字与出现的次数的映射关系

 1 class Solution {
 2 public:
 3     // 校验每行数字是否满足条件
 4     bool isRowValid(int row, const vector<vector<char>> &board) {
 5         if (board.size() != 9 || board[0].size() != 9) {
 6             return false;
 7         }
 8         unordered_map<char, int> hashMap; // key->数字,value->数字出现的次数
 9         hashMap.clear();
10         for (unsigned int j = 0; j < board[0].size(); j++) {
11             if (board[row][j] == '.') {
12                 continue;
13             }
14             if (hashMap.count(board[row][j]) == 0) { // 数字没出现过就加入hash表
15                 hashMap[board[row][j]]++;
16             } else { // 即将加入的数字之前出现过,不满足条件,直接返回false
17                 return false;
18             }
19         }
20         return true;
21     }
22     // 校验每列数字是否满足条件
23     bool isColValid(int col, const vector<vector<char>> &board) {
24         if (board.size() != 9 || board[0].size() != 9) {
25             return false;
26         }
27         unordered_map<char, int> hashMap; // key->数字,value->数字出现的次数
28         hashMap.clear();
29         for (unsigned int i = 0; i < board.size(); i++) {
30             if (board[i][col] == '.') {
31                 continue;
32             }
33             if (hashMap.count(board[i][col]) == 0) { // 数字没出现过就加入hash表
34                 hashMap[board[i][col]]++;
35             } else { // 即将加入的数字之前出现过,不满足条件,直接返回false
36                 return false;
37             }
38         }
39         return true;
40     }
41     // 校验每个3*3宫格内数字是否满足条件(row和col分别是3的倍数)
42     bool isThreeGongGeValid(int row, int col, const vector<vector<char>> &board) {
43         if (board.size() != 9 || board[0].size() != 9) {
44             return false;
45         }
46         unordered_map<char, int> hashMap; // key->数字,value->数字出现的次数
47         hashMap.clear();
48         for (unsigned int i = row; i < row + 3; i++) {
49             for (unsigned int j = col; j < col + 3; j++) {
50                 if (board[i][j] == '.') {
51                     continue;
52                 }
53                 if (hashMap.count(board[i][j]) == 0) { // 数字没出现过就加入hash表
54                     hashMap[board[i][j]]++;
55                 } else { // 即将加入的数字之前出现过,不满足条件,直接返回false
56                     return false;
57                 }
58             }
59         }
60         return true;
61     }
62     bool isValidSudoku(vector<vector<char>>& board) {
63         if (board.size() != 9 || board[0].size() != 9) {
64             return false;
65         }
66         int row = board.size();
67         int col = board[0].size();
68         // 1、判定每一行是否满足
69         for (int i = 0; i < row; i++) {
70             if (!isRowValid(i, board)) {
71                 return false;
72             }
73         }
74         // 2、判定每一列是否满足
75         for (int j = 0; j < col; j++) {
76             if (!isColValid(j, board)) {
77                 return false;
78             }
79         }
80         // 3、判定每个3*3宫格内数字是否满足
81         for (int i = 0; i < row; i += 3) {
82             for (int j = 0; j < col; j += 3) {
83                 if (!isThreeGongGeValid(i, j, board)) {
84                     return false;
85                 }
86             }
87         }
88         return true;
89     }
90 };

方法二：采用位运算，分别用vector存储每行/每列/每3*3宫格内数字(用int的9个bit表示0-9数字)

 1 class Solution {
 2 public:
 3     bool isValidSudoku(vector<vector<char>>& board) {
 4         if (board.size() != 9 || board[0].size() != 9) {
 5             return false;
 6         }
 7         vector<int> row(9, 0); // 存储每行的数字,用int的9位表示每行数字
 8         vector<int> col(9, 0); // 存储每列的数字,用int的9位表示每列数字
 9         vector<int> v(9, 0); // 存储每个3*3宫格内的数字,用int的9位表示每个3*3空格内的数字
10         for (unsigned int i = 0; i < board.size(); i++) {
11             for (unsigned int j = 0; j < board[0].size(); j++) {
12                 if (board[i][j] == '.') {
13                     continue;
14                 }
15                 int num = (1 << (board[i][j] - '0'));
16                 int threeGongGe = (i / 3) * 3 + j / 3; // 将3 * 3宫格二维转换为一维
17                 if ((row[i] & num) != 0 || (col[j] & num) != 0 || (v[threeGongGe] & num) != 0) {
18                     return false;
19                 }
20                 row[i] |= num; // 将第i行的num位置1
21                 col[j] |= num; // 将第i列的num位置1
22                 v[threeGongGe] |= num; // 将第threeGongGe个3 * 3宫格的num位置1
23             }
24         }
25         return true;
26     }
27 };