最近就在網上閑逛時，我撞見了一個很有意思的話題：「用一件事證明你已經開始消費降級了！」又到了網友們最擅長的領域了，我不開啟留言都知道，留言肯定是百家爭鳴。
果不其然，上來就非常炸裂，有位網友說：「別人懷孕7個月的二手女友都打算接盤了。」這話雖然是開玩笑的，但不得不說，還是非常炸裂。
然後是正常的回答，「我現在都不怎麽出門了。」這確實是符合題意。
還有人說，「以前還敢去K個歌，現在都是大橋邊合唱」咱就是說，這歌你是非唱不可嗎？
當然，大佬雖遲但到，「衛生紙洗洗還能用」。為了省錢，你也是真拼啊。
留言裏，甚至還有我都不敢放出來的回答，網友的才華我是佩服了。看到這些回答，說明大家狀態還是非常不錯的。不管是在開玩笑，還是真的苦中作樂，良好的心態必不可少。
也許我們的消費真的降級了。從大手大腳，到現在能省就省，但我們對生活的態度從未降級，依舊樂觀。
下面是今日的大廠演算法題
今日演算法題，來自LeetCode的第36題：有效的數獨，下面是我的演算法思路及實作，讓我們來看看吧。
# 演算法題目
判斷一個 9x9 的數獨是否有效。僅需要根據以下規則，驗證已經填入的數碼是否有效即可。
數碼 1-9 在每一行只能出現一次。
數碼 1-9 在每一列只能出現一次。
數碼 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。
數獨部份空格內已填入了數碼，空白格用 '.' 表示。
註意：
一個有效的數獨（針對已填入的數碼）不一定是可解的。
只需要根據上述規則，驗證已填入的數碼是否有效即可。
# 演算法思路
本問題可以透過使用哈希表來高效解決。具體步驟如下：
建立三個類別為哈希表的數據結構，分別用於儲存每一行、每一列以及每一個小 3x3 宮格中數碼出現的情況。
遍歷數獨：
對於每一個格子，透過其行號和列號判斷其所在的小宮格序號。
檢查當前數碼在當前行、當前列、當前小宮格中是否已經出現過，如果出現過，則說明數獨無效；如果沒有出現過，則在相應的行、列、宮格的哈希表中記錄該數碼。
完成遍歷後，如果沒有發現任何違反規則的情況，則數獨有效。
# 程式碼實作
Java實作
public boolean isValidSudoku(char board) { HashSetJavaScript實作
function isValidSudoku(board) { let rows = new Array(9).fill(0).map( => new Set); let cols = new Array(9).fill(0).map( => new Set); let boxes = new Array(9).fill(0).map( => new Set);
for (let i = 0; i < 9; i++) { for (let j = 0; j < 9; j++) { let num = board[i][j]; if (num !== '.') { let boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3); if (rows[i].has(num) || cols[j].has(num) || boxes[boxIndex].has(num)) { return false; } rows[i].add(num); cols[j].add(num); boxes[boxIndex].add(num); } } } return true;}
Go實作
func isValidSudoku(board byte) bool { var rows, cols [9][9]int var boxes [3][3][9]int
for i := 0; i < 9; i++ { for j := 0; j < 9; j++ { if board[i][j] != '.' { num := board[i][j] - '1' if rows[i][num] == 1 || cols[j][num] == 1 || boxes[i/3][j/3][num] == 1 { return false } rows[i][num], cols[j][num], boxes[i/3][j/3][num] = 1, 1, 1 } } } return true}
# 演算法解析
透過使用哈希表來記錄每個數碼在行、列以及宮格中的出現情況，可以有效地檢查數獨是否滿足給定的規則。
這種方法的時間復雜度為 O(1)，因為數獨的大小是固定的（9x9），並且空間復雜度也是 O(1)，對於每個數碼，我們只需要檢查其是否已經在相應的行、列或宮格中出現過即可。
# 範例和測試
考慮以下數獨：
5 3 . | . 7 . | . . .6 . . | 1 9 5 | . . .. 9 8 | . . . | . 6 8 . . | . 6 . | . . 34 . . | 8 . 3 | . . 17 . . | . 2 . | . . 6 6 . | . . . | 2 8 .. . . | 4 1 9 | . . 5. . . | . 8 . | . 7 9
透過上述任一實作的函數檢查，這個數獨是有效的，因為它滿足所有給定的規則。
# 總結
有效的數獨問題透過對陣列和哈希表的靈活使用，提供了一種高效檢查數獨規則的方法。這種方法不僅適用於數獨問題，還可以被套用到其他需要進行復雜規則驗證的場景中。掌握這種演算法思想，能夠在解決類似問題時提高效率和準確性。
