最近就在網上閑逛時，我撞見了一個很有意思的話題：「用一件事證明你已經開始消費降級了！」又到了網友們最擅長的領域了，我不開啟留言都知道，留言肯定是百家爭鳴。

果不其然，上來就非常炸裂，有位網友說：「別人懷孕7個月的二手女友都打算接盤了。」這話雖然是開玩笑的，但不得不說，還是非常炸裂。

然後是正常的回答，「我現在都不怎麽出門了。」這確實是符合題意。

還有人說，「以前還敢去K個歌，現在都是大橋邊合唱」咱就是說，這歌你是非唱不可嗎？

當然，大佬雖遲但到，「衛生紙洗洗還能用」。為了省錢，你也是真拼啊。

留言裏，甚至還有我都不敢放出來的回答，網友的才華我是佩服了。看到這些回答，說明大家狀態還是非常不錯的。不管是在開玩笑，還是真的苦中作樂，良好的心態必不可少。

也許我們的消費真的降級了。從大手大腳，到現在能省就省，但我們對生活的態度從未降級，依舊樂觀。

下面是今日的大廠演算法題

今日演算法題 ，來自LeetCod e的第36題：有效的數獨，下面是我 的算 法思路及實作，讓我們來看看吧。

# 演算法題目

判斷一個 9x9 的數獨是否有效。僅需要根據以下規則，驗證已經填入的數位是否有效即可。

1. 數位 1-9 在每一行只能出現一次。

   
   

2. 數位 1-9 在每一列只能出現一次。

3. 數位 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。

數獨部份空格內已填入了數位，空白格用 '.' 表示。

註意：

# 演算法思路

本問題可以透過使用哈希表來高效解決。具體步驟如下：

1. 建立三個型別為哈希表的數據結構，分別用於儲存每一行、每一列以及每一個小 3x3 宮格中數位出現的情況。

2. 遍歷數獨：

# 程式碼實作

Java實作

public boolean isValidSudoku(char[][] board) { HashSet<String> seen = new HashSet<>();for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {char number = board[i][j];if (number != '.') {if (!seen.add(number + " in row " + i) || !seen.add(number + " in column " + j) || !seen.add(number + " in block " + i / 3 + "-" + j / 3)) {returnfalse; } } } }returntrue;}

JavaScript實作

functionisValidSudoku(board) {let rows = newArray(9).fill(0).map(() =>newSet());let cols = newArray(9).fill(0).map(() =>newSet());let boxes = newArray(9).fill(0).map(() =>newSet());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)) {returnfalse; } rows[i].add(num); cols[j].add(num); boxes[boxIndex].add(num); } } }returntrue;}

Go實作

funcisValidSudoku(board [][]byte)bool {var rows, cols [9][9]intvar boxes [3][3][9]intfor 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 {returnfalse } rows[i][num], cols[j][num], boxes[i/3][j/3][num] = 1, 1, 1 } } }returntrue}

# 演算法解析

透過使用哈希表來記錄每個數位在行、列以及宮格中的出現情況，可以有效地檢查數獨是否滿足給定的規則。

這種方法的時間復雜度為 O(1)，因為數獨的大小是固定的（9x9），並且空間復雜度也是 O(1)，對於每個數位，我們只需要檢查其是否已經在相應的行、列或宮格中出現過即可。

# 範例和測試

考慮以下數獨：

53 . | . 7 . | . . .6 . . | 1 9 5 | . . .. 98| . . . | . 6 .------+------+------8 . . | . 6 . | . . 34 . . | 8 . 3 | . . 17 . . | . 2 . | . . 6------+------+------. 6 . | . . . |28 .. . . | 4 1 9 | . . 5. . . | . 8 . | . 79

透過上述任一實作的函式檢查，這個數獨是有效的，因為它滿足所有給定的規則。

# 總結

有效的數獨問題透過對陣列和哈希表的靈活使用，提供了一種高效檢查數獨規則的方法。這種方法不僅適用於數獨問題，還可以被套用到其他需要進行復雜規則驗證的場景中。掌握這種演算法思想，能夠在解決類似問題時提高效率和準確性。

熱門推薦