Leetcode 有效的数独

这段代码解决的是 验证一个数独是否有效 的问题，其算法思想是基于 规则校验和状态记录。具体思想如下：

---

算法思想

1. 核心目标：

   • 检查每个数字在 同一行、同一列 和 同一个 3x3 子格 中是否重复。

2. 状态记录：

   • 使用 3 个布尔二维数组分别记录：
     • 每行数字的出现情况 rows[i][num]。
     • 每列数字的出现情况 cols[j][num]。
     • 每个 3x3 子格数字的出现情况 boxes[boxIndex][num]。
   • 通过这些状态数组，可以快速检查某个数字是否在对应位置已存在。

3. 遍历与验证：

   • 遍历整个 9x9 的数独表格，对于每一个非空格的数字：
     • 计算数字对应的行、列和 3x3 子格索引。
     • 检查当前数字是否在对应行、列或 3x3 子格中已存在。
     • 如果存在，直接返回 false，表示数独无效。
     • 如果不存在，将该数字标记为已出现，更新状态数组。
   • 如果遍历完成未发现冲突，返回 true，表示数独有效。

---

算法步骤

1. 初始化数据结构

• 定义三个布尔二维数组：rows[9][9], cols[9][9], boxes[9][9]。
  • rows[i][num]: 记录第 i 行中数字 num+1 是否已经出现。
  • cols[j][num]: 记录第 j 列中数字 num+1 是否已经出现。
  • boxes[boxIndex][num]: 记录第 boxIndex 个 3x3 子格中数字 num+1 是否已经出现。

2. 遍历整个数独表格

• 对于每个位置 (i, j)：
  • 如果是空格（'.'），直接跳过。
  • 将字符数字转换为整数索引 num，如字符 '5' 转换为整数 4（因为数组索引从 0 开始）。
  • 计算数字所属的 3x3 子格索引：boxIndex = (i / 3) * 3 + j / 3。
    • 行和列分别除以 3 取整可以确定当前数字在哪一块 3x3 子格中。

3. 检查并标记状态

• 检查状态数组：
  • 如果 rows[i][num] == true，说明第 i 行已经出现过数字 num+1。
  • 如果 cols[j][num] == true，说明第 j 列已经出现过数字 num+1。
  • 如果 boxes[boxIndex][num] == true，说明该 3x3 子格已经出现过数字 num+1。
• 如果任何一项为 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' 转换为索引 0，'9' 转换为索引 8。

3. 为什么需要状态数组？

• 状态数组是为了快速记录和检查数字的存在性。
• 使用布尔值记录 true 或 false，可以节省时间复杂度，相较于遍历行、列和子格的直接检查更加高效。

---

时间和空间复杂度分析

1. 时间复杂度：

   • 遍历整个 9x9 表格，时间复杂度为 (O(9 \times 9) = O(81))，即常数级复杂度。

2. 空间复杂度：

   • 使用了 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行是否出现过num
        boolean [][] cols = new boolean[9][9]; //cols[j][num]表示第j列是否出现过num
        boolean [][] boxes = new boolean[9][9]; //boxes[boxindex][num]表示第boxindex个3*3方格中是否出现过num

        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                //首先跳过空格
                if(board[i][j] == '.') {
                    continue;
                }
                //首先获取boxindex
                int 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;
    }
}

原文地址：https://blog.csdn.net/coldasice342/article/details/143832924

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！