【Leetcode】【python】Valid Sudoku 有效的数独

题目大意

判断一个数度棋盘是否合理,不需要能解。

  1. 横向0-9
  2. 纵向0-9
  1. 小方格0-9

    解题思路

    这台网上很多答案都在暴力穷举,正确的python答案应该是用set。

    代码

    set()

    leetcode内他人提交的答案,膜一下。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution(object):
    def isValidSudoku(self, board):
    """
    :type board: List[List[str]]
    :rtype: bool
    """
    seen = set()
    for i in range(9):
    for j in range(9):
    c = board[i][j]
    if c == '.':
    continue
    if (i, c) in seen or (c, j) in seen or (i/3, j/3, c) in seen:
    return False
    seen.add((i, c))
    seen.add((c, j))
    seen.add((i/3, j/3, c))
    return True

    dict

我提交的,我强行按照标签给的hash table来做,把整个三中需要验证的都写为key,然后去组合这些key名,十分容易看懂,但最后通过时ms很高。所以用hash table的合理方案就是答案1(set)!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
Sudoku_dict = {'row_0':[], 'row_1':[], 'row_2':[], 'row_3':[], 'row_4':[], 'row_5':[], 'row_6':[], 'row_7':[], 'row_8':[],
'col_0':[], 'col_1':[], 'col_2':[], 'col_3':[], 'col_4':[], 'col_5':[], 'col_6':[], 'col_7':[], 'col_8':[],
'squ_00':[], 'squ_01':[], 'squ_02':[], 'squ_10':[], 'squ_11':[], 'squ_12':[], 'squ_20':[], 'squ_21':[], 'squ_22':[]}
for i in range(9):
for j in range(9):
if board[i][j]=='.':
continue
temp = board[i][j]
row_name = 'row_' + str(i)
col_name = 'col_' + str(j)
squ_name = 'squ_' + str((i)/3) + str((j)/3)
# print row_name, col_name, squ_name
if temp in Sudoku_dict[row_name]:
return False
else:
Sudoku_dict[row_name].append(temp)
if temp in Sudoku_dict[col_name]:
return False
else:
Sudoku_dict[col_name].append(temp)
if temp in Sudoku_dict[squ_name]:
return False
else:
Sudoku_dict[squ_name].append(temp)
# print Sudoku_dict
return True

总结

set和dict类似,也是一组key的集合,但不存储value。由于key不能重复,所以,在set中,没有重复的key。