36. Valid Sudoku

36. Valid Sudokuopen in new window

🟠 🔖 数组 哈希表 矩阵 🔗 LeetCodeopen in new window

题目

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules :

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: 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"]]
Output: true

Example 2:

Input: 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"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or '.'.

题目大意

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

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

解题思路

给出一个数独的棋盘，要求判断这个棋盘当前是否满足数独的要求：即行列是否都只包含 1-9，每个九宫格里面是否也只包含 1-9 。
注意这题和第 37 题是不同的，这一题是判断当前棋盘状态是否满足数独的要求，而第 37 题是要求求解数独。本题中的棋盘有些是无解的，但是棋盘状态是满足题意的。
只需要遍历矩阵，分别判断行列和九宫格内有没有重复的数字即可；
矩阵的数组下标 (i_j) 如下，难点在于如何计算九宫格内元素的下标:
- box[i][j] = board[3 * Math.floor(i / 3) + Math.floor(j / 3)][3 * (i % 3) + (j % 3)]

0_0 0_1 0_2 | 0_3 0_4 0_5 | 0_6 0_7 0_8
1_0 1_1 1_2 | 1_3 1_4 1_5 | 1_6 1_7 1_8
2_0 2_1 2_2 | 2_3 2_4 2_5 | 2_6 2_7 2_8
---------------------------------------
3_0 3_1 3_2 | 3_3 3_4 3_5 | 3_6 3_7 3_8
4_0 4_1 4_2 | 4_3 4_4 4_5 | 4_6 4_7 4_8
5_0 5_1 5_2 | 5_3 5_4 5_5 | 5_6 5_7 5_8
---------------------------------------
6_0 6_1 6_2 | 6_3 6_4 6_5 | 6_6 6_7 6_8
7_0 7_1 7_2 | 7_3 7_4 7_5 | 7_6 7_7 7_8
8_0 8_1 8_2 | 8_3 8_4 8_5 | 8_6 8_7 8_8

代码

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
  for (let i = 0; i < 9; i++) {
    let row = new Set();
    let col = new Set();
    let box = new Set();
    for (let j = 0; j < 9; j++) {
      let _row = board[i][j];
      let _col = board[j][i];
      let _box =
        board[3 * Math.floor(i / 3) + Math.floor(j / 3)][3 * (i % 3) + (j % 3)];

      if (_row != ".") {
        if (row.has(_row)) return false;
        row.add(_row);
      }
      if (_col != ".") {
        if (col.has(_col)) return false;
        col.add(_col);
      }
      if (_box != ".") {
        if (box.has(_box)) return false;
        box.add(_box);
      }
    }
  }
  return true;
};

36. Valid Sudoku

# 36. Valid Sudokuopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

36. Valid Sudokuopen in new window

题目

题目大意

解题思路

代码

相关题目