LeetCode36-有效的数独

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/valid-sudoku/

中文链接：https://leetcode-cn.com/problems/valid-sudoku/

题目详述

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

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

img

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

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

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:
[
  ["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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入:
[
  ["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 存在, 因此这个数独是无效的。

说明:

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

题目详解

  • 运用三个 boolean 数组 row、col、block 分别代表每一行、每一列和每一个 3x3 宫格。
  • 遍历数独，对于每一个数（不为.），得到在数组中对应的偏移量，即 t = board[i][j] - '1'。
  • 对于行，判断 row[i][t] 是否为 true，为 true 则不合法。
  • 对于列，判断 col[j][t] 是否为 true，为 true 则不合法。
  • 对于宫格，判断 block[k][t] 是否为 true，为 true 则不合法。其中 k = i / 3 * 3 + j / 3。
  • 然后设置三个数组对应位置为 true。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LeetCode_00036 {

    public boolean isValidSudoku(char[][] board) {
        boolean[][] row = new boolean[9][9];  // 代表每一行
        boolean[][] col = new boolean[9][9];  // 代表每一列
        boolean[][] block = new boolean[9][9];  // 代表每个 3x3 宫格
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    int t = board[i][j] - '1';
                    int k = i / 3 * 3 + j / 3;
                    if (row[i][t] || col[j][t] || block[k][t]) {
                        return false;
                    }
                    row[i][t] = true;
                    col[j][t] = true;
                    block[k][t] = true;
                }
            }
        }
        return true;
    }
}
  • 可以将上面的三个 boolean 数组改为三个 int 数组。
  • 运用位运算将数组映射到对应的二进制位来判断是否出现过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode_00036 {

    public boolean isValidSudoku(char[][] board) {
        int[] row = new int[9];  // 代表每一行
        int[] col = new int[9];  // 代表每一列
        int[] block = new int[9];  // 代表每个 3x3 宫格
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    // 映射到对应的二进制位
                    int t = 1 << (board[i][j] - '1');
                    int k = i / 3 * 3 + j / 3;
                    if ((row[i] & t) != 0 || (col[j] & t) != 0 || (block[k] & t) != 0) {
                        return false;
                    }
                    row[i] |= t;
                    col[j] |= t;
                    block[k] |= t;
                }
            }
        }
        return true;
    }
}