020-有效的数独 (Valid Sudoku)

题目描述

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

示例

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

解题思路

使用哈希表分别检查每一行、每一列和每一个3x3宫格是否有重复数字。对于每个数字，检查它是否在对应的行、列、宫格中已经出现过。

JavaScript 解决方案

/**
 * @param {character[][]} board
 * @return {boolean}
 */
const isValidSudoku = (board) => {
    const rows = new Array(9).fill().map(() => new Set());
    const cols = new Array(9).fill().map(() => new Set());
    const boxes = new Array(9).fill().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;
            
            // 检查行
            if (rows[i].has(num)) return false;
            rows[i].add(num);
            
            // 检查列
            if (cols[j].has(num)) return false;
            cols[j].add(num);
            
            // 检查3x3宫格
            const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
            if (boxes[boxIndex].has(num)) return false;
            boxes[boxIndex].add(num);
        }
    }
    
    return true;
};

复杂度分析

时间复杂度：O(1)，因为数独大小固定为9x9
空间复杂度：O(1)，使用了固定大小的哈希表

测试用例

// 测试函数
const testIsValidSudoku = () => {
    const testCases = [
        {
            board: [
                ["5","3",".",".","7",".",".",".","."],
                ["6",".",".","1","9","5",".",".","."],
                [".","9","8",".",".",".",".","6","."],
                ["8",".",".",".","6",".",".",".","3"],
                ["4",".",".","8",".","3",".",".","1"],
                ["7",".",".",".","2",".",".",".","6"],
                [".","6",".",".",".",".","2","8","."],
                [".",".",".","4","1","9",".",".","5"],
                [".",".",".",".","8",".",".","7","9"]
            ],
            expected: true
        },
        {
            board: [
                ["8","3",".",".","7",".",".",".","."],
                ["6",".",".","1","9","5",".",".","."],
                [".","9","8",".",".",".",".","6","."],
                ["8",".",".",".","6",".",".",".","3"],
                ["4",".",".","8",".","3",".",".","1"],
                ["7",".",".",".","2",".",".",".","6"],
                [".","6",".",".",".",".","2","8","."],
                [".",".",".","4","1","9",".",".","5"],
                [".",".",".",".","8",".",".","7","9"]
            ],
            expected: false
        },
        {
            board: [
                [".",".",".",".","5",".",".","1","."],
                [".","4",".","3",".",".",".",".","."],
                [".",".",".",".",".","3",".",".","1"],
                ["8",".",".",".",".",".",".","2","."],
                [".",".","2",".","7",".",".",".","."],
                [".","1","5",".",".",".",".",".","."],
                [".",".",".",".",".","2",".",".","."],
                [".","2",".","9",".",".",".",".","."],
                [".",".","4",".",".",".",".",".","."]
            ],
            expected: true
        }
    ];

    testCases.forEach((testCase, index) => {
        const result = isValidSudoku(testCase.board);
        const passed = result === testCase.expected;
        console.log(`测试用例 ${index + 1}: ${passed ? '通过' : '失败'}`);
        console.log(`输入: board = [${testCase.board.map(row => `[${row.join(',')}]`).join(', ')}]`);
        console.log(`期望: ${testCase.expected}, 实际: ${result}\n`);
    });
};

// 运行测试
testIsValidSudoku();

关键点总结

哈希表使用：使用Set来检查重复数字
宫格计算：使用公式计算3x3宫格的索引
跳过空格：忽略'.'字符
同时检查：对每个数字同时检查行、列、宫格
边界处理：数独大小固定为9x9

总结

这道题考察了以下重点：

哈希表应用：如何使用哈希表检查重复元素
二维数组处理：如何高效地遍历二维数组
数学计算：如何计算3x3宫格的索引
边界处理：对固定大小数组的处理

哈希表法是最优解，时间复杂度为 O(1)，空间复杂度为 O(1)。在实际面试中，建议先理解数独的规则，然后实现检查算法。

020-有效的数独 (Valid Sudoku)

On this page