企业官网建设流程全解析

LeetCode-Go 题解：36. Valid Sudoku 有效数独判定（双解法与源码解析）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇技术指南以 LeetCode-Go 仓库中 0036.Valid-Sudoku 的题解文档与源码为依托，完整讲解 36. Valid Sudoku 的判定规则、两种 Go 实现（O(n³) 暴力遍历与 O(n²) 缓存法）及其时间复杂度差异，并结合仓库内的单元测试用例说明边界行为。读完本文，你将掌握数独有效性校验的经典三约束（行、列、3x3 宫）判定套路，以及如何用一维索引技巧把二维宫格坐标映射到缓存数组。

题目定义与判定规则

给定一个 9x9 的数独棋盘board，判断它当前是否有效。题目只要求验证已经填入的数字是否有效，不需要求解数独。判定依据以下三条规则：

1. 数字1-9在每一行只能出现一次。
2. 数字1-9在每一列只能出现一次。
3. 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。

棋盘允许部分填充，未填充的空格用字符'.'表示。

题目的约束条件（Note）明确了输入边界：

• 一个（部分填充的）数独棋盘可能是有效的，但不一定是可解的——本题只做合法性校验，不做求解。
• 只需要根据上述规则验证已填入的数字。
• 给定棋盘只包含数字1-9和字符'.'。
• 给定棋盘尺寸恒为9x9。

输入输出示例

示例 1（输出 true）：

Input: [ ["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"] ] Output: true

示例 2（输出 false）：

Input: [ ["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"] ] Output: false Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

示例 2 与示例 1 的差别仅在于左上角第一个数字从5改成了8。修改后左上角 3x3 宫内出现了两个8（位置(0,0)与(3,0)），因此整个棋盘不满足规则，判定为无效。

题目大意（核心要点）

本题要解决的问题非常聚焦：判断一个 9x9 数独棋盘当前的状态是否满足数独要求，即：

• 每一行是否只包含 1-9 且不重复；
• 每一列是否只包含 1-9 且不重复；
• 每一个 3x3 宫内是否只包含 1-9 且不重复。

需要特别注意的是，本题与第 37 题（Sudoku Solver）是不同的：第 36 题只判断当前棋盘状态是否满足规则，而第 37 题要求真正求解数独（填充空格）。本题中的部分棋盘可能是无解的，但只要其当前状态满足上述三条规则，依然判定为有效。例如 0037.Sudoku-Solver 一题要求保证题目有唯一解，而本题则完全不需要考虑可解性。

解法一：暴力遍历（O(n³)）

仓库中的第一版实现位于 36. Valid Sudoku.go，思路是对"行、列、3x3 宫"三组约束分别做三次完整遍历，每次用一个长度为 10 的数组tmp做数字出现标记。

// 解法一 暴力遍历，时间复杂度 O(n^3) func isValidSudoku(board [][]byte) bool { // 判断行 row for i := 0; i < 9; i++ { tmp := [10]int{} for j := 0; j < 9; j++ { cellVal := board[i][j : j+1] if string(cellVal) != "." { index, _ := strconv.Atoi(string(cellVal)) if index > 9 || index < 1 { return false } if tmp[index] == 1 { return false } tmp[index] = 1 } } } // 判断列 column for i := 0; i < 9; i++ { tmp := [10]int{} for j := 0; j < 9; j++ { cellVal := board[j][i] if string(cellVal) != "." { // 数字范围已在判断行的循环中校验过，这里无需重复校验 index, _ := strconv.Atoi(string(cellVal)) if tmp[index] == 1 { return false } tmp[index] = 1 } } } // 判断 9宫格 3X3 cell for i := 0; i < 3; i++ { for j := 0; j < 3; j++ { tmp := [10]int{} for ii := i * 3; ii < i*3+3; ii++ { for jj := j * 3; jj < j*3+3; jj++ { cellVal := board[ii][jj] if string(cellVal) != "." { index, _ := strconv.Atoi(string(cellVal)) if tmp[index] == 1 { return false } tmp[index] = 1 } } } } } return true }

实现要点拆解

• 行校验：外层循环固定行号i，内层遍历该行 9 列。用strconv.Atoi把字节转成数字作为下标，tmp[index] == 1表示该数字已出现过，立刻返回false。这里还额外做了数字范围校验（index > 9 || index < 1），因此即使输入混入'0'之类的非法字符也能被安全拦截。
• 列校验：交换下标访问方式为board[j][i]，即可实现按列扫描。由于行校验已经完成数字范围检查，列校验不再重复该逻辑。
• 3x3 宫校验：外层两层循环(i, j)枚举 9 个宫格的左上角起点（i*3、j*3），内层两层循环遍历该宫内 3x3 共 9 个格子，同样用tmp数组查重。

复杂度分析

该解法对棋盘做了三趟完整遍历，每趟 81 个格子，外加 3x3 宫嵌套循环的常数开销，整体时间复杂度为O(n³)（n=9 为棋盘边长时实际常数级，按通用复杂度写法记作 O(n³)），空间复杂度为 O(1)（仅使用定长数组）。由于棋盘尺寸恒为 9x9，该解法在本题约束下依然完全可行。

解法二：一次遍历 + 三路缓存（O(n²)）

仓库中的第二版实现同样位于 36. Valid Sudoku.go，核心思路是只遍历棋盘一次，用三张 9x9 的布尔缓存表分别记录"该数字是否已在本行 / 本列 / 本宫出现过"，查重失败立即返回。

// 解法二 添加缓存，时间复杂度 O(n^2) func isValidSudoku1(board [][]byte) bool { rowbuf, colbuf, boxbuf := make([][]bool, 9), make([][]bool, 9), make([][]bool, 9) for i := 0; i < 9; i++ { rowbuf[i] = make([]bool, 9) colbuf[i] = make([]bool, 9) boxbuf[i] = make([]bool, 9) } // 遍历一次，添加缓存 for r := 0; r < 9; r++ { for c := 0; c < 9; c++ { if board[r][c] != '.' { num := board[r][c] - '0' - byte(1) if rowbuf[r][num] || colbuf[c][num] || boxbuf[r/3*3+c/3][num] { return false } rowbuf[r][num] = true colbuf[c][num] = true boxbuf[r/3*3+c/3][num] = true // r,c 转换到box方格中 } } } return true }

关键技巧：宫格下标映射

本解法最有价值的一行是boxbuf[r/3*3+c/3][num]。它把二维坐标(r, c)通过整数除法映射到 9 个 3x3 宫的唯一编号：

• r/3得到宫格所在的行块（0~2）；
• c/3得到宫格所在的列块（0~2）；
• r/3*3+c/3将二维块坐标线性化为 0~8 的一维宫编号。

例如(0,0)和(3,0)都映射到宫编号0/3*3+0/3 = 0，这正是示例 2 中两个8同处左上角 3x3 宫、从而被判定重复的关键依据。

另外，num := board[r][c] - '0' - byte(1)直接把字节字符'1'~'9'减去'0'再减 1，换算成下标0~8，避免了strconv.Atoi的字符串转换开销，也不需要用[10]int而可用[9]bool紧凑存储。

复杂度分析

全程只扫描一次 81 个格子，每格做 O(1) 的查重与标记，时间复杂度为O(n²)，空间复杂度为 O(n²)（三张 9x9 布尔表）。相比解法一，用少量额外空间换来了更优的时间复杂度。

单元测试与边界行为验证

仓库在 36. Valid Sudoku_test.go 中提供了完整的表驱动测试，覆盖了本题几乎所有边界场景：

测试代码里还有一个值得注意的细节：onlyValidChars辅助函数会先判断棋盘是否只含'.'或'1'-'9'。由于解法二直接做board[r][c] - '0' - byte(1)的算术换算，只支持合法字符；一旦输入混入'0'等非法字符，换算出的num会变成负数导致数组越界。因此测试对解法二做了前置过滤，而对解法一（含显式范围校验）则不设限制。这从侧面说明：解法一更健壮、对非法输入更宽容，解法二则在输入合法的前提下更快、代码更精简。

运行测试可执行仓库根目录的测试脚本（gotest.sh 使用go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...对全部题解做带覆盖率测试），也可以单独运行：

go test ./leetcode/0036.Valid-Sudoku/ -v -run Test_Problem36

总结：两类解法的选型建议

• 追求健壮性：使用解法一（isValidSudoku），它对输入字符做了显式范围校验，即使遇到'0'等非法字符也不会越界，适合作为通用校验函数。
• 追求性能与简洁：使用解法二（isValidSudoku1），一次遍历加三路布尔缓存，配合r/3*3+c/3的宫格线性化索引，代码最精炼、常数最小，前提是输入已保证只含合法字符（题目 Note 中已声明）。

无论哪种实现，核心都是把"行、列、3x3 宫"三条约束转化为"数字去重"问题，这也是后续第 37 题 Sudoku Solver 求解、以及其他棋盘类回溯问题（如 N-Queens、Word Search）共用的基础套路。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go