LeetCode 圖解 | 36.有效的數獨
- 2020 年 2 月 20 日
- 筆記
以下文章來源於算法無遺策 ，作者我脫下短袖
今天分享一個LeetCode題，題號是36，標題是：有效的數獨，題目標籤是散列表，散列表也稱哈希表。此題解題思路用到了少量的空間換取時間的方法，降低時間上的消耗。
題目描述
判斷一個 9×9 的數獨是否有效。只需要根據以下規則，驗證已經填入的數字是否有效即可。
數字 1-9 在每一行只能出現一次。 數字 1-9 在每一列只能出現一次。 數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。
數獨
上圖是一個部分填充的有效的數獨。
數獨部分空格內已填入了數字，空白格用 '.' 表示。
示例 1:
輸入: [ ["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:
輸入: [ ["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 解釋: 除了第一行的第一個數字從 5 改為 8 以外，空格內其他數字均與 示例1 相同。 但由於位於左上角的 3x3 宮內有兩個 8 存在, 因此這個數獨是無效的。
說明:
一個有效的數獨（部分已被填充）不一定是可解的。 只需要根據以上規則，驗證已經填入的數字是否有效即可。 給定數獨序列只包含數字 1-9 和字符 '.' 。 給定數獨永遠是 9x9 形式的。
解題
此題沒有要求數獨是可解的，只要求滿足以下規則，驗證已經填入的數字是否有效即可：
數字 1-9 在每一行只能出現一次。 數字 1-9 在每一列只能出現一次。 數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。
行的下標設為i，列的下標設為j，宮格的下標設為k，默認為0，如下圖：
行、列和宮格
隨着下標i和下標j的移動，i和j可以直接從下標中獲取數字，但k如何獲取對應的數字呢？看上面圖，k隨着i變化和k隨着j變化都有規律的，不多說，直接給公式：k = (int)(i / 3) * 3 + (int)(j / 3)。
根據規則，某數字的三個下標都只能出現一次，例如8：[0，0，0]，往後這個數組裡就不能再出現0了，有0出現就不符合有效數獨的規則了；再例如3：[0，1，0]，i下標和k下標不能再出現0了，j下標不能再出現1了。
但怎麼判斷某數字的三個下標是否是只出現了一次呢？
題目標籤只有散列表，那正合我意，我就是要用散列表去解決此題。而且數組裡的值最小是0，最大值是8，數組的長度都固定為3，可以用少量的空間換取時間的方法，如下圖8：[0，0，0]的表示：
空間換時間
這樣就減少了兩個數組比較的煩惱，通過空間換取時間的方法，就減少了不必要的比較計算。因為行i、列j和宮格k的長度都是9，將二維數組攤開作為一維數組，下標i、下標j+9和下標k+18分別控制一維數組的下標，存放的值都是布爾類型，默認為false。
保存某數字的時候，一維數組的下標i、下標j+9和下標k+18的值都變為true。保存某數字之前，需要判斷三個下標的值是否存在true，如果不存在，則將三個下標對應的值都變為true；如果存在，說明某下標已經出現一次了，再出現一次則意味着這個數獨已經無效，直接返回false。如下圖數字8的下標k已經出現一次了。
失效的數獨
動畫：使用散列表
Code：使用散列表
public boolean isValidSudoku(char[][] board) { // 創建散列表 Map<Integer, boolean[]> map = new HashMap<>(); for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] != '.') { // 字符的ASCII碼 十進制 int index = board[i][j]; // 創建宮格標記 int k = i / 3 * 3 + j / 3; // 空間換取時間 if (!map.containsKey(index)) { map.put(index, new boolean[27]); // 27個空間默認放false } // 獲取散列表的值 boolean[] booleans = map.get(index); if (booleans[i] == true || booleans[j + 9] == true || booleans[k + 18] == true) { return false; } else { booleans[i] = true; booleans[j + 9] = true; booleans[k + 18] = true; } } } } return true; } public static void main(String[] args) { char[][] 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'} }; boolean validSudoku = new Solution().isValidSudoku(board); System.out.println(validSudoku); }
時間複雜度
時間複雜度是O(n)，但實際上比O(n)要快。
