C++刷leetcode（36. 有效的数独）【数据结构】【set】

糖逗

题目描述：

1. 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
   
2. 
   
3. 数字 1-9 在每一行只能出现一次。
   
4. 数字 1-9 在每一列只能出现一次。
   
5. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
   
6. 
   
7. 
   
8. 上图是一个部分填充的有效的数独。
   
9. 
   
10. 数独部分空格内已填入了数字，空白格用 '.' 表示。
    
11. 
    
12. 示例 1:
    
13. 
    
14. 输入:
    
15. [
    
16.   ["5","3",".",".","7",".",".",".","."],
    
17.   ["6",".",".","1","9","5",".",".","."],
    
18.   [".","9","8",".",".",".",".","6","."],
    
19.   ["8",".",".",".","6",".",".",".","3"],
    
20.   ["4",".",".","8",".","3",".",".","1"],
    
21.   ["7",".",".",".","2",".",".",".","6"],
    
22.   [".","6",".",".",".",".","2","8","."],
    
23.   [".",".",".","4","1","9",".",".","5"],
    
24.   [".",".",".",".","8",".",".","7","9"]
    
25. ]
    
26. 输出: true
    
27. 示例 2:
    
28. 
    
29. 输入:
    
30. [
    
31.   ["8","3",".",".","7",".",".",".","."],
    
32.   ["6",".",".","1","9","5",".",".","."],
    
33.   [".","9","8",".",".",".",".","6","."],
    
34.   ["8",".",".",".","6",".",".",".","3"],
    
35.   ["4",".",".","8",".","3",".",".","1"],
    
36.   ["7",".",".",".","2",".",".",".","6"],
    
37.   [".","6",".",".",".",".","2","8","."],
    
38.   [".",".",".","4","1","9",".",".","5"],
    
39.   [".",".",".",".","8",".",".","7","9"]
    
40. ]
    
41. 输出: false
    
42. 解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
    
43.      但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
    
44. 说明:
    
45. 
    
46. 一个有效的数独（部分已被填充）不一定是可解的。
    
47. 只需要根据以上规则，验证已经填入的数字是否有效即可。
    
48. 给定数独序列只包含数字 1-9 和字符 '.' 。
    
49. 给定数独永远是 9x9 形式的。
    
50. 
    
51. 来源：力扣（LeetCode）
    
52. 链接：https://leetcode-cn.com/problems/valid-sudoku
    
53. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     bool isValidSudoku(vector<vector<char>>& board) {
   
4.         vector<set<char> > row(9), col(9), matrix(9);
   
5.         for(int i = 0; i < 9; i++){
   
6.             for(int j = 0; j < 9; j ++){
   
7.                 int temp = (i/3) *3 + (j/3);
   
8.                 char store = board[i][j];
   
9.                 if(store == '.')continue;
   
10.                 if(row[i].count(store) || col[j].count(store) || matrix[temp].count(store)) return false;
    
11.                 row[i].insert(store);
    
12.                 col[j].insert(store);
    
13.                 matrix[temp].insert(store);
    
14.             }
    
15.         }
    
16.         return true;
    
17.     }
    
18. };

复制代码