64 lines
1.7 KiB
JavaScript
64 lines
1.7 KiB
JavaScript
/**
|
|
* https://leetcode.cn/problems/valid-sudoku/?envType=study-plan-v2&envId=top-interview-150
|
|
* @param {character[][]} board
|
|
* @return {boolean}
|
|
*/
|
|
const isValidSudoku = function (board) {
|
|
return f1(board);
|
|
};
|
|
|
|
function f1(board) {
|
|
const rows = Array(9).fill(null).map(() => new Set());
|
|
const cols = Array(9).fill(null).map(() => new Set());
|
|
const boxes = Array(9).fill(null).map(() => new Set());
|
|
|
|
for (let i = 0; i < 9; i++) {
|
|
for (let j = 0; j < 9; j++) {
|
|
const num = board[i][j];
|
|
if (num === '.') continue; // 空格跳过
|
|
|
|
const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3); // 计算所在的3x3子格的索引
|
|
|
|
// 检查当前数字是否已经出现过
|
|
if (rows[i].has(num) || cols[j].has(num) || boxes[boxIndex].has(num)) {
|
|
return false;
|
|
}
|
|
|
|
// 将当前数字加入对应的set中
|
|
rows[i].add(num);
|
|
cols[j].add(num);
|
|
boxes[boxIndex].add(num);
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
function f2(board) {
|
|
// 使用位运算加速
|
|
const rows = Array(9).fill(0);
|
|
const cols = Array(9).fill(0);
|
|
const block = Array(9).fill(0);
|
|
|
|
for (let i = 0; i < 9; i++) {
|
|
for (let j = 0; j < 9; j++) {
|
|
if (board[i][j] === '.') continue;
|
|
|
|
const x = board[i][j] - '0'; // 转换字符为数字
|
|
const blockIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3); // 计算所在的3x3子格的索引
|
|
|
|
// 检查当前数字是否已经出现过
|
|
if ((rows[i] >> x & 1) || (cols[j] >> x & 1) || (block[blockIndex] >> x & 1)) {
|
|
return false;
|
|
}
|
|
|
|
// 使用位运算设置当前数字已出现
|
|
rows[i] |= 1 << x;
|
|
cols[j] |= 1 << x;
|
|
block[blockIndex] |= 1 << x;
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|