36. Valid Sudoku
程序员文章站
2022-07-15 12:28:08
...
这题难度为中等,目前通过率为37.7%
题目:
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
1.Each row must contain the digits 1-9 without repetition.
2.Each column must contain the digits 1-9 without repetition.
3.Each of the 9 (3x3) sub-boxes of the grid must contain the digits 1-9 without repetition.
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:
1.A Sudoku board (partially filled) could be valid but is not necessarily solvable.
2.Only the filled cells need to be validated according to the mentioned rules.
3.The given board contain only digits 1-9 and the character '.'.
4.The given board size is always 9x9.
题目是给出一个数独判断已填数字是否满足规则。
思路:
把题目当成是一个空的数独板,然后往上面填已知的数字,如果填数字的过程中违反规则,则返回False。填完所有格子后,返回True。
实现过程中用了三个数组,分别是判断行、列、每个9宫格中是否有数字重复。
代码:
class Solution:
def isValidSudoku(self, board):
row = [[False for i in range(9)] for j in range(9)]
col = [[False for i in range(9)] for j in range(9)]
sqr = [[[False for i in range(9)] for j in range(3)] for k in range(3)]
for i in range(9):
for j in range(9):
if board[i][j] != '.':
num = int(board[i][j])-1
if row[i][num] or col[j][num] or sqr[i//3][j//3][num] :
return False
row[i][num] = True
col[j][num] = True
sqr[i // 3][j // 3][num] = True
return True
复杂度分析:
由于整个规模是固定的,因此时间复杂度T(n)=O(1)。
提交:
上一篇: BigDecimal类的加减乘除
推荐阅读
-
【关于栈】Valid Parentheses详解
-
css3中检验表单的required,focus,valid和invalid样式
-
AndroidStudio构建项目提示错误信息“unable to find valid certification”的完美解决方案
-
entity framework异常 The specified cast from a materialized 'System.Int32' type to the 'System.String' type is not valid
-
参数验证 @Validated 和 @Valid 的区别
-
js is_valid_filename验证文件名的函数
-
CENTOS7错误:Cannot find a valid baseurl for repo: base/7/x86_6
-
[转载]—Health Check Reports Problem: Dependency$ p_timestamp mismatch for VALID objects (文档 ID 781959.1)
-
Linux安装Apache报错:Cannot find a valid baseurl for repo: base/7/x86_64解决方案
-
centos7安装docker后运行出现Cannot find a valid baseurl for repo: base/7/x86_64 错误,怎么解决?