今天分享一個LeetCode題，題號是36，標題是：有效的數獨，題目標籤是散列表，散列表也稱哈希表。此題解題思路用到了少量的空間換取時間的方法，降低時間上的消耗。
題目描述判斷一個 9x9 的數獨是否有效。只需要根據以下規則，驗證已經填入的數字是否有效即可。
數字 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)要快。