36. 有效的数独

真正的才智是刚毅的志向。 ——拿破仑。

参考36. 有效的数独。

题目

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

1. 数字 1-9 在每一行只能出现一次。

2. 数字 1-9 在每一列只能出现一次。

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

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。

• 只需要根据以上规则，验证已经填入的数字是否有效即可。

• 空白格用 '.' 表示。
  

  数独

解题思路

• 枚举：枚举数独时判断对应三条规则是否满足。

枚举

class Solution {
    public boolean isValidSudoku(char[][] board) {
        
        for(int i = 0; i < 9; i++) {
            int[] count = new int[9];
            int[] count2 = new int[9];
            for(int j = 0; j < 9; j++) {
                // 数字 1-9 在每一行只能出现一次。
                if(board[i][j]!='.' && count[board[i][j]-'1']++ == 1) return false;
                // 数字 1-9 在每一列只能出现一次。
                if(board[j][i]!='.' && count2[board[j][i]-'1']++ == 1) return false;
                //数字 1-9 在每一个 3x3 宫内只能出现一次。
                if(i%3 == 0 && j%3 == 0) {
                    int[] count3 = new int[9];
                    for(int m = i;m < i+3;m++) {
                        for(int n = j;n < j+3;n++) {
                            if(board[m][n] == '.') continue;
                            if(count3[board[m][n]-'1']++ == 1) return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：O(1)，数独长度为9*9=81固定。
• 空间复杂度：O(1)，使用空间为9固定。

2023.05.07