「leetcode」36. 有效的數獨

題目

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

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

數字 1-9 在每一列只能出現一次。

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

數獨部分空格內已填入了數字，空白格用 &39; 表示。

示例 1:

輸入:
[
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;]
]
輸出: true

示例 2:

輸入:
[
  [&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
  [&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
  [&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
  [&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
  [&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
  [&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
  [&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
  [&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
  [&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;]
]
輸出: false

解釋: 除了第一行的第一個數字從 5 改為 8 以外，空格內其他數字均與 示例1 相同。

但由於位於左上角的 3x3 宮內有兩個 8 存在, 因此這個數獨是無效的。

說明:
一個有效的數獨（部分已被填充）不一定是可解的。

只需要根據以上規則，驗證已經填入的數字是否有效即可。

給定數獨序列只包含數字 1-9 和字符 &39; 。

給定數獨永遠是 9x9 形式的。

思路

最簡單的思路的是分別循環：判斷行中沒有重複的數字，判斷列中沒有重複的數字，判斷 3 x 3 子數獨沒有重複的數字。

但能不能通過一次循環來實現呢？可以的，我們可以通過三個輔助 Map 來實現。
舉例子：

[
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;],
[&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;,&34;]
]

第0行0列5，記錄 rowMap[05] = 1， colMap[05] = 1， sudokuMap[005] = 1
第0行1列3，記錄 rowMap[03] = 1， colMap[13] = 1， sudokuMap[003] = 1
...
第i行j列N，記錄 rowMap[i + N] = 1， colMap[j + N] = 1， sudokuMap[N/3 + M/3 + N] = 1
當下一項在 rowMap || colMap || sudokuMap 中存在時，表示這不是一個有效的數獨

代碼

/**
* lang=javascript
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function (board) {
let rowMap = {};
let colMap = {};
let sudokuMap = {};

for (let row = 0; row < 9; row++) {
for (let col = 0; col < 9; col++) {
const num = board[row][col];
const rowKey = &39; + row + num;
const colKey = &39; + col + num;
const matrixKey =
&39; +
parseInt(row / 3) +
parseInt(col / 3) +
num;
if (num === &39;) continue;
else if (
rowMap[rowKey] ||
colMap[colKey] ||
sudokuMap[matrixKey]
) {
return false;
} else {
rowMap[rowKey] = 1;
colMap[colKey] = 1;
sudokuMap[matrixKey] = 1;
}
}
}

return true;
};

複雜度分析

時間複雜度：因為數獨固定是9 x 9，循環一次，所以為O(1)。

空間複雜度：使用了額外的Map來記錄，為O(1)。

執行

執行用時：96 ms, 在所有 JavaScript 提交中擊敗了69.25%的用戶。

內存消耗：43.1 MB, 在所有 JavaScript 提交中擊敗了25.92%的用戶。