36 Valid Sudoku 有效的數(shù)獨(dú)
Description:
Determine if a 9x9 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 9 3x3 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:
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 9x9.
題目描述:
判斷一個 9x9 的數(shù)獨(dú)是否有效冯吓。只需要根據(jù)以下規(guī)則劣光，驗證已經(jīng)填入的數(shù)字是否有效即可墓赴。
數(shù)字 1-9 在每一行只能出現(xiàn)一次渔隶。
數(shù)字 1-9 在每一列只能出現(xiàn)一次浅悉。
數(shù)字 1-9 在每一個以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次峻堰。
上圖是一個部分填充的有效的數(shù)獨(dú)悟民。
數(shù)獨(dú)部分空格內(nèi)已填入了數(shù)字侠姑，空白格用 '.' 表示。
示例 :
示例 1:
輸入:
[
["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:
輸入:
[
["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
解釋: 除了第一行的第一個數(shù)字從 5 改為 8 以外疫蔓，空格內(nèi)其他數(shù)字均與 示例1 相同含懊。
但由于位于左上角的 3x3 宮內(nèi)有兩個 8 存在, 因此這個數(shù)獨(dú)是無效的。
說明:
一個有效的數(shù)獨(dú)（部分已被填充）不一定是可解的衅胀。
只需要根據(jù)以上規(guī)則岔乔，驗證已經(jīng)填入的數(shù)字是否有效即可。
給定數(shù)獨(dú)序列只包含數(shù)字 1-9 和字符 '.' 滚躯。
給定數(shù)獨(dú)永遠(yuǎn)是 9x9 形式的雏门。
思路:
- 3次遍歷逐行, 逐列, 和對每個盒子都進(jìn)行一次遍歷
- 方法 1的三次遍歷可以用一次遍歷完成, row的下標(biāo)對應(yīng)最外層遍歷下標(biāo) i, col的下標(biāo)對應(yīng)內(nèi)層遍歷下標(biāo) j, 盒子的下標(biāo)可以用 (i / 3) * 3 + j / 3找到
- 由于下標(biāo)最大為 9, 可以使用位運(yùn)算代替建立數(shù)組, 加快運(yùn)算速度, 用二進(jìn)制上的 1表示該位已經(jīng)訪問過
時間復(fù)雜度O(1), 空間復(fù)雜度O(1), 最多遍歷 81(* 3)次, 最多建立 9 * 9數(shù)組 3個
代碼:
C++:
class Solution
{
public:
bool isValidSudoku(vector<vector<char>>& board)
{
int row[9][9]{0}, col[9][9]{0}, box[9][9]{0};
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (board[i][j] != '.')
{
int num = board[i][j] - '1', box_index = i / 3 * 3 + j / 3;
if (row[i][num] or col[j][num] or box[box_index][num]) return false;
row[i][num] = 1;
col[j][num] = 1;
box[box_index][num] = 1;
}
}
}
return true;
}
};
Java:
class Solution {
public boolean isValidSudoku(char[][] board) {
for (int i = 0; i < 9; i++) {
int row = 0, col = 0, box = 0;
for (int j = 0; j < 9; j++) {
int r = board[i][j] - '0', c = board[j][i] - '0', b = board[(i / 3) * 3 + j / 3][(i % 3) * 3 + j % 3] - '0';
if (r > 0) row = helper(r, row);
if (c > 0) col = helper(c, col);
if (b > 0) box = helper(b, box);
if (row == -1 || col == -1 || box == -1) return false;
}
}
return true;
}
private int helper(int n, int val) {
return ((val >> n) & 1) == 1 ? -1 : val ^ (1 << n);
}
}
Python:
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
def helper(n: int, val: int):
return -1 if ((val >> n) & 1) == 1 else val ^ (1 << n)
for i in range(9):
row = col = box = 0
for j in range(9):
r, c, b = ord(board[i][j]) - 48, ord(board[j][i]) - 48, ord(board[(i // 3) * 3 + j // 3][(i % 3) * 3 + j % 3]) - 48
row, col, box = helper(r, row) if r > 0 else row, helper(c, col) if c > 0 else col, helper(b, box) if b > 0 else box
if row == -1 or col == -1 or box == -1:
return False
return True
