数据结构第五天学习进展如何？

本文共计505个文字，预计阅读时间需要3分钟。

36. 判断有效数独判断一个数独是否有效，只需检查当前数独中的数独是否有效（无需填充数独）。只需提供3个二维数组，分别代表9行、9列和9个九宫格。

pythonclass Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: row=[[False] * 9 for _ in range(9)] col=[[False] * 9 for _ in range(9)] box=[[False] * 9 for _ in range(9)]

for i in range(9): for j in range(9): num=board[i][j] if num !='.': box_index=(i // 3) * 3 + j // 3 if row[i][ord(num) - ord('1')] or col[j][ord(num) - ord('1')] or box[box_index][ord(num) - ord('1')]: return False row[i][ord(num) - ord('1')]=col[j][ord(num) - ord('1')]=box[box_index][ord(num) - ord('1')]=True return True

36. 有效的数独

判断当前数独是否有效（不需要填充数独） 只要用3个二维数组维护9行、9列、9个九宫格。

class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: row = [[] * 9 for _ in range(9)] col = [[] * 9 for _ in range(9)] nine = [[] * 9 for _ in range(9)] for i in range(len(board)): for j in range(len(board[0])): tmp = board[i][j] if not tmp.isdigit(): continue if (tmp in row[i]) or (tmp in col[j]) or (tmp in nine[(j // 3) * 3 + (i // 3)]): return False row[i].append(tmp) col[j].append(tmp) nine[(j // 3) * 3 + (i // 3)].append(tmp) return True

73. 矩阵置零

如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 A： 利用数组的首行和首列来记录 0 值 另外用两个布尔值记录首行首列是否需要置0

class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ #标记 m,n = len(matrix), len(matrix[0]) row = any(x == 0 for x in matrix[0]) col = any(matrix[r][0] == 0 for r in range(m) ) for i in range(m): for j in range(n): if matrix[i][j] == 0: matrix[i][0] = 0 matrix[0][j] = 0 #置零 for i in range(1,m): for j in range(1,n): if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0 if row: for j in range(0,n): matrix[0][j] = 0 if col: for i in range(0,m): matrix[i][0] = 0