36. Valid Sudoku

Leetcode link

题目简介

/**
 * @param {character[][]} board
 * @return {boolean}
 */

题目给我们一个 9*9 的格子组成的数独棋盘

要求我们分析当前填入的数字是否符合数独规则：

1. 当前行只包含一个 1～9 的数字
2. 当前列只包含一个 1～9 的数字
3. 当前 3*3 的格子只包含一个 1～9 的数字

解题思路

这题需要我们遍历所有格子然后分别对比三个规则判断

为了减少计算量，我们可以用三个 9*9 的二位数组分别来保存三个规则下，当前遍历的数字是否被用过了

如果在后续遍历过程中，发现当前遍历的数字在之前被用上了，就表示重复了，需要返回 false

如果遍历完成所有格子都没有重复的，则返回 true

Javascript

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
    const len = board.length
    const row = Array.from({ length: len }, _ => new Array(len).fill(false))
    const col = Array.from({ length: len }, _ => new Array(len).fill(false))
    const box = Array.from({ length: len }, _ => new Array(len).fill(false))

    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            if(board[i][j] === '.') {
                continue
            }

            const boxIdx = Math.floor(i / 3) * 3 + Math.floor(j / 3)
            const num = board[i][j] - '1'

            if(row[i][num] || col[j][num] || box[boxIdx][num]) {
                // if the num has already existed
                return false
            }

            row[i][num] = col[j][num] = box[boxIdx][num] = true
        }
    }
    return true
};