有效的数独

一.题目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(vectorvectorchar 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]获取当前字符num board[i][j]。如果num .则跳过继续处理下一个格子。否则将字符转换为整数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)值。