LC36. 有效的数独（第16题）

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

菜鸟就要从第16题继续

一、题目描述：

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。（请参考示例图）
 

注意：

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

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/va…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路分析：

其实这个题的总体思路是很清晰，就是遍历一遍，然后在每个遍历的同时分别统计它在所属的横、纵、方块区中是否有相同数值。统计一方面可以用数组，每个位置一个值，存在就加1，判断是否超过1。或者就是用set，看里面是否已经有了这个值。这道题的难点在于数组、map的声明，动态的赋值读取等。

数组：注意js的数组声明要一层一层的，其次在index处的处理，采用charCodeAt()方法来获取可返回指定位置的字符的Unicode编码，与0的unicode相减获取差值。

对象：利用对象管理，注意数据的储存与读取rows[i + ‘-‘ + num]，还有对方块部分序列的处理，按照从左到右从上到下的顺序分为9个boxIndex = parseInt(i / 3) * 3 + parseInt(j / 3);

map：通过循环声明3个数组，27个map，然后依次操作，方块部分的序号同上。

parseInt() 函数可解析一个字符串，并返回一个整数。

三、AC 代码：

1、数组

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
    const rows = new Array(9).fill(0).map(() => new Array(9).fill(0));
    const columns = new Array(9).fill(0).map(() => new Array(9).fill(0));
    const subboxes = new Array(3).fill(0).map(() => new Array(3).fill(0).map(() => 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 !== '.') {
                const index = c.charCodeAt() - '0'.charCodeAt() - 1;
                rows[i][index]++;
                columns[j][index]++;
                subboxes[Math.floor(i / 3)][Math.floor(j / 3)][index]++;
                if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[Math.floor(i / 3)][Math.floor(j / 3)][index] > 1) {
                    return false;
                }
            }
        }
    }
    return true;
};
复制代码

2、对象

/**
 * @param {character[][]} board
 * @return {boolean}
 */
const isValidSudoku = board => {
    const [rows, columns, boxes] = [{}, {}, {}];
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const num = board[i][j];
            if (num !== '.') {
                const boxIndex = parseInt(i / 3) * 3 + parseInt(j / 3);
                if (rows[i + '-' + num] || columns[j + '-' + num] || boxes[boxIndex + '-' + num]) {
                    return false;
                }
                rows[i + '-' + num] = true;
                columns[j + '-' + num] = true;
                boxes[boxIndex + '-' + num] = true;
            }
        }
    }
    return true;
};
复制代码

3、map

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
let rows = []
let cols = []
let box = []
for (let i = 0; i < 9; i++) {
    rows[i] = new Map()
    cols[i] = new Map()
    box[i] = new Map()
}
for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
        if (board[i][j] !== '.') {
            // 获取数字所在子数组的序号
            let s = parseInt(i / 3) * 3 + parseInt(j / 3) 
            if (rows[i].has(board[i][j]) || cols[j].has(board[i][j]) || box[s].has(board[i][j]))
                return false
            else {
                rows[i].set(board[i][j], 1)
                cols[j].set(board[i][j], 1)
                box[s].set(board[i][j], 1)
            }
        }
    }
}
return true
};

复制代码