[Leetcode][python]Valid Sudoku/有效的数独

深碍√TFBOYSˉ_ 2022-06-08 03:58 185阅读 0赞

## 题目大意 ##

判断一个数度棋盘是否合理，不需要能解。  
1. 横向0-9  
2. 纵向0-9  
3. 小方格0-9

## 解题思路 ##

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

## 代码 ##

### set() ###

leetcode内他人提交的答案，膜一下。

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）！!！

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。