leetcode explore 初级算法第十题。原题链接:
https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/30/
原题内容如下:
题意拆解:
1、首先,输入是一个二维数组,二维数组的结果是列表嵌套列表,而最里层的列表里接收的是数字和 . 号。 2、根据已经输入的数字,判断是否符合数独的条件。 3、数独条件为:每一列和每一行数字不重复;图片中加粗的 3*3 格里,数字不能重复。
其实这个题目确实是一个简单版的判断数独的问题,因为它不需要去推理出其他数字,只需要根据已经出现的数字来判断是否满足条件即可。
而这个题目只需要把题目给出的三个条件分别用代码实现即可,考察的是我们对二维列表的熟练程度。参考代码如下:
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
if not board:
return True
# 行列同时检查
line_dict = {}
col_dict = {}
# 3*3 检查
three_dict = {}
for col in range(len(board[0])):
for line in range(len(board)):
cur_num = board[line][col]
if cur_num == ".":
continue
# 列固定
if not col_dict.get(col):
col_dict[col] = {}
if col_dict[col].get(cur_num):
return False
col_dict[col][cur_num] = 1
# 行固定
if not line_dict.get(line):
line_dict[line] = {}
if line_dict[line].get(cur_num):
return False
line_dict[line][cur_num] = 1
# 3*3
three_col = col // 3
three_line = line // 3
if not three_dict.get(three_col):
three_dict[three_col] = {}
if not three_dict[three_col].get(three_line):
three_dict[three_col][three_line] = {}
if three_dict[three_col][three_line].get(cur_num):
return False
three_dict[three_col][three_line][cur_num] = 1
return True
1、对于列表嵌套的情况,要熟练去获取数据 2、通过这个题目我们也能看到“数独”这样一个比较有趣的数学题目,可以去了解下它的解题方法。