提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
今天这题没啥意思,像古诗文默写。
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
注意:
一个有效的数独(部分已被填充)不一定是可解的。
只需要根据以上规则,验证已经填入的数字是否有效即可。
空白格用 ‘.’ 表示。
示例 1:
输入: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”]]
输出:true
示例 2:
输入: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”]]
输出:false
解释:除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
board.length == 9
board[i].length == 9
board[i][j] 是一位数字(1-9)或者 '.'
本题并不需要填数,只需要判断已经填好的数是否符合规则即可,整体来讲就是遍历+判断,没什么技术含量
如果使用暴力解法,就是先按行遍历,再按列遍历,最后在方块内遍历,每次在一行or一列内维持一个len=9的列表,表中的01代表下表数字是否在这一part中出现。对于九个方块,需要维持一个9*9的二维表,每行代表一个方块。
暴力破解时间复杂度O(n^2)
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
#暴破
#按行遍历,验证每一行
for i in range(9):
temp=[0 for x in range(10)]
for j in range(9):
if(board[i][j] != "."): #有数
board[i][j]=int(board[i][j]) #转化为数字
if temp[board[i][j]]==0 : #没重复
temp[board[i][j]]=1
else: #重复了
return False
#按列遍历,验证每一列
for i in range(9):
temp=[0 for x in range(10)]
for j in range(9):
if(board[j][i] != "."): #有数
if temp[board[j][i]]==0 : #没重复
temp[board[j][i]]=1
else: #重复了
return False
#方格内遍历,形成一张9*9的表,每行代表一个方块
temp=[[0 for y in range(10)] for x in range(10)]
for i in range(9):
for j in range(9):
if(board[i][j] != "."): #有数
row=i//3
col=j//3 #求出方格的位置
index=row*3+col #求出在表中存放的行数
if temp[index][board[i][j]]==0 : #没重复
temp[index][board[i][j]]=1
else: #重复了
return False
return True