LeetCode 0036 - Valid Sudoku
# Hints
- 模拟
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Determine if a Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits
1-9
without repetition.Each column must contain the digits
1-9
without repetition.Each of the sub-boxes of the grid must contain the digits
1-9
without repetition.
A partially filled sudoku which is valid.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'
.
Example 1:
Input:
[
["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"]
]
Output: true
Example 2:
Input:
[
["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"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being
modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
The given board contain only digits 1-9
and the character '.'
.
The given board size is always .
# 题意
给定一个 的数独,判断当前数独是否合法(无需判断是否存在合法方案填满整个数独,只需判断当前给定情况)。
# 题解
按题意模拟即可。唯一的难点是对每个 的方格的处理,求一个坐标映射即可。
# AC代码
class Solution {
public:
bool isValidSudoku(vector<vector<char>> & board) {
// 声明
bool existed[10];
// 判断行
for (int i = 0; i < 9; i ++) {
memset(existed, false, sizeof(existed));
for (int j = 0; j < 9; j ++) {
if (!check(board[i][j], i, j, existed)) {
return false;
}
}
}
// 判断列
for (int j = 0; j < 9; j ++) {
memset(existed, false, sizeof(existed));
for (int i = 0; i < 9; i ++) {
if (!check(board[i][j], i, j, existed)) {
return false;
}
}
}
// 判断方格
for (int k = 0; k < 9; k ++) {
memset(existed, false, sizeof(existed));
int x = 3 * (k / 3), y = 3 * (k % 3);
for (int i = x; i < x + 3; i ++) for (int j = y; j < y + 3; j ++) {
if (!check(board[i][j], i, j, existed)) {
return false;
}
}
}
// 返回
return true;
}
// 判断
bool check(char num, int x, int y, bool existed[]) {
if (num == '.') {
return true;
}
if (!existed[num - '0']) {
existed[num - '0'] = true;
return true;
}
return false;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01