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-9在每一行只能出现一次。数字1-9在每一列只能出现一次。数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。棋盘允许部分填充未填充的空格用字符.表示。题目的约束条件Note明确了输入边界一个部分填充的数独棋盘可能是有效的但不一定是可解的——本题只做合法性校验不做求解。只需要根据上述规则验证已填入的数字。给定棋盘只包含数字1-9和字符.。给定棋盘尺寸恒为9x9。输入输出示例示例 1输出 trueInput: [ [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输出 falseInput: [ [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 8s 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 : j1] 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*33; ii { for jj : j * 3; jj j*33; 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³)n9 为棋盘边长时实际常数级按通用复杂度写法记作 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*3c/3][num] { return false } rowbuf[r][num] true colbuf[c][num] true boxbuf[r/3*3c/3][num] true // r,c 转换到box方格中 } } } return true }关键技巧宫格下标映射本解法最有价值的一行是boxbuf[r/3*3c/3][num]。它把二维坐标(r, c)通过整数除法映射到 9 个 3x3 宫的唯一编号r/3得到宫格所在的行块0~2c/3得到宫格所在的列块0~2r/3*3c/3将二维块坐标线性化为 0~8 的一维宫编号。例如(0,0)和(3,0)都映射到宫编号0/3*30/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 中提供了完整的表驱动测试覆盖了本题几乎所有边界场景测试用例场景说明期望输出示例 1 棋盘合法部分填充棋盘true示例 2 棋盘左上 3x3 宫内 8 重复false第一行8,7,6,5,4,3,2,1型棋盘行、列均满足规则true行内5,5重复行约束违反false含0非法字符数字范围越界index 1false仅 3x3 宫内5重复行、列均无重复仅宫约束违反false测试代码里还有一个值得注意的细节onlyValidChars辅助函数会先判断棋盘是否只含.或1-9。由于解法二直接做board[r][c] - 0 - byte(1)的算术换算只支持合法字符一旦输入混入0等非法字符换算出的num会变成负数导致数组越界。因此测试对解法二做了前置过滤而对解法一含显式范围校验则不设限制。这从侧面说明解法一更健壮、对非法输入更宽容解法二则在输入合法的前提下更快、代码更精简。运行测试可执行仓库根目录的测试脚本gotest.sh 使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对全部题解做带覆盖率测试也可以单独运行go test ./leetcode/0036.Valid-Sudoku/ -v -run Test_Problem36总结两类解法的选型建议追求健壮性使用解法一isValidSudoku它对输入字符做了显式范围校验即使遇到0等非法字符也不会越界适合作为通用校验函数。追求性能与简洁使用解法二isValidSudoku1一次遍历加三路布尔缓存配合r/3*3c/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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考