leetcode 面试经典 150 题：有效的数独

链接	有效的数独
题序号	36
题型	数组
解题方法	双层for循环一次遍历法
难度	中等
熟练度	✅✅✅

题目

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

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

注意：
一个有效的数独（部分已被填充）不一定是可解的。只需要根据以上规则，验证已经填入的数字是否有效即可。空白格用 ‘.’ 表示。

示例 1：
输入：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”]]
输出：true

示例 2：
输入：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”]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与示例1 相同。但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 ‘.’

题解

核心要点：
- 检查每一行：对于数独的每一行，我们需要确保数字1-9只出现一次。我们可以使用一个长度为9的数组（或者集合）来记录每一行中已经出现过的数字。
- 检查每一列：类似地，对于每一列，我们也需要确保数字1-9只出现一次。同样使用一个长度为9的数组（或者集合）来记录每一列中已经出现过的数字。
- 检查每一个3x3宫格：在数独中，有9个3x3的宫格，我们需要确保在每一个宫格内，数字1-9只出现一次。我们可以使用9个长度为9的数组（或者集合）来记录每个宫格中已经出现过的数字。
- 遍历数独板：从左到右，从上到下，遍历数独板上的每一个单元格。对于非空单元格（即不是’.'的单元格），检查其值是否已经在当前行、列或宫格中出现过。如果出现过，则数独无效；否则，将该值添加到当前行、列和宫格的记录中。
- 返回结果：如果遍历完所有单元格后没有发现任何重复，则数独有效；否则，数独无效。
时间复杂度：O(1)。数独共有 81 个单元格，只需要对每个单元格遍历一次即可。
空间复杂度：O(1)。由于数独的大小固定，因此哈希表的空间也是固定的。
c++ 实现算法：

bool isValidSudoku(vector<vector<char>>& board) {vector<unordered_set<char>> rows(9); // 存储每一行的数字vector<unordered_set<char>> cols(9); // 存储每一列的数字vector<unordered_set<char>> boxes(9); // 存储每个 3x3 子区域的数字for (int i = 0; i < 9; ++i) {for (int j = 0; j < 9; ++j) {char num = board[i][j];if (num == '.') continue; //如果当前格子是 '.'（空格），直接跳过。int boxIndex = (i / 3) * 3 + j / 3; // 计算子区域索引，通过该公式计算当前格子属于哪个子区域。// 检查行、列和子区域中是否已经存在该数字if (rows[i].count(num) || cols[j].count(num) || boxes[boxIndex].count(num)) {return false;}// 将数字添加到对应的集合中//rows[i]: 记录数字在第 i 行中出现。// cols[j]: 记录数字在第 j 列中出现。//boxes[boxIndex]: 记录数字在当前子区域中出现。rows[i].insert(num);cols[j].insert(num);boxes[boxIndex].insert(num);}}return true;
}

演示：以示例1为例

/*遍历每个格子
按照 for (i, j) 遍历 9×9 的棋盘。第一步：board[0][0]
当前格子：'5'，属于 第 0 行，第 0 列，左上角子区域。
检查：
rows[0]：空集合，数字 '5' 不存在。
cols[0]：空集合，数字 '5' 不存在。
boxes[0]：空集合，数字 '5' 不存在。
动作：将 '5' 插入：
rows[0] → { '5' }
cols[0] → { '5' }
boxes[0] → { '5' }第二步：board[0][1]
当前格子：'3'，属于 第 0 行，第 1 列，左上角子区域。
检查：
rows[0]：{ '5' }，数字 '3' 不存在。
cols[1]：空集合，数字 '3' 不存在。
boxes[0]：{ '5' }，数字 '3' 不存在。
动作：将 '3' 插入：
rows[0] → { '5', '3' }
cols[1] → { '3' }
boxes[0] → { '5', '3' }第三步：board[0][2]
当前格子：'.'，跳过。第四步：board[0][4]
当前格子：'7'，属于 第 0 行，第 4 列，中间子区域。
检查：
rows[0]：{ '5', '3' }，数字 '7' 不存在。
cols[4]：空集合，数字 '7' 不存在。
boxes[1]：空集合，数字 '7' 不存在。
动作：将 '7' 插入：
rows[0] → { '5', '3', '7' }
cols[4] → { '7' }
boxes[1] → { '7' }第五步：board[1][0]
当前格子：'6'，属于 第 1 行，第 0 列，左上角子区域。
检查：
rows[1]：空集合，数字 '6' 不存在。
cols[0]：{ '5' }，数字 '6' 不存在。
boxes[0]：{ '5', '3' }，数字 '6' 不存在。
动作：将 '6' 插入：
rows[1] → { '6' }
cols[0] → { '5', '6' }
boxes[0] → { '5', '3', '6' }其余步骤
程序继续按顺序遍历，重复检查和插入：遇到 '.' 跳过。
若数字未重复，插入到对应的 rows[i]、cols[j] 和 boxes[boxIndex]。*/

完整c++ demo：

#include <vector>
#include <unordered_set>
#include <iostream>
using namespace std;bool isValidSudoku(vector<vector<char>>& board) {vector<unordered_set<char>> rows(9); // 存储每一行的数字vector<unordered_set<char>> cols(9); // 存储每一列的数字vector<unordered_set<char>> boxes(9); // 存储每个 3x3 子区域的数字for (int i = 0; i < 9; ++i) {for (int j = 0; j < 9; ++j) {char num = board[i][j];if (num == '.') continue; //如果当前格子是 '.'（空格），直接跳过。int boxIndex = (i / 3) * 3 + j / 3; // 计算子区域索引，通过该公式计算当前格子属于哪个子区域。// 检查行、列和子区域中是否已经存在该数字if (rows[i].count(num) || cols[j].count(num) || boxes[boxIndex].count(num)) {return false;}// 将数字添加到对应的集合中//rows[i]: 记录数字在第 i 行中出现。// cols[j]: 记录数字在第 j 列中出现。//boxes[boxIndex]: 记录数字在当前子区域中出现。rows[i].insert(num);cols[j].insert(num);boxes[boxIndex].insert(num);}}return true;
}int main() {vector<vector<char>> 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'}};cout << (isValidSudoku(board) ? "True" : "False") << endl;return 0;
}