科學(xué)計(jì)算【免費(fèi)下載鏈接】codeforces-go算法競(jìng)賽模板庫(kù) by 靈茶山艾府 項(xiàng)目地址https://gitcode.com/GitHub_Trending/co/codeforces-go點(diǎn)擊查看免費(fèi)下載導(dǎo)讀本文以 leetcode/biweekly/191/b/README.md 題解為主體深入剖析力扣雙周賽 191 第 2 題「Count Values With Equally Spaced Occurrences II」等間隔出現(xiàn)次數(shù) II的經(jīng)典解法先用哈希表統(tǒng)計(jì)每個(gè)值出現(xiàn)的所有下標(biāo)再逐一判斷這些下標(biāo)是否構(gòu)成等差數(shù)列。讀完本文你將掌握「位置分組 等間隔判定」這一簡(jiǎn)潔的 O(n) 算法并看到它在當(dāng)前倉(cāng)庫(kù)中對(duì)應(yīng)的 Go 實(shí)現(xiàn)、單測(cè)用例與自動(dòng)化測(cè)試框架是如何組織起來(lái)的。一、題意梳理什么樣的值「等間隔出現(xiàn)」題目給一個(gè)整數(shù)數(shù)組nums要求統(tǒng)計(jì)其中「等間隔出現(xiàn)」的元素的個(gè)數(shù)。一個(gè)值x被視為「等間隔出現(xiàn)」需要滿(mǎn)足x在數(shù)組中出現(xiàn)至少 3 次x每次出現(xiàn)的位置下標(biāo)構(gòu)成一個(gè)等差數(shù)列即相鄰兩次出現(xiàn)的位置差為一個(gè)固定的非零常數(shù)。例如nums [1,8,1,5,1,5,8,5]1出現(xiàn)在下標(biāo)0, 2, 4相鄰間隔均為2符合5出現(xiàn)在下標(biāo)3, 5, 7相鄰間隔均為2符合8只出現(xiàn)在下標(biāo)1, 6不足 3 次不計(jì)入。因此答案為2。需要注意本題II 版本只要求「至少 3 次」與同一場(chǎng)雙周賽的 Q1I 版本恰好要求「剛好出現(xiàn) 3 次」不同下文會(huì)專(zhuān)門(mén)對(duì)比二者在實(shí)現(xiàn)上的差異。二、核心思路哈希表分組 等差判定題解給出兩步式框架統(tǒng)計(jì)位置遍歷數(shù)組把每個(gè)值x的所有出現(xiàn)下標(biāo)依次記錄在pos[x]中判斷等間隔遍歷每個(gè)pos[x]若長(zhǎng)度不足 3 直接跳過(guò)否則用pos[1] - pos[0]求出相鄰下標(biāo)差d再檢查該組內(nèi)所有相鄰下標(biāo)差是否都等于d。若成立答案加一。該思路的正確性基于一個(gè)簡(jiǎn)單事實(shí)下標(biāo)是天然有序的。由于我們?cè)诒闅v數(shù)組時(shí)按下標(biāo)遞增的順序appendpos[x]內(nèi)部必然按從小到大排列因此只需比較相鄰差是否恒定即可判斷一組位置是否構(gòu)成等差數(shù)列無(wú)需額外排序。由于每個(gè)元素只會(huì)被加入一個(gè)分組、每個(gè)分組只被遍歷一次整體代價(jià)與數(shù)組長(zhǎng)度線(xiàn)性相關(guān)。題解給出的復(fù)雜度為時(shí)間復(fù)雜度O(n)其中 n 是nums的長(zhǎng)度空間復(fù)雜度O(n)用于存儲(chǔ)每個(gè)值的出現(xiàn)位置列表。三、多語(yǔ)言實(shí)現(xiàn)Python / Java / C / Go原題解文檔提供了四種語(yǔ)言的完整實(shí)現(xiàn)這里全部保留并補(bǔ)充關(guān)鍵注釋方便對(duì)照學(xué)習(xí)。Python 3class Solution: def countSpecialIntegers(self, nums: list[int]) - int: pos defaultdict(list) for i, x in enumerate(nums): pos[x].append(i) ans 0 for p in pos.values(): if len(p) 3: continue d p[1] - p[0] if all(y - x d for x, y in pairwise(p)): ans 1 return anspairwise(p)來(lái)自itertools逐個(gè)生成相鄰元素對(duì)(p[0], p[1]), (p[1], p[2]), ...配合all(...)實(shí)現(xiàn)等間隔判定寫(xiě)法最為緊湊。Javaclass Solution { public int countSpecialIntegers(int[] nums) { MapInteger, ListInteger pos new HashMap(); for (int i 0; i nums.length; i) { pos.computeIfAbsent(nums[i], _ - new ArrayList()).add(i); } int ans 0; for (ListInteger p : pos.values()) { if (p.size() 3) { continue; } boolean ok true; int d p.get(1) - p.get(0); for (int i 2; i p.size(); i) { if (p.get(i) - p.get(i - 1) ! d) { ok false; break; } } if (ok) { ans; } } return ans; } }computeIfAbsent(nums[i], _ - new ArrayList()).add(i)是 Java 中「按值分組建索引」的標(biāo)準(zhǔn)寫(xiě)法鍵不存在時(shí)先創(chuàng)建列表再插入下標(biāo)。Cclass Solution { public: int countSpecialIntegers(vectorint nums) { unordered_mapint, vectorint pos; for (int i 0; i nums.size(); i) { pos[nums[i]].push_back(i); } int ans 0; for (auto [_, p] : pos) { if (p.size() 3) { continue; } bool ok true; int d p[1] - p[0]; for (int i 2; i p.size(); i) { if (p[i] - p[i - 1] ! d) { ok false; break; } } ans ok; } return ans; } };C17 的結(jié)構(gòu)化綁定auto [_, p]直接解包出分組列表ans ok利用bool到int的隱式轉(zhuǎn)換省去顯式分支。Gofunc countSpecialIntegers(nums []int) (ans int) { pos : map[int][]int{} for i, x : range nums { pos[x] append(pos[x], i) } next: for _, p : range pos { if len(p) 3 { continue } d : p[1] - p[0] for i : 2; i len(p); i { if p[i]-p[i-1] ! d { continue next } } ans } return }Go 版本有兩處值得學(xué)習(xí)的慣用法具名返回值(ans int)聲明了具名返回變量函數(shù)體內(nèi)ans后直接return即可返回結(jié)果帶標(biāo)簽的continue next當(dāng)內(nèi)層循環(huán)發(fā)現(xiàn)間隔不相等時(shí)直接跳出整組判定并跳到外層循環(huán)處理下一個(gè)分組避免引入額外的布爾標(biāo)志位。四、倉(cāng)庫(kù)源碼級(jí)驗(yàn)證Go 實(shí)現(xiàn)、測(cè)試數(shù)據(jù)與自動(dòng)化測(cè)試該題解在倉(cāng)庫(kù)中并非孤立存在b.go 是完整的可運(yùn)行實(shí)現(xiàn)與之配套的 b.txt 和 b_test.go 共同構(gòu)成了可自動(dòng)驗(yàn)證的最小閉環(huán)。4.1 實(shí)現(xiàn)文件b.go 與題解文檔中的 Go 代碼完全一致用map[int][]int{}分組記錄下標(biāo)再對(duì)每個(gè)分組做等間隔判定邏輯與文檔一一對(duì)應(yīng)。4.2 測(cè)試用例文件b.txt 以「輸入 期望輸出」交替的格式存放了 3 組用例[1,8,1,5,1,5,8,5] 2 [8,8,8,8] 1 [8,6,6,8,8] 0可以手工推演驗(yàn)證用例位置分組判定過(guò)程結(jié)果[1,8,1,5,1,5,8,5]1→[0,2,4]8→[1,6]5→[3,5,7]1 間隔 2 成立8 不足 3 次5 間隔 2 成立2[8,8,8,8]8→[0,1,2,3]間隔恒為 1成立1[8,6,6,8,8]8→[0,3,4]6→[1,2]8 的間隔為 3、1 不相等6 不足 3 次0其中第三組用例特意構(gòu)造了「出現(xiàn)次數(shù)足夠但間隔不等」的反例用來(lái)攔截「只判斷出現(xiàn)次數(shù)、不判斷等間隔」的錯(cuò)誤實(shí)現(xiàn)。4.3 自動(dòng)化測(cè)試入口b_test.go 的測(cè)試函數(shù)只有寥寥數(shù)行核心是調(diào)用了測(cè)試工具庫(kù)的testutil.RunLeetCodeFuncWithFilefunc Test_b(t *testing.T) { if err : testutil.RunLeetCodeFuncWithFile(t, countSpecialIntegers, b.txt, 0); err ! nil { t.Fatal(err) } }從 leetcode/testutil/leetcode.go 的實(shí)現(xiàn)可以看到該框架的工作方式os.ReadFile(filePath)讀取b.txt的原始內(nèi)容經(jīng)trimSpaceAndEmptyLine清洗為逐行字符串通過(guò)反射reflect.TypeOf(f)讀取被測(cè)函數(shù)的入?yún)?出參個(gè)數(shù)據(jù)此推算每組用例占用的行數(shù)fNumIn fNumOut將每組合并為一個(gè) example交給RunLeetCodeFuncWithExamples執(zhí)行解析輸入、調(diào)用被測(cè)函數(shù)、比對(duì)期望輸出并給出通過(guò)/失敗結(jié)論。這意味著只要把新的「輸入 期望輸出」追加進(jìn)b.txt無(wú)需改動(dòng)任何 Go 代碼就能自動(dòng)擴(kuò)展回歸測(cè)試——這正是這套題解倉(cāng)庫(kù)把「題解文檔、實(shí)現(xiàn)代碼、測(cè)試數(shù)據(jù)、測(cè)試框架」四者打通的體現(xiàn)。五、延伸對(duì)比Q1恰好 3 次與 Q2至少 3 次同場(chǎng)雙周賽的 Q1「Count Values With Equally Spaced Occurrences I」與本篇 Q2 使用完全相同的算法骨架唯一的區(qū)別在于判定條件。倉(cāng)庫(kù)中的 a.go 是 Q1 的 Go 實(shí)現(xiàn)func countSpecialIntegers(nums []int) (ans int) { pos : map[int][]int{} for i, x : range nums { pos[x] append(pos[x], i) } for _, p : range pos { if len(p) 3 p[1]-p[0] p[2]-p[1] { ans } } return }兩版代碼的對(duì)照一目了然Q1a.golen(p) 3只統(tǒng)計(jì)「恰好出現(xiàn) 3 次且等間隔」的值因?yàn)殚L(zhǎng)度固定為 3只需比較p[1]-p[0]與p[2]-p[1]這一對(duì)差值Q2b.golen(p) 3通過(guò)跳過(guò)len(p) 3實(shí)現(xiàn)統(tǒng)計(jì)「至少出現(xiàn) 3 次且相鄰間隔全部相等」的值長(zhǎng)度不定需用循環(huán)逐一校驗(yàn)所有相鄰差。Q1 的測(cè)試數(shù)據(jù) a.txt 與 Q2 完全相同但期望輸出不同——比如對(duì)[8,8,8,8]Q1 因 8 出現(xiàn)了 4 次不滿(mǎn)足恰好 3 次而輸出 0Q2 則因 8 的下標(biāo)[0,1,2,3]等間隔而輸出 1。這組「同數(shù)據(jù)、異答案」的用例恰好精準(zhǔn)地刻畫(huà)了兩個(gè)版本的語(yǔ)義差別也提醒我們?cè)诟?jìng)賽或面試中務(wù)必先確認(rèn)「至少」還是「恰好」的表述。六、邊界情況與易錯(cuò)點(diǎn)總結(jié)圍繞該算法有幾點(diǎn)值得在實(shí)戰(zhàn)中留意出現(xiàn)次數(shù)不足 3 次直接跳過(guò)。位置列表長(zhǎng)度小于 3 時(shí)任何等差判定都無(wú)意義下標(biāo)差恒定性等間隔要求是所有相鄰差都相等。即使p[1]-p[0]與p[2]-p[1]相等只要后續(xù)某一段差不同該值依然不能計(jì)入下標(biāo)天然有序遍歷時(shí)按i遞增順序appendpos[x]內(nèi)部無(wú)需排序即可直接做相鄰差比較元素值域pos的鍵是數(shù)組元素本身可能為負(fù)數(shù)或大整數(shù)用哈希表而非按值開(kāi)數(shù)組分組才能保證空間復(fù)雜度與出現(xiàn)元素種類(lèi)相關(guān)而非與值域相關(guān)復(fù)雜度不隨分組數(shù)量退化即使所有元素互不相同每個(gè)分組長(zhǎng)度也為 1內(nèi)層循環(huán)立即跳過(guò)整體仍是 O(n)。結(jié)語(yǔ)「等間隔出現(xiàn)次數(shù) II」的解法雖然短小卻完整展示了哈希位置分組這一基礎(chǔ)而重要的建模技巧把一個(gè)「判斷分布規(guī)律」的問(wèn)題轉(zhuǎn)化為「對(duì)每個(gè)值收集下標(biāo)、再檢查等差數(shù)列」的線(xiàn)性?huà)呙鑶?wèn)題。配合本倉(cāng)庫(kù) b.go、b_test.go、b.txt 以及 leetcode/testutil/leetcode.go 的自動(dòng)化測(cè)試框架你可以直接本地運(yùn)行g(shù)o test復(fù)現(xiàn)全部驗(yàn)證過(guò)程并將這套「位置分組 等差判定」的思路遷移到諸如「字符等間隔出現(xiàn)」「周期性模式檢測(cè)」等同類(lèi)問(wèn)題中。贊分享科學(xué)計(jì)算【免費(fèi)下載鏈接】codeforces-go算法競(jìng)賽模板庫(kù) by 靈茶山艾府 項(xiàng)目地址https://gitcode.com/GitHub_Trending/co/codeforces-go點(diǎn)擊查看免費(fèi)下載相關(guān)推薦codeforces-go 題解剖析力扣雙周賽 176 Q2「前綴連通組」哈希表計(jì)數(shù)解法codeforces go 題解剖析力扣雙周賽 176 Q2「前綴連通組」哈希表計(jì)數(shù)解法 導(dǎo)讀 本題是力扣雙周賽 176 的第二題Number of Pre科學(xué)計(jì)算交替異或劃分計(jì)數(shù)前綴異或 雙哈希表 DP 精講力扣雙周賽 174 Q3 · codeforces-go 題解精讀交替異或劃分計(jì)數(shù)前綴異或 雙哈希表 DP 精講力扣雙周賽 174 Q3 · codeforces go 題解精讀 本篇以 codeforces go科學(xué)計(jì)算codeforces-go 題解精講力扣雙周賽 166 Q1「多數(shù)頻數(shù)字符組」的頻數(shù)分組技巧與 Go 實(shí)現(xiàn)codeforces go 題解精講力扣雙周賽 166 Q1「多數(shù)頻數(shù)字符組」的頻數(shù)分組技巧與 Go 實(shí)現(xiàn) 本篇基于 codeforces go 倉(cāng)庫(kù)中 le科學(xué)計(jì)算上一篇Diablo Edit2終極免費(fèi)暗黑破壞神2存檔修改器完全指南下一篇Video2X實(shí)操指南一條命令完成視頻畫(huà)質(zhì)增強(qiáng)創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考