LeetCode第36题有效的数独

继续打卡算法题，今天学习的是LeetCode的第36题有效的数独，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。

分析一波题目

这个题目需要遍历二维数组，一维数组好遍历，一层循环就搞定了，二维数组需要两层，由于需要判断3x3宫格内是否有重复数字，这个题目就加大了难度。

因此，我们肯定需要有记录，每一行哪些数字出现过了，每一列哪些数字出现过了，每一个3x3宫格内哪些数字出现过了。他们怎么记录呢？

每一行，每一列，我们可以分别用两个二维数字记录，行的索引记录行数，列索引存储数字，值存储数字出现的次数。

3x3宫格的数字怎么记录呢？

这里有个技巧，我们只要把当前遍历的行，列除3，计算得到一个坐标，定位到3x3宫格的第一位置。

比如第1个3x3格子

a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2] a[2][0] a[2][1] a[2][2]

我们把行，列除3，得到的坐标都是[0,0]

解题核心要点

1、遍历二维数组

2、巧用二维数组记录出现过的数字

3、记录3x3宫格内出现的数字，使用行列坐标除3得到存储位置

编码解决

class Solution {
    public boolean isValidSudoku(char[][] board) {
        //技巧 用3个数组 表示出现次数的数组
        //某1行出现1-9数字的次数
        int[][] rows = new int[9][9];
        //某1列出现1-9数字的次数
        int[][] colums = new int[9][9];
        //某1个9宫格内 1-9数字出现的次数
        int[][][] nightGe = new int[9][9][9];
        for(int i=0;i<board.length; i++) {
            for(int j=0; j<board[0].length; j++) {
                char a = board[i][j];
                if(a != '.') {
                    int index = a-'0'-1;
                    rows[i][index]++;
                    colums[j][index]++;
                    //这里很关键 每相连的3宫格内 不能出现重复的数字
                    // 0 1 2 以内的都存到0这个数组下标位置
                    // 3 4 5 以内的都存到1这个数组下标位置
                    // 6 7 8 以内的都存到2这个数组下标位置
                    nightGe[i/3][j/3][index]++;
                    //判断数字是否已经出现过了，如果出现过了返回false
                    if(rows[i][index] > 1 || colums[j][index] >1 || nightGe[i/3][j/3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

总结

一维数组遍历比较简单，由于二维数字使用比较少，二维数字遍历就比较难了，二维数组通过两层遍历，巧用二维数组记录出现的数字，这个点是比较巧妙的。