有效的数独

[Cosen95]

leetcode: https://leetcode-cn.com/problems/valid-sudoku/

[Cosen95]

思路分析

首先，这道题目通过两层遍历就可以解决。我们先初始化三个变量：

• rows: 存放1-9横排的值
• columns: 存放1-9竖排的值
• boxes: 存放9个小九宫格的值

接下来就是两层遍历，进行对比：rows[i] 存放对应横坐标的值，columns[j] 存放对应纵坐标的值，boxes[boxIndex] 存放对应小盒子的值。关键就是这里的boxIndex怎么取？

我们再来看一下题目，这里用一下leetcode官方题解中的一张图：

不难得出如下的表格，对应就是boxIndex的取值：

+0	0	1	2
+3	3	4	5
+6	6	7	8

假设我们确定了第一排可以通过 Math.floor(j / 3) 来控制（加粗字体），那么我们第二排和第三排理应在第一排的基础上 + 3。

而恰巧 Math.floor(i / 3) * 3 即可得到对应相加值：

• 0/1/2：+0
• 3/4/5：+3
• 6/7/8：+6

这样刚好就对应到 boxes[Math.floor(i / 3) * 3 + Math.floor(j / 3) ]

代码实现

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
    // 初始化横、竖以及小九宫格
    const rows = [], columns = [], boxes = []
    for (let i = 0; i < 9; i++) {
        rows[i] = []
        columns[i] = []
        boxes[i] = []
    }

    for(let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            // 依次判断横、竖以及小九宫格
            const value = board[i][j]
            // 比较非 . 元素
            if (value !== '.') {
                // 检查横排
                if(!rows[i].includes(value)) {
                    rows[i].push(value)
                } else {
                    return false
                }

                // 检查竖排
                if(!columns[j].includes(value)) {
                    columns[j].push(value)
                } else {
                    return false
                }

                // 检查小九宫格
                // 拆分为9个小九宫格，对应下标的处理和获取是本题的解题关键
                const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3)
                if(!boxes[boxIndex].includes(value)) {
                    boxes[boxIndex].push(value)
                } else {
                    return false
                }
            }
        }
    }
    // 默认返回true
    return true
};