題目出處
難度
Medium
題目分類
array, hash-table, matrix
個人範例程式碼
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# Each row must contain the digits 1-9 without repetition.
for each_row in board:
if self.checknums(each_row):
pass
else:
return False # early return
# Each column must contain the digits 1-9 without repetition.
transpose_board = list(zip(*board)) # unpack list, then rezip by column
for each_row in transpose_board:
if self.checknums(each_row):
pass
else:
return False # early return
# Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
for y_idx in range(0, 9, 3):
for x_idx in range(0, 9, 3):
collection = self.getsubbox(board, x_idx, y_idx)
if self.checknums(collection):
pass
else:
return False # early return
return True
def getsubbox(self, board, start_x ,start_y):
collection = []
for y_idx in range(3):
for x_idx in range(3):
collection.append(board[start_y+y_idx][start_x+x_idx])
return collection
def checknums(self, nums: List[str]) -> bool:
keep = set()
for ele in nums:
if ele == ".":
pass
elif ele in keep:
return False
else:
keep.add(ele)
return True
Time Complexity
x
算法說明
這題，基本上就是條件多了一點，
要比較有耐心的處理，並且把指定的項目都拿出來，
除此之外難度不高。
要有耐心處理條件反而是我覺得這題難的地方。
我的算法基本上就依照題目敘述，
先建立一個檢查的函數，之後我們都以「9個位置為單位」傳入，
檢查出結果並回傳。
比較麻煩的大概是小的 sub-box，這裡要有點耐心處理。
幾個小細節可以注意：
「轉置矩陣」好用技巧：用「*」拆開 list後，再用「zip」重組。
簡單來說，想快速得到轉置矩陣(像這題我們為了把 column 拉出來)，
我們可以用「*」拆開 list後，再用「zip」重組。
a = [[1,2],[3,4]]
print(*a) # [1,2],[3,4] <- 拆開 list
print(list(zip(*a))) # [[1,3],[2,4]] <- 拆開 list，zip 重組，從 zip 轉 list 格式
詳情可以看我的另外一篇：
early return：只要發現不合規則，即可以 return。
相對於此方法的就是建立一個 flag，過程中全檢查，最後才回傳這個 flag，但因為我們早知道結果，不需要全部組合都檢查才 return。
搜尋請用 set/ dict 而不要用 list：set/dict 的查找速度為 O(1)，list 為 O(n)。
簡單來說，只要單純是做搜尋功能的，建議都用 set/dict，查找速度為 O(1)，
有些人 list 因為太方便用習慣了，但 list 查詢速度為 O(n)，可能會浪費很多時間在查找上。
一提再提的重點：只要有「找重複」的事情，幾乎必使用 set()
這題換句話說就是「找有沒有重複數字」，這部分應該會使用到 set。
set 在「找尋重複項目」可以發揮最快的時間，幾乎是「找重複問題」必用。
corner case 特殊情況處理
x
Boundary conditions/ Edge conditions 邊際情況處理
x
討論區看到的一些酷解法 - 1
這個作者很聰明的，把在 sudoku 出現的每一個元素都弄成一個 set，
依據規則總共有三種：
這個解法漂亮的地方在於，[0,1,2,3,4,5,6,7,8] 經過 // 3 後，會變成 [0,0,0,1,1,1,2,2,2]，
因此我們就可以比較重複元素了！
可以參考：
範例程式碼
看完解答後我自己也照他的概念重寫了自己的，真的快又準確，好猛…
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# Each row must contain the digits 1-9 without repetition.
rule1_set = set()
# Each column must contain the digits 1-9 without repetition.
rule2_set = set()
# Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
rule3_set = set()
for y, each_row in enumerate(board):
for x, ele in enumerate(each_row):
if ele != '.':
rule1_ele = (ele, y)
rule2_ele = (x, ele)
rule3_ele = (x//3, y//3, ele)
if rule1_ele in rule1_set:
return False
else:
rule1_set.add(rule1_ele)
if rule2_ele in rule2_set:
return False
else:
rule2_set.add(rule2_ele)
if rule3_ele in rule3_set:
return False
else:
rule3_set.add(rule3_ele)
return True
corner case 特殊情況處理
注意要處理 “.”，不然會以為已經出現過了。
Boundary conditions/ Edge conditions 邊際情況處理
x
討論區看到的一些酷解法 - 2
與上面酷解法差不多，這邊只是想強調比對時，可以用
if len(list) == len(set(list)):
# 兩者相等，表示 set 未刪去東西 (無重複項)
else:
# 兩者不相等，表示 set 有刪去東西 (有重複項)
注意：不可以比較「 list = set(list))」，因為「資料型態不同」，必定為 False
可以參考：
範例程式碼
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# Each row must contain the digits 1-9 without repetition.
rule1_list = []
# Each column must contain the digits 1-9 without repetition.
rule2_list = []
# Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
rule3_list = []
for y, each_row in enumerate(board):
for x, ele in enumerate(each_row):
if ele != '.':
rule1_ele = (ele, y)
rule2_ele = (x, ele)
rule3_ele = (x//3, y//3, ele)
rule1_list.append(rule1_ele)
rule2_list.append(rule2_ele)
rule3_list.append(rule3_ele)
return len(set(rule1_list)) == len(rule1_list) and \
len(set(rule2_list)) == len(rule2_list) and \
len(set(rule3_list)) == len(rule3_list) # if no duplicate in list, will return True
corner case 特殊情況處理
注意要處理 “.”，不然會以為已經出現過了。
Boundary conditions/ Edge conditions 邊際情況處理
x