力扣(leetcode) 36. 有效的數獨（暴力法）（哈希表套清單法）

題目在這​​:https://leetcode-cn.com/problems/valid-sudoku/​​

法一:(暴力法)

思路分析:

首先想到使用暴力法解決這道題。

1.建立函數一個函數用于判斷整行數組是否有重複數字。

2.将整個二維數組周遊，每一行都調用該函數進行判斷是否有重複數字，

3.然後轉置整個數組，繼續上面的步驟。(相當于判斷了每列是否有重複數字)

4.然後再逐個切片出來每一個九宮格，繼續拿去判斷。

這樣比較麻煩，但是屬于首先當道的比較容易明白的暴力法。

完整代碼:

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        from  collections import  Counter

        import  numpy as np

        def Judge(board):  # 用于判斷所有橫向數組中是否有重複的元素
            for i in board:
                hash_i = Counter(i)
                for j in hash_i:
                    if j != '.':
                        if hash_i[j] > 1:
                            return False
            return True
        def Slice(ll):  # 用于單行判斷
            hash_j = Counter(ll)
            for j in hash_j:
                if j != '.':
                    if hash_j[j] > 1:
                        return False
            return True


        if __name__ == '__main__':

           
            np_board_T = np.array(board).T
            res = np.array(board)


            return (
                Judge(board)
                and Judge(np_board_T)
                and Slice(res[6:9,0:3].flatten().tolist())
                and Slice(res[6:9,3:6].flatten().tolist())
                and Slice(res[6:9,6:9].flatten().tolist())

                and Slice(res[0:3,0:3].flatten().tolist())
                and Slice(res[0:3,3:6].flatten().tolist())
                and Slice(res[0:3,6:9].flatten().tolist())

                and Slice(res[3:6,0:3].flatten().tolist())
                and Slice(res[3:6,3:6].flatten().tolist())
                and Slice(res[3:6,6:9].flatten().tolist())

            )      

代碼中使用了一部分numpy的函數，其實完全沒必要用，普通的方法也可以實作。就是順便複習一下numpy。

關于numpy的總結，可以看我​​​另一篇文章​​，有總結筆記。

法二:(哈希表套清單)

我也是才知道哈希表可以這樣套用。

哈希表套用 定義方法:

from collections import  defaultdict

        xx = defaultdict(list)  # 哈希表套list
        xy = defaultdict(set)   #`哈希表套set
                                # 其他套法同理      

假設 三個哈希表 row 存行 col 存列 nin 存九宮格

實際上我們平常用的哈希表是這樣的 ​

​{key:val}​

​​。而哈希表套清單，就是将val出變成一個清單 ​

​{key:[list]}​

​​。

像這道題 我們就可以用key表示行數(列數，九宮格) .而val可以表示該行、列、九宮格裡的數字 ，

比如 ​​

​row = {0:[1,3,4,5]}​

​​ 表示第0行 裡有數字 ​

​1，3，4，5​

​。

且，每個數字必定存在于 某個行、某個列、某個九宮格當中，

可以使用 公式 : ​​

​i // 3 * 3 + j // 3​

​ 計算目前數字在那個九宮格之中。

• 周遊整體數組，看目前元素是否在行、列、九宮格之中，如果在，則檢查是否有重複的，有重複則直接傳回False。如果不在則加入其中。（此時行，列，九宮格，三個哈希表均需加入,原因前面已經說過了。）
• 若目前元素為空 即題中所給的 逗号，則直接結束本次循環。

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        from collections import  defaultdict

        row = defaultdict(list) # 行
        col = defaultdict(list) # 列
        nin = defaultdict(list) # 九宮格
        for i in range(9):
            for j in range(9):
                val = board[i][j]
                if val == '.':
                    continue

                point = i // 3 * 3 + j // 3

                if val in row[i] or val in col[j] or val in nin[point]:
                    return False
                row[i].append(val)
                col[j].append(val)
                nin[point].append(val)
                
        return  True