力扣面试经典——36题

💡 参考代码：

/**
 * 验证9x9数独是否有效
 * 
 * 验证规则：
 * 1. 数字1-9在每一行只能出现一次
 * 2. 数字1-9在每一列只能出现一次
 * 3. 数字1-9在每个3x3宫格内只能出现一次
 * 
 * @param board 9x9的字符数组，代表数独棋盘
 * @param boardSize 棋盘行数（应为9）
 * @param boardColSize 每行的列数数组
 * @return bool 如果数独有效返回true，否则返回false
 */
bool isValidSudoku(char** board, int boardSize, int* boardColSize) {
    // 使用三个二维数组分别记录行、列、3x3宫格中数字的出现情况
    // rows[i][num]: 第i行中数字num+1是否已出现
    // cols[j][num]: 第j列中数字num+1是否已出现
    // boxes[boxIndex][num]: 第boxIndex个3x3宫格中数字num+1是否已出现
    int rows[9][9] = {0};
    int cols[9][9] = {0};
    int boxes[9][9] = {0};
    
    // 遍历整个数独棋盘
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            // 如果当前格子不是空格
            if (board[i][j] != '.') {
                // 将字符转换为数字（1-9）
                int num = board[i][j] - '1';
                
                // 计算当前格子所属的3x3宫格索引
                // 每个3x3宫格的索引计算公式：(行号/3)*3 + 列号/3
                int boxIndex = (i / 3) * 3 + j / 3;
                
                // 检查该数字是否已在当前行、列或宫格中出现过
                if (rows[i][num] || cols[j][num] || boxes[boxIndex][num]) {
                    // 如果出现过，说明数独无效
                    return false;
                }
                
                // 标记该数字已在对应的行、列、宫格中出现
                rows[i][num] = 1;
                cols[j][num] = 1;
                boxes[boxIndex][num] = 1;
            }
        }
    }
    
    // 所有检查通过，数独有效
    return true;
}

// 测试函数
int main() {
    // 示例1：有效的数独
    char* board1[9] = {
        "53..7....",
        "6..195...",
        ".98....6.",
        "8...6...3",
        "4..8.3..1",
        "7...2...6",
        ".6....28.",
        "...419..5",
        "....8..79"
    };
    
    // 示例2：无效的数独（左上角3x3宫格有两个8）
    char* board2[9] = {
        "83..7....",
        "6..195...",
        ".98....6.",
        "8...6...3",
        "4..8.3..1",
        "7...2...6",
        ".6....28.",
        "...419..5",
        "....8..79"
    };
    
    int colSize[9] = {9, 9, 9, 9, 9, 9, 9, 9, 9};
    
    printf("示例1结果: %s\n", isValidSudoku(board1, 9, colSize) ? "true" : "false");
    printf("示例2结果: %s\n", isValidSudoku(board2, 9, colSize) ? "true" : "false");
    
    return 0;
}

📖 总结：

点击展开题目总结

🤔 有效的数独

1️⃣ 题目核心信息

🎯 功能描述：验证一个9x9的数独棋盘是否符合数独规则，即每行、每列和每个3x3宫格内数字1-9都不能重复出现。

📥 输入输出：

• 输入：char** board - 9x9的字符数组，代表数独棋盘；.表示空格
• 输出：bool - 如果数独有效返回true，否则返回false

---

2️⃣ 实现原理

💡 核心思路：使用哈希表思想，通过三个二维数组分别记录每行、每列和每个3x3宫格中数字的出现情况，一次遍历完成所有检查。

📋 实现步骤：

1. 创建三个二维数组分别记录行、列、宫格中数字出现情况
2. 遍历整个9x9棋盘
3. 对于非空格的数字，计算其在行、列、宫格中的索引
4. 检查该数字是否已在对应位置出现过，如出现则返回false
5. 标记该数字在对应位置已出现
6. 遍历完成未发现冲突则返回true

---

3️⃣ 关键点解析

🎯 代码技巧

• 宫格索引计算：使用(i / 3) * 3 + j / 3公式将9x9棋盘映射到9个3x3宫格
• 状态记录：使用二维数组作为哈希表记录数字出现状态，避免重复搜索
• 一次遍历：同时检查行、列、宫格三个维度，提高效率

4️⃣ 使用场景

✅ 适用情况：

• 数独游戏验证
• 9x9网格数据唯一性检查
• 类似规则的二维数组验证问题

⚠️ 前提条件：

• 输入必须是9x9的二维数组
• 数组元素只能是数字字符'1'-'9'或空格字符'.'

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(1) - 固定遍历81个格子，由于棋盘大小固定为9x9

• 💾 空间复杂度：O(1) - 使用固定大小的三个9x9数组存储状态

6️⃣ 注意事项

🚩 边界情况：

• 空格字符.的处理
• 棋盘边界（第0行/列和第8行/列）
• 宫格边界交叉点

💥 易错点：

• 宫格索引计算错误
• 字符到数字的转换错误（忘记减去'1'）
• 状态标记和检查顺序错误
• 忘记处理空格字符导致将其当作数字处理

加载评论中...