leetcode
leetcode 1 ~ 50
有效的数独

有效的数独

难度:

标签:

题目描述

请你判断一个 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 存在, 因此这个数独是无效的。

 

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字（1-9）或者 '.'

代码结果

运行时间: 56 ms, 内存: 14.9 MB

/*
 * 思路：
 * 1. 使用流操作来遍历数独棋盘，分别检查行、列和子宫格中的数字是否有重复。
 * 2. 对于每一个数字，如果已经在对应行、列或子宫格中出现，则返回false。
 * 3. 使用Set来存储已经出现的数字，避免重复。
 */
 
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;
 
public class Solution {
    public boolean isValidSudoku(char[][] board) {
        return IntStream.range(0, 9).allMatch(i -> {
            Set<Character> rows = new HashSet<>();
            Set<Character> cols = new HashSet<>();
            Set<Character> box = new HashSet<>();
            return IntStream.range(0, 9).allMatch(j -> {
                char r = board[i][j];
                char c = board[j][i];
                char b = board[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3];
                return (r == '.' || rows.add(r)) &&
                       (c == '.' || cols.add(c)) &&
                       (b == '.' || box.add(b));
            });
        });
    }
}

解释

方法:

题解的思路是使用三个哈希表来分别记录每一行、每一列和每个3x3宫格中已经出现过的数字。遍历数独矩阵，对于每个非空的单元格，检查其值是否已经在对应的行、列或3x3宫格的哈希表中出现过。如果出现过，说明数独无效，返回False；否则将该值添加到对应的哈希表中。遍历完整个矩阵后，如果没有发现重复的数字，说明数独有效，返回True。

时间复杂度:

O(1)

空间复杂度:

O(1)

代码细节讲解

🦆
在实现检查是否有效的数独时，你如何确定一个数字是否应该被添加到对应的行、列或3x3宫格的哈希表中？
▷
在检查数独是否有效的过程中，对于数独板上的每一个非空单元格，我们首先读取其值。然后，我们需要确定这个值是否已经存在于当前单元格所在的行、列或宫格的哈希表中。如果该值已存在，说明在数独的行、列或宫格中已经有重复的数字，因此数独无效；如果不存在，则将这个值添加到相应的哈希表中，表示该行、列或宫格已经包含了这个数字。这种方法可以快速地检查并记录每个数字出现的情况，保证数独的每个行、列和宫格内的数字都是唯一的。
🦆
数独验证中，使用三个哈希表来记录状态的具体实现逻辑是什么？能否详细解释这些哈希表是如何更新和查询的？
▷
在数独验证的实现中，我们使用三组哈希表，分别代表数独的每一行、每一列和每一个3x3宫格。这些哈希表用于存储已经在对应行、列或宫格中出现过的数字。对于数独板上的每个单元格，我们首先检查该单元格的值。若该值不为空，则计算它应属于的宫格的索引，这可以通过行索引整除3乘以3加上列索引整除3得到。接下来，我们查询该值是否已经存在于对应的行、列或宫格的哈希表中。如果存在，返回False表示数独无效。如果不存在，则将该值添加到三个哈希表的相应位置。这样的查询和更新操作都是O(1)的时间复杂度，使得整个数独验证过程非常高效。
🦆
在数独问题中，为何选择哈希表来存储行、列及3x3宫格内的数字，而不是使用其他数据结构如数组或链表？
▷
在处理数独问题时，选择哈希表而不是数组或链表主要基于效率和简便性的考虑。哈希表提供了常数时间复杂度的插入和查找操作，这使得检查数字是否已存在变得非常快速。相比之下，如果使用数组，虽然空间利用率可能更高，但在检查一个数字是否存在时可能需要遍历整个数组，其时间复杂度为O(n)。链表虽然可以动态增长，但其查找和插入（如果需要保持有序）的平均时间复杂度也是O(n)。因此，哈希表在这种需要频繁查找和插入的场景下，提供了最佳的时间效率。

相关问题

解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

  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"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

 

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 '.'
  • 题目数据 保证 输入数独仅有一个解
搜索插入位置解数独