如何查询某个网站的设计公司,前端兼职平台的行业前景,美工做图哪个网站好,用户管理系统登录admin本文目录 1 中文题目2 求解方法#xff1a;python内置函数set2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目
请根据以下规则判断一个 9 x 9 的数独是否有效。
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线… 本文目录 1 中文题目2 求解方法python内置函数set2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目
请根据以下规则判断一个 9 x 9 的数独是否有效。
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。见下方的参考示例图
注意
一个有效的数独部分已被填充不一定是可解的。只需要根据以上规则验证已经填入的数字是否有效即可。空白格用 ‘.’ 表示。
示例 对于上面的数独其输入格式如下
输入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输入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 9board[i].length 9board[i][j] 是一位数字1-9或者 ‘.’ 2 求解方法python内置函数set
2.1 方法思路
方法核心
使用三组集合分别记录每行、每列和每个3x3方块中已出现的数字一次遍历完成所有验证使用数学公式计算粗实线分割出来的3x3方块的索引
实现步骤
1初始化数据结构
创建9个集合用于存储每行的数字创建9个集合用于存储每列的数字创建9个集合用于存储每个3x3方块的数字
2遍历数独板
双层循环遍历9x9的数独板对于每个位置获取当前数字跳过空格用’.表示计算当前位置所在的3x3方块的索引检查数字是否重复出现将不重复的数字添加到对应集合中
3验证过程
检查当前数字是否已在当前行出现检查当前数字是否已在当前列出现检查当前数字是否已在当前3x3方块出现如果出现重复立即返回False如果遍历完成没有重复返回True
方法示例
输入数独板示例部分
[[5,3,.,.,7,.,.,.,.],[6,.,.,1,9,5,.,.,.],[.,9,8,.,.,.,.,6,.],...
]详细执行过程1. 初始化rows [set(), set(), set(), ...] (9个空集合)cols [set(), set(), set(), ...] (9个空集合)boxes [set(), set(), set(), ...] (9个空集合)2. 处理第一个位置 (0,0)- 数字为 5- box_index (0 // 3) * 3 (0 // 3) 0- 检查 rows[0], cols[0], boxes[0] 都不包含 5- 将 5 添加到这三个集合中3. 处理第二个位置 (0,1)- 数字为 3- box_index (0 // 3) * 3 (1 // 3) 0- 检查集合添加数字4. 继续处理每个位置...示例中3x3方块索引的计算
- 位置(0,0): (0//3)*3 0//3 0
- 位置(0,4): (0//3)*3 4//3 1
- 位置(4,4): (4//3)*3 4//3 42.2 Python代码
class Solution:def isValidSudoku(self, board: List[List[str]]) - bool:# 初始化用于存储每行、每列和每个3x3方块中数字出现情况的集合rows [set() for _ in range(9)]cols [set() for _ in range(9)]boxes [set() for _ in range(9)]# 遍历整个数独板for i in range(9):for j in range(9):# 获取当前位置的数字num board[i][j]# 如果是空格继续下一个位置if num .:continue# 计算当前位置所在的3x3方块的索引# box_index (行号 // 3) * 3 (列号 // 3)box_index (i // 3) * 3 j // 3# 检查当前数字是否已经在对应的行、列或3x3方块中出现过if (num in rows[i] or num in cols[j] or num in boxes[box_index]):return False# 将当前数字添加到对应的集合中rows[i].add(num)cols[j].add(num)boxes[box_index].add(num)# 遍历完成且没有发现重复返回Truereturn True2.3 复杂度分析
时间复杂度O(1) 固定大小的9x9网格遍历一次数独数组每次检查和添加操作都是O(1)总操作次数是常数 空间复杂度O(1) 使用固定大小的集合9个集合用于行9个集合用于列9个集合用于3x3方块 3 题目总结
题目难度中等 数据结构二维数组 应用算法Python内置函数set
