36. 有效的數獨（點擊查看題目）
題目描述
判斷一個 9x9 的數獨是否有效。只需要根據以下規則，驗證已經填入的數字是否有效即可。
- 數字 1-9 在每一行只能出現一次。
- 數字 1-9 在每一列只能出現一次。
- 數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。
上圖是一個部分填充的有效的數獨
數獨部分空格內已填入了數字，空白格用 '.' 表示。
示例 1:
示例 2:
說明:
- 一個有效的數獨（部分已被填充）不一定是可解的。
- 只需要根據以上規則，驗證已經填入的數字是否有效即可。
- 給定數獨序列只包含數字 1-9 和字符 '.' 。
- 給定數獨永遠是 9x9 形式的。
解決方案
思路
一個簡單的解決方案是遍歷該 9 x 9 數獨 三 次，以確保：
- 行中沒有重複的數字。
- 列中沒有重複的數字。
- 3 x 3 子數獨內沒有重複的數字。
實際上，所有這一切都可以在一次迭代中完成。
方法：一次迭代
首先，讓我們來討論下面兩個問題：
- 如何枚舉子數獨？
可以使用 box_index = (row / 3) * 3 + columns / 3，其中 / 是整數除法。
- 如何確保行 / 列 / 子數獨中沒有重複項？
可以利用 value -> count 哈希映射來跟蹤所有已經遇到的值。
現在，我們完成了這個算法的所有準備工作：
- 遍歷數獨。
- 檢查看到每個單元格值是否已經在當前的行 / 列 / 子數獨中出現過：
- 如果出現重複，返回 false。
- 如果沒有，則保留此值以進行進一步跟蹤。
- 返回 true。
圖片詳解
Java 實現
Python 實現
複雜度分析
時間複雜度：O(1)，因為我們只對 81 個單元格進行了一次迭代。
空間複雜度：O(1)。
分享到:
閱讀更多 力扣LeetCode 的文章
