企业网站改版计划书,中交上航建设网站,我要招聘员工在哪里找招得快,全自动精准引流软件这段代码解决的是 验证一个数独是否有效 的问题#xff0c;其算法思想是基于 规则校验和状态记录。具体思想如下#xff1a; 算法思想 核心目标#xff1a; 检查每个数字在 同一行、同一列 和 同一个 3x3 子格 中是否重复。 状态记录#xff1a; 使用 3 个布尔二维数组分别…
这段代码解决的是 验证一个数独是否有效 的问题其算法思想是基于 规则校验和状态记录。具体思想如下 算法思想 核心目标 检查每个数字在 同一行、同一列 和 同一个 3x3 子格 中是否重复。 状态记录 使用 3 个布尔二维数组分别记录 每行数字的出现情况 rows[i][num]。每列数字的出现情况 cols[j][num]。每个 3x3 子格数字的出现情况 boxes[boxIndex][num]。 通过这些状态数组可以快速检查某个数字是否在对应位置已存在。 遍历与验证 遍历整个 9x9 的数独表格对于每一个非空格的数字 计算数字对应的行、列和 3x3 子格索引。检查当前数字是否在对应行、列或 3x3 子格中已存在。如果存在直接返回 false表示数独无效。如果不存在将该数字标记为已出现更新状态数组。 如果遍历完成未发现冲突返回 true表示数独有效。 算法步骤
1. 初始化数据结构
定义三个布尔二维数组rows[9][9], cols[9][9], boxes[9][9]。 rows[i][num]: 记录第 i 行中数字 num1 是否已经出现。cols[j][num]: 记录第 j 列中数字 num1 是否已经出现。boxes[boxIndex][num]: 记录第 boxIndex 个 3x3 子格中数字 num1 是否已经出现。
2. 遍历整个数独表格
对于每个位置 (i, j) 如果是空格.直接跳过。将字符数字转换为整数索引 num如字符 5 转换为整数 4因为数组索引从 0 开始。计算数字所属的 3x3 子格索引boxIndex (i / 3) * 3 j / 3。 行和列分别除以 3 取整可以确定当前数字在哪一块 3x3 子格中。
3. 检查并标记状态
检查状态数组 如果 rows[i][num] true说明第 i 行已经出现过数字 num1。如果 cols[j][num] true说明第 j 列已经出现过数字 num1。如果 boxes[boxIndex][num] true说明该 3x3 子格已经出现过数字 num1。 如果任何一项为 true直接返回 false。否则更新状态数组将当前数字标记为已出现。
4. 返回结果
如果遍历完成未发现任何冲突则返回 true表示数独有效。 关键点说明
1. 如何定位到 3x3 子格
整个数独分为 9 个 3x3 子格子格索引
0 1 2
3 4 5
6 7 8每个数字的位置 (i, j) 通过公式 (i / 3) * 3 j / 3 定位到对应的子格索引。
2. 字符数字如何转换为数组索引
数独中数字以字符形式存储例如 5。将其转为整数索引num board[i][j] - 1。 1 转换为索引 09 转换为索引 8。
3. 为什么需要状态数组
状态数组是为了快速记录和检查数字的存在性。使用布尔值记录 true 或 false可以节省时间复杂度相较于遍历行、列和子格的直接检查更加高效。 时间和空间复杂度分析 时间复杂度 遍历整个 9x9 表格时间复杂度为 (O(9 \times 9) O(81))即常数级复杂度。 空间复杂度 使用了 3 个 9x9 的布尔数组总空间为 (3 \times 9 \times 9 O(243))即常数级复杂度。 总结
通过 遍历整个数独表格 和 使用状态数组记录数字的出现情况有效避免了重复检查算法逻辑清晰且高效。算法充分利用了布尔数组在快速状态查询和标记上的优势实现了对数独规则的校验。
class Solution {public boolean isValidSudoku(char[][] board) {boolean [][] rows new boolean[9][9]; //rows[i][num]表示第i行是否出现过numboolean [][] cols new boolean[9][9]; //cols[j][num]表示第j列是否出现过numboolean [][] boxes new boolean[9][9]; //boxes[boxindex][num]表示第boxindex个3*3方格中是否出现过numfor(int i 0; i 9; i) {for(int j 0; j 9; j) {//首先跳过空格if(board[i][j] .) {continue;}//首先获取boxindexint boxindex (i / 3) * 3 (j / 3);//将字符数字转换为索引int num board[i][j] - 1;if(rows[i][num] || cols[j][num] || boxes[boxindex][num]) {return false;}//然后标记rows[i][num] true;cols[j][num] true;boxes[boxindex][num] true;}}return true;}
}
