题目
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
数独.png
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1:
输入
[
["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:
输入
[
["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 存在, 因此这个数独是无效的。
说明:
- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
- 给定数独序列只包含数字
1-9和字符'.'。 - 给定数独永远是
9x9形式的。
解题思路
我的思路：答案(一)
建一个字典，值都是空集合，其中的键有3种类型：
第一种：键是0~8，记录每一行的数据；
第二种：键是9~17，记录每一列的数据；
第三种：这一种比较特殊，在9 * 9的大图里面，总共只有9个 小图，因此，每一个3 * 3是一个单独的集合，这里我用(i // 3, j//3)作为键
然后，就是依次遍历这81个数，分别判断这个元素是否在对应的集合中，如果不存在就添加，如果存在就返回。
结果完成了，但是比较慢。
我觉得主要慢在建这个字典的时候的运算就非常大
最快思路：答案(二)
弄3个列表，每个列表里面有9个集合
遍历这81个数，根据行和列，判断是否属于对应列表中某个索引值的集合中，和我上面的基本思想一样。
这里最关键还用了一种方案，将2个一样的列表，双遍历得到的2个数，组合成唯一不重复的索引值的方法，详见代码。
答案(一)
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
target_dict = {}
for i in range(9):
target_dict[i] = set()
target_dict[i + 10] = set()
for i in range(3):
for j in range(3):
target_dict[(i, j)] = set()
for l in range(9):
for k in range(9):
value = board[l][k]
if value == '.':
continue
if value in target_dict[l]:
return False
else:
target_dict[l].add(value)
if value in target_dict[k + 10]:
return False
else:
target_dict[k + 10].add(value)
if value in target_dict[(l // 3, k // 3)]:
return False
else:
target_dict[(l // 3, k // 3)].add(value)
return True
答案(二)
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
row = [set() for i in range(9)]
vertical = [set() for i in range(9)]
net = [set() for i in range(9)]
for i in range(9):
for j in range(9):
num = board[i][j]
if num == '.':
continue
if num in row[i]:
return False
if num in vertical[j]:
return False
index = i // 3 * 3 + j // 3
if num in net[index]:
return False
row[i].add(num)
vertical[j].add(num)
net[index].add(num)
return True
