36. 有效的数独
难度: 中等
数组
哈希表
矩阵
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
注意:
一个有效的数独(部分已被填充)不一定是可解的。 只需要根据以上规则,验证已经填入的数字是否有效即可。 空白格用 '.' 表示。
示例
解法
分别需要判断每一行/每一列/每一个 3*3 的粗线单元格数字没有重复的数字。
每一行, 使用 row 每一列, 使用 col 每一个 3*3 的粗线单元格, 使用 box
没有重复,使用数组去重后的长度与原始长度对比
整个数独分为 9 个粗线单元格, 下标 0-9
let boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function (board) {
const row = [];
const col = {};
const box = {};
for (let i = 0; i < board.length; i++) {
row[i] = row[i] || [];
for (let j = 0; j < board[i].length; j++) {
col[j] = col[j] || [];
if (board[i][j] !== ".") {
col[j].push(board[i][j]);
row[i].push(board[i][j]);
let boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
box[boxIndex] = box[boxIndex] || [];
box[boxIndex].push(board[i][j]);
}
}
}
const hasRepeat = (data) => {
return Object.values(data).find(
(item) => [...new Set(item)].length !== item.length
);
};
if (hasRepeat(row) || hasRepeat(col) || hasRepeat(box)) {
return false;
}
return true;
};