企业官网建设流程全解析

LeetCode 36. 有效的数独 — TypeScript 实现

思路

与 Rust 版本完全一致，利用三个二维数组分别记录行、列、3×3 宫中每个数字是否已出现，一次遍历完成校验。

代码

function isValidSudoku(board: string[][]): boolean {
// rows[i][d] 表示第 i 行数字 d 是否已出现
const rows: boolean[][] = Array.from({ length: 9 }, () => Array(9).fill(false));
const cols: boolean[][] = Array.from({ length: 9 }, () => Array(9).fill(false));
const boxes: boolean[][] = Array.from({ length: 9 }, () => Array(9).fill(false));

for (let i = 0; i < 9; i++) { for (let j = 0; j < 9; j++) { const c = board[i][j]; if (c === '.') { continue; } const digit = parseInt(c, 10) - 1; // 0~8 const boxIdx = Math.floor(i / 3) * 3 + Math.floor(j / 3); // 0~8 if (rows[i][digit] || cols[j][digit] || boxes[boxIdx][digit]) { return false; } rows[i][digit] = true; cols[j][digit] = true; boxes[boxIdx][digit] = true; } } return true

}

关键点

要点 说明
数字映射
“parseInt© - 1”，将
“‘1’~‘9’” 转为
“0~8” 下标
宫的编号
“Math.floor(i / 3) * 3 + Math.floor(j / 3)”
数组初始化
“Array.from({ length: 9 }, () => Array(9).fill(false))” 避免引用同一数组
时间复杂度 O(1)，固定 81 格
空间复杂度 O(1)，固定 3×9×9

常见陷阱

1. 数组浅拷贝：如果用
   “Array(9).fill(Array(9).fill(false))”，所有行会引用同一个数组，修改一行会影响所有行。务必用
   “Array.from” 逐行创建。
2. 字符转数字：
   “board[i][j]” 是字符串，需要用
   “parseInt(c, 10) - 1” 或
   “c.charCodeAt(0) - ‘1’.charCodeAt(0)” 转换。
3. 跳过空白：遇到
   “‘.’” 直接
   “continue”，不参与校验。

替代方案（位运算优化）

如果对空间极致追求，可以用
“number” 的位掩码代替布尔数组：

function isValidSudoku(board: string[][]): boolean {
const rows = new Array(9).fill(0);
const cols = new Array(9).fill(0);
const boxes = new Array(9).fill(0);

for (let i = 0; i < 9; i++) { for (let j = 0; j < 9; j++) { const c = board[i][j]; if (c === '.') continue; const mask = 1 << (parseInt(c, 10) - 1); const boxIdx = Math.floor(i / 3) * 3 + Math.floor(j / 3); if ((rows[i] & mask) || (cols[j] & mask) || (boxes[boxIdx] & mask)) { return false; } rows[i] |= mask; cols[j] |= mask; boxes[boxIdx] |= mask; } } return true

}

位运算版本将空间从 3×81 个布尔值压缩到 27 个整数，逻辑完全一致，性能略优。