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)。