Skip to content

Latest commit

 

History

History
162 lines (137 loc) · 5.12 KB

0036.md

File metadata and controls

162 lines (137 loc) · 5.12 KB
Raw
title description keywords
36. 有效的数独
LeetCode,36. 有效的数独,有效的数独,Valid Sudoku,解题思路,数组,哈希表,矩阵
LeetCode
36. 有效的数独
有效的数独
Valid Sudoku
解题思路
数组
哈希表
矩阵

36. 有效的数独

🟠 Medium  🔖  数组 哈希表 矩阵  🔗 力扣 LeetCode

题目

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

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. 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. 数字  1-9  在每一行只能出现一次。
  2. 数字  1-9  在每一列只能出现一次。
  3. 数字  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;
};

相关题目

题号 标题 题解 标签 难度
37 解数独 [✓] 数组 哈希表 回溯 1+ Hard
2133 检查是否每一行每一列都包含全部整数 数组 哈希表 矩阵 Easy