獨判定（雙解法與源碼解析）)
LeetCode-Go 題解36. Valid Sudoku 有效數(shù)獨判定雙解法與源碼解析【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技術(shù)指南以 LeetCode-Go 倉庫中 0036.Valid-Sudoku 的題解文檔與源碼為依托完整講解 36. Valid Sudoku 的判定規(guī)則、兩種 Go 實現(xiàn)O(n3) 暴力遍歷與 O(n2) 緩存法及其時間復(fù)雜度差異并結(jié)合倉庫內(nèi)的單元測試用例說明邊界行為。讀完本文你將掌握數(shù)獨有效性校驗的經(jīng)典三約束行、列、3x3 宮判定套路以及如何用一維索引技巧把二維宮格坐標映射到緩存數(shù)組。題目定義與判定規(guī)則給定一個 9x9 的數(shù)獨棋盤board判斷它當前是否有效。題目只要求驗證已經(jīng)填入的數(shù)字是否有效不需要求解數(shù)獨。判定依據(jù)以下三條規(guī)則數(shù)字1-9在每一行只能出現(xiàn)一次。數(shù)字1-9在每一列只能出現(xiàn)一次。數(shù)字1-9在每一個以粗實線分隔的3x3宮內(nèi)只能出現(xiàn)一次。棋盤允許部分填充未填充的空格用字符.表示。題目的約束條件Note明確了輸入邊界一個部分填充的數(shù)獨棋盤可能是有效的但不一定是可解的——本題只做合法性校驗不做求解。只需要根據(jù)上述規(guī)則驗證已填入的數(shù)字。給定棋盤只包含數(shù)字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 的差別僅在于左上角第一個數(shù)字從5改成了8。修改后左上角 3x3 宮內(nèi)出現(xiàn)了兩個8位置(0,0)與(3,0)因此整個棋盤不滿足規(guī)則判定為無效。題目大意核心要點本題要解決的問題非常聚焦判斷一個 9x9 數(shù)獨棋盤當前的狀態(tài)是否滿足數(shù)獨要求即每一行是否只包含 1-9 且不重復(fù)每一列是否只包含 1-9 且不重復(fù)每一個 3x3 宮內(nèi)是否只包含 1-9 且不重復(fù)。需要特別注意的是本題與第 37 題Sudoku Solver是不同的第 36 題只判斷當前棋盤狀態(tài)是否滿足規(guī)則而第 37 題要求真正求解數(shù)獨填充空格。本題中的部分棋盤可能是無解的但只要其當前狀態(tài)滿足上述三條規(guī)則依然判定為有效。例如 0037.Sudoku-Solver 一題要求保證題目有唯一解而本題則完全不需要考慮可解性。解法一暴力遍歷O(n3)倉庫中的第一版實現(xiàn)位于 36. Valid Sudoku.go思路是對行、列、3x3 宮三組約束分別做三次完整遍歷每次用一個長度為 10 的數(shù)組tmp做數(shù)字出現(xiàn)標記。// 解法一 暴力遍歷時間復(fù)雜度 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) ! . { // 數(shù)字范圍已在判斷行的循環(huán)中校驗過這里無需重復(fù)校驗 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 }實現(xiàn)要點拆解行校驗外層循環(huán)固定行號i內(nèi)層遍歷該行 9 列。用strconv.Atoi把字節(jié)轉(zhuǎn)成數(shù)字作為下標tmp[index] 1表示該數(shù)字已出現(xiàn)過立刻返回false。這里還額外做了數(shù)字范圍校驗index 9 || index 1因此即使輸入混入0之類的非法字符也能被安全攔截。列校驗交換下標訪問方式為board[j][i]即可實現(xiàn)按列掃描。由于行校驗已經(jīng)完成數(shù)字范圍檢查列校驗不再重復(fù)該邏輯。3x3 宮校驗外層兩層循環(huán)(i, j)枚舉 9 個宮格的左上角起點i*3、j*3內(nèi)層兩層循環(huán)遍歷該宮內(nèi) 3x3 共 9 個格子同樣用tmp數(shù)組查重。復(fù)雜度分析該解法對棋盤做了三趟完整遍歷每趟 81 個格子外加 3x3 宮嵌套循環(huán)的常數(shù)開銷整體時間復(fù)雜度為O(n3)n9 為棋盤邊長時實際常數(shù)級按通用復(fù)雜度寫法記作 O(n3)空間復(fù)雜度為 O(1)僅使用定長數(shù)組。由于棋盤尺寸恒為 9x9該解法在本題約束下依然完全可行。解法二一次遍歷 三路緩存O(n2)倉庫中的第二版實現(xiàn)同樣位于 36. Valid Sudoku.go核心思路是只遍歷棋盤一次用三張 9x9 的布爾緩存表分別記錄該數(shù)字是否已在本行 / 本列 / 本宮出現(xiàn)過查重失敗立即返回。// 解法二 添加緩存時間復(fù)雜度 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 轉(zhuǎn)換到box方格中 } } } return true }關(guān)鍵技巧宮格下標映射本解法最有價值的一行是boxbuf[r/3*3c/3][num]。它把二維坐標(r, c)通過整數(shù)除法映射到 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 宮、從而被判定重復(fù)的關(guān)鍵依據(jù)。另外num : board[r][c] - 0 - byte(1)直接把字節(jié)字符1~9減去0再減 1換算成下標0~8避免了strconv.Atoi的字符串轉(zhuǎn)換開銷也不需要用[10]int而可用[9]bool緊湊存儲。復(fù)雜度分析全程只掃描一次 81 個格子每格做 O(1) 的查重與標記時間復(fù)雜度為O(n2)空間復(fù)雜度為 O(n2)三張 9x9 布爾表。相比解法一用少量額外空間換來了更優(yōu)的時間復(fù)雜度。單元測試與邊界行為驗證倉庫在 36. Valid Sudoku_test.go 中提供了完整的表驅(qū)動測試覆蓋了本題幾乎所有邊界場景測試用例場景說明期望輸出示例 1 棋盤合法部分填充棋盤true示例 2 棋盤左上 3x3 宮內(nèi) 8 重復(fù)false第一行8,7,6,5,4,3,2,1型棋盤行、列均滿足規(guī)則true行內(nèi)5,5重復(fù)行約束違反false含0非法字符數(shù)字范圍越界index 1false僅 3x3 宮內(nèi)5重復(fù)行、列均無重復(fù)僅宮約束違反false測試代碼里還有一個值得注意的細節(jié)onlyValidChars輔助函數(shù)會先判斷棋盤是否只含.或1-9。由于解法二直接做board[r][c] - 0 - byte(1)的算術(shù)換算只支持合法字符一旦輸入混入0等非法字符換算出的num會變成負數(shù)導(dǎo)致數(shù)組越界。因此測試對解法二做了前置過濾而對解法一含顯式范圍校驗則不設(shè)限制。這從側(cè)面說明解法一更健壯、對非法輸入更寬容解法二則在輸入合法的前提下更快、代碼更精簡。運行測試可執(zhí)行倉庫根目錄的測試腳本gotest.sh 使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...對全部題解做帶覆蓋率測試也可以單獨運行g(shù)o test ./leetcode/0036.Valid-Sudoku/ -v -run Test_Problem36總結(jié)兩類解法的選型建議追求健壯性使用解法一isValidSudoku它對輸入字符做了顯式范圍校驗即使遇到0等非法字符也不會越界適合作為通用校驗函數(shù)。追求性能與簡潔使用解法二isValidSudoku1一次遍歷加三路布爾緩存配合r/3*3c/3的宮格線性化索引代碼最精煉、常數(shù)最小前提是輸入已保證只含合法字符題目 Note 中已聲明。無論哪種實現(xiàn)核心都是把行、列、3x3 宮三條約束轉(zhuǎn)化為數(shù)字去重問題這也是后續(xù)第 37 題 Sudoku Solver 求解、以及其他棋盤類回溯問題如 N-Queens、Word Search共用的基礎(chǔ)套路。【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 LeetCode-Go 題解：36. Valid Sudoku 有效數(shù)獨判定（雙解法與源碼解析）
LeetCode-Go 題解36. Valid Sudoku 有效數(shù)獨判定雙解法與源碼解析【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技術(shù)指南以 LeetCode-Go 倉庫中 0036.Valid-Sudoku 的題解文檔與源碼為依托完整講解 36. Valid Sudoku 的判定規(guī)則、兩種 Go 實現(xiàn)O(n3) 暴力遍歷與 O(n2) 緩存法及其時間復(fù)雜度差異并結(jié)合倉庫內(nèi)的單元測試用例說明邊界行為。讀完本文你將掌握數(shù)獨有效性校驗的經(jīng)典三約束行、列、3x3 宮判定套路以及如何用一維索引技巧把二維宮格坐標映射到緩存數(shù)組。題目定義與判定規(guī)則給定一個 9x9 的數(shù)獨棋盤board判斷它當前是否有效。題目只要求驗證已經(jīng)填入的數(shù)字是否有效不需要求解數(shù)獨。判定依據(jù)以下三條規(guī)則數(shù)字1-9在每一行只能出現(xiàn)一次。數(shù)字1-9在每一列只能出現(xiàn)一次。數(shù)字1-9在每一個以粗實線分隔的3x3宮內(nèi)只能出現(xiàn)一次。棋盤允許部分填充未填充的空格用字符.表示。題目的約束條件Note明確了輸入邊界一個部分填充的數(shù)獨棋盤可能是有效的但不一定是可解的——本題只做合法性校驗不做求解。只需要根據(jù)上述規(guī)則驗證已填入的數(shù)字。給定棋盤只包含數(shù)字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 的差別僅在于左上角第一個數(shù)字從5改成了8。修改后左上角 3x3 宮內(nèi)出現(xiàn)了兩個8位置(0,0)與(3,0)因此整個棋盤不滿足規(guī)則判定為無效。題目大意核心要點本題要解決的問題非常聚焦判斷一個 9x9 數(shù)獨棋盤當前的狀態(tài)是否滿足數(shù)獨要求即每一行是否只包含 1-9 且不重復(fù)每一列是否只包含 1-9 且不重復(fù)每一個 3x3 宮內(nèi)是否只包含 1-9 且不重復(fù)。需要特別注意的是本題與第 37 題Sudoku Solver是不同的第 36 題只判斷當前棋盤狀態(tài)是否滿足規(guī)則而第 37 題要求真正求解數(shù)獨填充空格。本題中的部分棋盤可能是無解的但只要其當前狀態(tài)滿足上述三條規(guī)則依然判定為有效。例如 0037.Sudoku-Solver 一題要求保證題目有唯一解而本題則完全不需要考慮可解性。解法一暴力遍歷O(n3)倉庫中的第一版實現(xiàn)位于 36. Valid Sudoku.go思路是對行、列、3x3 宮三組約束分別做三次完整遍歷每次用一個長度為 10 的數(shù)組tmp做數(shù)字出現(xiàn)標記。// 解法一 暴力遍歷時間復(fù)雜度 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) ! . { // 數(shù)字范圍已在判斷行的循環(huán)中校驗過這里無需重復(fù)校驗 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 }實現(xiàn)要點拆解行校驗外層循環(huán)固定行號i內(nèi)層遍歷該行 9 列。用strconv.Atoi把字節(jié)轉(zhuǎn)成數(shù)字作為下標tmp[index] 1表示該數(shù)字已出現(xiàn)過立刻返回false。這里還額外做了數(shù)字范圍校驗index 9 || index 1因此即使輸入混入0之類的非法字符也能被安全攔截。列校驗交換下標訪問方式為board[j][i]即可實現(xiàn)按列掃描。由于行校驗已經(jīng)完成數(shù)字范圍檢查列校驗不再重復(fù)該邏輯。3x3 宮校驗外層兩層循環(huán)(i, j)枚舉 9 個宮格的左上角起點i*3、j*3內(nèi)層兩層循環(huán)遍歷該宮內(nèi) 3x3 共 9 個格子同樣用tmp數(shù)組查重。復(fù)雜度分析該解法對棋盤做了三趟完整遍歷每趟 81 個格子外加 3x3 宮嵌套循環(huán)的常數(shù)開銷整體時間復(fù)雜度為O(n3)n9 為棋盤邊長時實際常數(shù)級按通用復(fù)雜度寫法記作 O(n3)空間復(fù)雜度為 O(1)僅使用定長數(shù)組。由于棋盤尺寸恒為 9x9該解法在本題約束下依然完全可行。解法二一次遍歷 三路緩存O(n2)倉庫中的第二版實現(xiàn)同樣位于 36. Valid Sudoku.go核心思路是只遍歷棋盤一次用三張 9x9 的布爾緩存表分別記錄該數(shù)字是否已在本行 / 本列 / 本宮出現(xiàn)過查重失敗立即返回。// 解法二 添加緩存時間復(fù)雜度 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 轉(zhuǎn)換到box方格中 } } } return true }關(guān)鍵技巧宮格下標映射本解法最有價值的一行是boxbuf[r/3*3c/3][num]。它把二維坐標(r, c)通過整數(shù)除法映射到 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 宮、從而被判定重復(fù)的關(guān)鍵依據(jù)。另外num : board[r][c] - 0 - byte(1)直接把字節(jié)字符1~9減去0再減 1換算成下標0~8避免了strconv.Atoi的字符串轉(zhuǎn)換開銷也不需要用[10]int而可用[9]bool緊湊存儲。復(fù)雜度分析全程只掃描一次 81 個格子每格做 O(1) 的查重與標記時間復(fù)雜度為O(n2)空間復(fù)雜度為 O(n2)三張 9x9 布爾表。相比解法一用少量額外空間換來了更優(yōu)的時間復(fù)雜度。單元測試與邊界行為驗證倉庫在 36. Valid Sudoku_test.go 中提供了完整的表驅(qū)動測試覆蓋了本題幾乎所有邊界場景測試用例場景說明期望輸出示例 1 棋盤合法部分填充棋盤true示例 2 棋盤左上 3x3 宮內(nèi) 8 重復(fù)false第一行8,7,6,5,4,3,2,1型棋盤行、列均滿足規(guī)則true行內(nèi)5,5重復(fù)行約束違反false含0非法字符數(shù)字范圍越界index 1false僅 3x3 宮內(nèi)5重復(fù)行、列均無重復(fù)僅宮約束違反false測試代碼里還有一個值得注意的細節(jié)onlyValidChars輔助函數(shù)會先判斷棋盤是否只含.或1-9。由于解法二直接做board[r][c] - 0 - byte(1)的算術(shù)換算只支持合法字符一旦輸入混入0等非法字符換算出的num會變成負數(shù)導(dǎo)致數(shù)組越界。因此測試對解法二做了前置過濾而對解法一含顯式范圍校驗則不設(shè)限制。這從側(cè)面說明解法一更健壯、對非法輸入更寬容解法二則在輸入合法的前提下更快、代碼更精簡。運行測試可執(zhí)行倉庫根目錄的測試腳本gotest.sh 使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...對全部題解做帶覆蓋率測試也可以單獨運行g(shù)o test ./leetcode/0036.Valid-Sudoku/ -v -run Test_Problem36總結(jié)兩類解法的選型建議追求健壯性使用解法一isValidSudoku它對輸入字符做了顯式范圍校驗即使遇到0等非法字符也不會越界適合作為通用校驗函數(shù)。追求性能與簡潔使用解法二isValidSudoku1一次遍歷加三路布爾緩存配合r/3*3c/3的宮格線性化索引代碼最精煉、常數(shù)最小前提是輸入已保證只含合法字符題目 Note 中已聲明。無論哪種實現(xiàn)核心都是把行、列、3x3 宮三條約束轉(zhuǎn)化為數(shù)字去重問題這也是后續(xù)第 37 題 Sudoku Solver 求解、以及其他棋盤類回溯問題如 N-Queens、Word Search共用的基礎(chǔ)套路。【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考