企业官网建设流程全解析

一.题目

36. 有效的数独 - 力扣（LeetCode）

二.思路讲解

2.1 审题

数独的规则很简单：在9×9的棋盘上，每一行、每一列以及每一个3×3的九宫格内，数字1-9只能出现一次。题目要求我们判断给定的部分填充棋盘是否满足这些规则（空白用'.'表示）。由于需要快速判断某个数字是否在对应区域出现过，很自然地会想到用哈希表来记录。

2.2 思路讲解

我们需要分别检查行、列和九宫格，因此可以用三个二维布尔数组（或哈希表）来记录数字是否已出现：

• 行：row[9][10]，row[i][num]表示第i行中数字num是否已经出现过。

• 列：col[9][10]，col[j][num]表示第j列中数字num是否已经出现过。

• 九宫格：九宫格有 9 个，每个格子可用(i/3, j/3)定位。

遍历整个棋盘，对于每个非'.'的数字num，分别检查在对应行、列、宫中是否已被标记：

• 如果任一已标记，则返回false。

• 否则，将三个位置都标记为已出现。

三.代码演示

class Solution { public: int row[9][10];//行 int col[9][10];//列 int grid[3][3][10];//九宫格 bool isValidSudoku(vector<vector<char>>& board) { for(int i = 0;i < 9;i++) { for(int j = 0;j < 9;j++) { char num = board[i][j];//获取一个格子的元素 //看是不是数字 if(num != '.') { if(row[i][num - '0'] || col[j][num - '0'] || grid[i/3][j/3][num - '0']) { return false; } row[i][num - '0'] = col[j][num - '0'] = grid[i/3][j/3][num - '0'] = 1;//表示存在 } } } return true; } };

四.代码讲解

一、数据结构设计

由于数独棋盘固定为 9×9，且数字范围是 1-9，我们可以用三个三维数组来模拟哈希表，记录每个数字在行、列、九宫格中的出现情况：

• row[9][10]：row[i][num]表示第i行中数字num是否已经出现过（1 表示出现过，0 表示未出现）。第二维大小为 10，是为了让下标直接对应数字 1-9（索引 0 闲置）。

• col[9][10]：同理，col[j][num]表示第j列中数字num是否出现过。

• grid[3][3][10]：grid[gx][gy][num]表示第(gx, gy)个 3×3 宫中数字num是否出现过。九宫格的编号通过行下标i/3和列下标j/3确定，范围均为 0-2。

二、遍历棋盘

使用两层for循环遍历整个 9×9 棋盘，依次处理每个格子board[i][j]：

1. 获取当前字符num = board[i][j]。

2. 如果num == '.'，则跳过，继续处理下一个格子。

3. 否则，将字符转换为整数d = num - '0'（注意字符 '0' 到 '9' 的 ASCII 转换）。

三、检查冲突

在放置数字之前，需要检查该数字是否已经在当前行、当前列、当前宫中出现过：

• row[i][d]：当前行是否已存在该数字

• col[j][d]：当前列是否已存在该数字

• grid[i/3][j/3][d]：当前九宫格是否已存在该数字

如果三者中任意一个为1，说明发生了重复，数独无效，直接返回false。

四、标记已出现

如果未冲突，则将这三个位置都标记为1，表示该数字已被使用：

row[i][d] = col[j][d] = grid[i/3][j/3][d] = 1;

五、关键细节

• 数组下标设计：row[9][10]中第二维大小为 10，是为了直接用d作为下标，避免d-1的转换，使代码更直观。

• 九宫格定位：i/3和j/3的整除运算将 0-8 的行/列映射到 0-2 的宫索引。例如，第 0、1、2 行都对应宫行 0，第 3、4、5 行对应宫行 1，以此类推。同一宫内的格子具有相同的(i/3, j/3)值。