- Valid Sudoku
中等
https://leetcode.cn/problems/valid-sudoku/
Determine if a 9 x 9 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 nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
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.
Example 1:
Input: 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"]]
Output: true
Example 2:
Input: 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"]]
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.
Constraints:
board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or '.'.
相关企业
- 亚马逊 Amazon|17
- 优步 Uber|9
- 苹果 Apple|8
- 微软 Microsoft|8
- Facebook|5
- 字节跳动|4
- 谷歌 Google|3
- 英伟达 NVIDIA|2
相关标签
- Array
- Hash Table
- Matrix
相似题目
- Sudoku Solver 困难
这题考查的是二维数组的遍历顺序。
判断每一行是否合法,外层循环枚举行,内层循环枚举列。
判断每一列是否合法,外层循环枚举列,内层循环枚举行。
判断每一块是否合法,每一块左上角的坐标都是(0, 0), (3, 0), (6, 0), (0, 3), (3, 3), (6, 3), (0, 6), (3, 6), (6, 6) ,可以发现都是3的倍数,可以总结出规律,先枚举i = [0, 1, 2],再枚举j = [0, 1, 2],左上角坐标就是(i3, j3)。
假设这是一个N * N的数独,不止是9 * 9。
要遍历3次这个数独,时间复杂度为O(N^2)。
需要O(N)的空间,记录以用过的数。
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
if not board:
return False
# 先枚举行,检查每行是否合法
for row in range(9):
used = set()
for col in range(9):
if not self.isValid(board[row][col], used):
return False
# 先枚举列,检查每列是否合法
for col in range(9):
used = set()
for row in range(9):
if not self.isValid(board[row][col], used):
return False
# 每一块左上角的坐标(0, 0), (3, 0), (6, 0), (0, 3), (3, 3), (6, 3), (0, 6), (3, 6), (6, 6)
# 每个分块的左上角的坐标为(i * 3, j * 3)
for i in range(3):
for j in range(3):
used = set()
for row in range(i*3, i*3+3):
for col in range(j*3, j*3+3):
if not self.isValid(board[row][col], used):
return False
return True
def isValid(self, char, used):
if char == ".":
return True
if char in used:
return False
used.add(char)
return True