Leaky Cauldron
0%

有效的数独

Posted on Edited on

题目(LeetCode #36)

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

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

下图是一个部分填充的有效的数独。

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

示例1：

输入：

1
2
3
4
5
6
7
8
9
10
11
[
    ["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"]
]

输出：

1
true

示例2：

输入：

1
2
3
4
5
6
7
8
9
10
11
[
    ["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"]
]

输出：

1
false

解释： 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明：

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。
  • 给定数独序列只包含数字 1-9 和字符 ‘.’ 。
  • 给定数独永远是 9x9 形式的。

题解

参考题解

遍历 9 x 9 的数独，确保其满足：

  • 同一行中无重复数字
  • 同一列中无重复数字
  • 每个 3 x 3 的子数独中无重复数字

这三个条件可在一次迭代中完成，难点在于如何枚举子数独。

子数独的索引可通过 (row / 3) * 3 + column / 3 算得，其中 / 为整除（我也不知道别人是怎么想到的🙃）。

而判断是否有重复项可通过 Map 来判断，其中 key 为数字，value 为出现次数，在此使用二维数组来存储对应关系。

复杂度

由于单元格数量确定，始终为 81 个，故时间复杂度和空间复杂度均为 O(1) 。

实现

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] columns = new int[9][9];
        int[][] boxes = new int[9][9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char num = board[i][j];
                if (num == '.') continue;
                int n = num - '1';
                int box_index = (i / 3) * 3 + j / 3;

                rows[i][n] = rows[i][n] + 1;
                columns[j][n] = columns[j][n] + 1;
                boxes[box_index][n] = boxes[box_index][n] + 1;

                if (rows[i][n] > 1 || columns[j][n] > 1 || boxes[box_index][n] > 1)
                    return false;
            }
        }

        return true;
    }

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def isValidSudoku(self, board: list) -> bool:
        rows = [[0 for i in range(9)] for i in range(9)]
        columns = [[0 for i in range(9)] for i in range(9)]
        boxes = [[0 for i in range(9)] for i in range(9)]

        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num == '.': continue
                num = int(num) - 1
                box_index = (i // 3) * 3 + j // 3

                rows[i][num] += 1
                columns[j][num] += 1
                boxes[box_index][num] += 1

                if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                    return False

        return True

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func isValidSudoku(board [][]byte) bool {
    rows := [9][9]int{}
    columns := [9][9]int{}
    boxes := [9][9]int{}

    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            num := board[i][j]
            if num == '.' {
                continue
            }
            boxIndex := (i/3)*3 + j/3
            num = num - '1'
            rows[i][num]++
            columns[j][num]++
            boxes[boxIndex][num]++

            if rows[i][num] > 1 || columns[j][num] > 1 || boxes[boxIndex][num] > 1 {
                return false
            }
        }
    }

    return true
}