企业官网建设流程全解析

以下是 LeetCode 36「有效的数独」的 Python3 实现。

解题思路

需要检查三类区域中数字是否重复：

1. 每一行
2. 每一列
3. 每一个 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):num=board[i][j]ifnum=='.':continuebox_idx=(i//3)*3+j//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