LeetCode刷题【36】有效的数独

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

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

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

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。

 

示例 1：

输入：board = 
[["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：

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

 

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'

题解，今日 9月17日每日一题

看题面也知道不复杂，就横着统计，竖着统计，小区块统计
然后这个小区块统计的话int blockIdx = (row/3)3 + (col/3);

也不算复杂，找个图画画大概算下应该就能算出来这个关系，

除三取整，再加上一个0到3之间的值，这个值与col有关 当然如果实在想不出来，或者在其他题目中遇到了某种短时间内无法归纳出规律的转换过程，也可以单独写个转换方法，入参就是col和row

逻辑就是

• 如果0 <= row <= 2 并且 0 <= col <= 2 返回0
• 如果0 <= row <= 2 并且 3 <= col <= 5 返回1
• 如果0 <= row <= 2 并且 6 <= col <= 8 返回2
• 如果3 <= row <= 5 并且 0 <= col <= 2 返回3
• 如果3 <= row <= 5 并且 3 <= col <= 5 返回4
• ……

就这么写下去，也不复杂，非常简单直观，不同的复杂情况下，这样写的效率可能比归纳出(row/3)3 + (col/3)这样的逻辑运算过程更快更便捷。

代码如下

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rowCount = new int[9][9];
        int[][] colCount = new int[9][9];
        int[][] blockCount = new int[9][9];

        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == '.'){
                    continue;
                }
//                System.out.println("row:"+row + "  col:"+col);
                int num = board[row][col] - '0' - 1;
                int blockIdx = (row/3)*3 + (col/3);
//                System.out.println("num          ="+(num));
//                System.out.println("blockIdx    ="+blockIdx);
//                System.out.println(Arrays.toString(rowCount[row]));
//                System.out.println(Arrays.toString(colCount[col]));
//                System.out.println(Arrays.toString(blockCount[blockIdx]));
                if (rowCount[row][num] == 1 ||
                        colCount[col][num] == 1 ||
                        blockCount[blockIdx][num] == 1)
                {
//                    System.out.println("已存在");
//                    System.out.println(rowCount[row][num]);
//                    System.out.println(colCount[col][num]);
//                    System.out.println(blockCount[blockIdx][num]);
                    return false;
                }
                rowCount[row][num] = 1;
                colCount[col][num] = 1;
                blockCount[blockIdx][num] = 1;
            }
        }
        return true;
    }
}