Leetcode 每日一题 36.有效的数独

问题描述

输入输出格式

算法思路

过题图片

代码实现

题目链接

复杂度分析

问题描述

给定一个 9x9 的数独棋盘，我们需要判断棋盘上已填入的数字是否有效。根据数独的规则，有效性需要满足以下条件：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

输入输出格式

输入：一个 9x9 的二维数组 board，其中每个元素是一个字符，表示数独棋盘上的数字或空白。

输出：一个布尔值，如果数独有效返回 true，否则返回 false。

算法思路

为了判断数独的有效性，我们需要检查每一行、每一列以及每一个 3x3 宫格中的数字是否重复。我们可以使用三个数据结构来分别跟踪这些位置的数字出现次数：

行：使用一个数组 rows，其中每个元素是一个 HashMap，用于存储每一行中数字的出现次数。
列：使用一个数组 cols，与 rows 类似，用于存储每一列中数字的出现次数。
3x3 宫格：使用一个二维数组 cubes，其中每个元素是一个 HashMap，用于存储每个 3x3 宫格中数字的出现次数。

遍历整个棋盘，对于每个非空白的单元格，我们检查其对应的行、列和宫格中该数字是否已经出现过。如果出现过，则数独无效；否则，我们更新对应的计数器。

过题图片

代码实现

java

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 用于检查每一行
        Map<Character, Integer>[] rows = new HashMap[9];
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashMap<>();
        }

        // 用于检查每一列
        Map<Character, Integer>[] cols = new HashMap[9];
        for (int i = 0; i < 9; i++) {
            cols[i] = new HashMap<>();
        }

        // 用于检查每一个3x3宫格
        Map<Character, Integer>[][] cubes = new HashMap[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cubes[i][j] = new HashMap<>();
            }
        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') continue;

                // 检查行
                if (rows[i].getOrDefault(c, 0) > 0) return false;
                rows[i].put(c, rows[i].getOrDefault(c, 0) + 1);

                // 检查列
                if (cols[j].getOrDefault(c, 0) > 0) return false;
                cols[j].put(c, cols[j].getOrDefault(c, 0) + 1);

                // 检查3x3宫格
                int cubeIndexI = i / 3;
                int cubeIndexJ = j / 3;
                if (cubes[cubeIndexI][cubeIndexJ].getOrDefault(c, 0) > 0) return false;
                cubes[cubeIndexI][cubeIndexJ].put(c, cubes[cubeIndexI][cubeIndexJ].getOrDefault(c, 0) + 1);
            }
        }

        return true;
    }
}