以下是 LeetCode 36「有效的数独」的 Python3 实现。解题思路需要检查三类区域中数字是否重复每一行每一列每一个 3×3 宫格可以一次遍历整个棋盘用三个哈希集合数组分别记录· rows[i]第 i 行已经出现过的数字· cols[j]第 j 列已经出现过的数字· boxes[k]第 k 个宫格已经出现过的数字宫格索引通过 (i // 3) * 3 j // 3 计算。遇到 ‘.’ 跳过遇到数字时如果已经出现在对应的行、列或宫格集合中说明数独无效直接返回 False否则将该数字加入三个集合。代码fromtypingimportListclassSolution:defisValidSudoku(self,board:List[List[str]])-bool:rows[set()for_inrange(9)]cols[set()for_inrange(9)]boxes[set()for_inrange(9)]foriinrange(9):forjinrange(9):numboard[i][j]ifnum.:continuebox_idx(i//3)*3j//3ifnuminrows[i]ornumincols[j]ornuminboxes[box_idx]:returnFalserows[i].add(num)cols[j].add(num)boxes[box_idx].add(num)returnTrue复杂度分析· 时间复杂度O(9×9) O(1)因为棋盘大小固定。· 空间复杂度O(9×9) O(1)最坏情况下三个集合共存储 81 个数字。测试示例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]]print(Solution().isValidSudoku(board))# True