主題

LeetCode - 36. Valid Sudoku 解題心得

Not In My Back Yard | 2021-05-08 00:00:10 | 巴幣 2 | 人氣 41

題目連結:


題目意譯:
判斷一個 9 × 9 數獨版面是否合法。只有有數字的格子需要按照以下方式檢查:
每列只能包含數字 1 ~ 9 且不重複。
每行只能包含數字 1 ~ 9 且不重複。
網格中九個 3 × 3 子網格,每個只能包含數字 1 ~ 9 且不重複。

注:
一個數獨版面(部分格子有數字)可以是合法的但不一定是可解的。
只有有著數字的格子需要按照提及的規則檢查合法性。

限制:
board.length == 9
board[i].length == 9
board[i][j] 為數字或是 '.'。



範例測資:
範例 1:
輸入: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
輸出: true

範例 2:
輸入: board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
輸出: false
解釋: 如同範例 1,除了左上角的 5 被更改為 8。因為左上角的 3 × 3 子網格有兩個 8,因此不合法。


解題思維:
可以根據這題的方式統計整個版面每列、每行以及每個九宮格區域的數字出現情形。以下為該文章節錄:
「我們定義 R[i][1] 、 C[i][1] 、 B[i][1] 分別代表為第 i 列、第 i 行以及第 i 個子區域(從左上開始,從左到右由上至下編號)裡有沒有數字 1 。其他如 R[i][7] 、C[i][8] 等等也是與此同理。」
「其中 block(i, j) 為 floor(i ÷ 3) × 3 + floor(j ÷ 3),而 floor() 為下高斯函數。」

所以當碰到第 i 列第 j 行的數字 c 時,如果 R[i][c] 、 C[j][c] 或是 B[block(i, j)][c] 其中一者已經為真(True)時,則代表有重複的數字出現於列、行或是九宮格內。因此給定的輸入版面不合法。

如果掃完所有數字(記得跳過空的格子 '.')後都沒有以上情形發生,則代表版面合法。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作