LeetCode-36-有效的数独
in LeetCode with 0 comment
哈希表

LeetCode-36-有效的数独

in LeetCode with 0 comment

哈希表

原题地址：有效的数独

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

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

250px-Sudoku-by-L2G-20050714.svg 上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:

输入:
[
  ["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

示例 2:

输入:
[
  ["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 存在, 因此这个数独是无效的。

说明:

解答

根据规则，我们需要判断每一个填写的数字在对应的行、列及小九宫格上是否有重复。我们可以用Set来记录数字的每一次出现并判断是否有重复：

/**
 * @param {string[][]} board
 * @return {boolean}
 */
const isValidSudoku1 = function(board) {
    // 对每一行、每一列及每一个小九宫格分别用一个Set来记录出现过的数字
    let columnSets = new Array(board.length);
    let rowSets = new Array(board.length);
    let boxSets = new Array(board.length);
    for (let i = 0; i < board.length; i ++) {
        columnSets[i] = new Set();
        rowSets[i] = new Set();
        boxSets[i] = new Set();
    }
    for (let i = 0; i < board.length; i ++) {
        for (let j = 0; j < board.length; j ++) {
            // 还没有填的格子不用处理
            if (board[i][j] === '.') {
                continue;
            }
            // 填过的格子需要分别判断该数字在对应的行、列及小九宫中是否出现过
            // 出现过就返回false，否则把这一次的出现记录到对应的行、列及小九宫Set中
            if (columnSets[i].has(board[i][j])) {
                return false;
            }
            columnSets[i].add(board[i][j]);
            if (rowSets[j].has(board[i][j])) {
                return false;
            }
            rowSets[j].add(board[i][j]);
	    // 对应小九宫的序号
            let boxIndex = Math.floor(i/3)*3+Math.floor(j/3);
            if (boxSets[boxIndex].has(board[i][j])) {
                return false;
            }
            boxSets[boxIndex].add(board[i][j]);
        }
    }
    return true;
};

测试：

let start = new Date();
const test = isValidSudoku1;
console.log(test([
    ["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
console.log(test([
    ["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
console.log(new Date().getTime() - start.getTime()); // 10

时间复杂度： 只需要一次遍历，时间复杂度为$O(9^2)=O(1)$
空间复杂度： 需要三个辅助数组，空间复杂度为$O(3 \times 9^2)=O(1)$

本文由 李海平 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 5,2019

← → ↓ ↑