LeetCode 36. 有效的数独

Categories:

题目描述
思路分析
1. 解法一：行列宫统计（推荐）
相似题目

题目描述

✅ 36. 有效的数独

思路分析

解法一：行列宫统计（推荐）

核心思路：

使用三个布尔数组分别记录行、列、3x3 宫格中数字是否出现。

遍历棋盘，若某数字在对应行/列/宫已出现则无效。

只需验证一次即可。

复杂度分析：

时间复杂度：O(1)，固定 9x9 棋盘。

空间复杂度：O(1)，固定大小数组。

class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] row = new boolean[9][9];
        boolean[][] col = new boolean[9][9];
        boolean[][] box = new boolean[9][9];

        // 遍历棋盘并统计行列宫
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') {
                    continue;
                }

                int idx = c - '1';
                int b = (i / 3) * 3 + j / 3;

                if (row[i][idx] || col[j][idx] || box[b][idx]) {
                    return false;
                }

                row[i][idx] = true;
                col[j][idx] = true;
                box[b][idx] = true;
            }
        }

        return true;
    }
}

func isValidSudoku(board [][]byte) bool {
	row := make([][]bool, 9)
	col := make([][]bool, 9)
	box := make([][]bool, 9)
	for i := 0; i < 9; i++ {
		row[i] = make([]bool, 9)
		col[i] = make([]bool, 9)
		box[i] = make([]bool, 9)
	}

	// 遍历棋盘并统计行列宫
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			c := board[i][j]
			if c == '.' {
				continue
			}

			idx := int(c - '1')
			b := (i/3)*3 + j/3

			if row[i][idx] || col[j][idx] || box[b][idx] {
				return false
			}

			row[i][idx] = true
			col[j][idx] = true
			box[b][idx] = true
		}
	}

	return true
}

相似题目

题目	难度	考察点
37. 解数独	困难	回溯
51. N 皇后	困难	回溯
52. N 皇后 II	困难	回溯
79. 单词搜索	中等	回溯
212. 单词搜索 II	困难	回溯、字典树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/70892084