代码训练LeetCode(43)有效的数独

代码训练(43)有效的数独

Author: Once Day Date: 2025年7月2日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

• 3. 无重复字符的最长子串 - 力扣（LeetCode）
• 力扣 (LeetCode) 全球极客挚爱的技术成长平台

文章目录

• • • 代码训练(43)有效的数独
    • • 1. 原题
      • 2. 分析
      • 3. 代码实现
      • 4. 总结

1. 原题

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

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 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 存在, 因此这个数独是无效的。

2. 分析

数独是一个经典的逻辑排列游戏，通常由一个9x9的网格组成。在这个问题中，我们需要验证一个给定的9x9数独是否符合以下条件：

1. 每一行中，数字1-9必须唯一出现。
2. 每一列中，数字1-9必须唯一出现。
3. 每个3x3的小格子中，数字1-9必须唯一出现。

为了验证数独的有效性，我们可以采用以下步骤：

分析步骤：

1. 初始化数据结构：为每一行、每一列和每一个3x3的块创建一个数组（或哈希表），用于记录数字的出现情况。
2. 遍历数独，逐个检查数独中的每个单元格。
   • 对于每个数字，更新对应行、列和块的记录。
   • 如果在任何行、列或块中发现重复数字，则立即返回无效。
3. 完成遍历：如果没有发现任何重复，那么数独有效。

考虑以下数独布局：

5 3 . | . 7 . | . . .6 . . | 1 9 5 | . . .. 9 8 | . . . | . 6 .------+------+------8 . . | . 6 . | . . 34 . . | 8 . 3 | . . 17 . . | . 2 . | . . 6------+------+------. 6 . | . . . | 2 8 .. . . | 4 1 9 | . . 5. . . | . 8 . | . 7 9

在第一个3x3块中，数字5、3、6、9、8是有效的。

继续检查其他行、列和块。

性能优化关键点：

• 数据结构选择：使用长度为9的布尔数组（或位图）来跟踪每行、每列和每个块的数字出现情况，这可以减少内存使用并提高访问速度。
• 一次遍历：整个数独只遍历一次，同时更新行、列和块的状态，这提高了效率。

3. 代码实现

#include bool isValidSudoku(char** board, int boardSize, int* boardColSize) { bool row[9][9] = {false}, col[9][9] = {false}, block[9][9] = {false}; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] != \'.\') { int num = board[i][j] - \'1\'; // 数字1-9转换为索引0-8 int blockIndex = (i / 3) * 3 + (j / 3); if (row[i][num] || col[j][num] || block[blockIndex][num]) {  return false; } row[i][num] = col[j][num] = block[blockIndex][num] = true; } } } return true;}

4. 总结

这个题目考察了数组的使用、布尔逻辑及简单的算法思维。通过这类问题，可以增强对基本数据结构的理解和操作能力。要提升编程能力，建议多练习类似的逻辑判断和数组操作题目，以锻炼思维和编程技巧。