科學(xué)計(jì)算【免費(fèi)下載鏈接】codeforces-go算法競(jìng)賽模板庫(kù) by 靈茶山艾府 項(xiàng)目地址https://gitcode.com/GitHub_Trending/co/codeforces-go點(diǎn)擊查看免費(fèi)下載本文以 LeetCode 周賽 192 的 A 題「重新排列數(shù)組Shuffle the Array1470」為切入點(diǎn)完整講解兩種解法O(n) 額外空間的「創(chuàng)建新數(shù)組」與 O(1) 額外空間的「置換環(huán)原地交換」并結(jié)合算法競(jìng)賽模板庫(kù) codeforces-go 中該題對(duì)應(yīng)的 Go 源碼實(shí)現(xiàn) 與 單元測(cè)試用例從源碼級(jí)驗(yàn)證兩種算法的正確性。讀完本文你將掌握「雙指針線性填充」與「利用置換環(huán) 符號(hào)位標(biāo)記訪問(wèn)」兩類(lèi)經(jīng)典數(shù)組重排技巧并能直接在本倉(cāng)庫(kù)的周賽目錄結(jié)構(gòu)中復(fù)現(xiàn)與擴(kuò)展這類(lèi)題解。題目概述與問(wèn)題背景題目要求給定數(shù)組nums它由x1, x2, ..., xn, y1, y2, ..., yn構(gòu)成即前 n 個(gè)元素與后 n 個(gè)元素分別構(gòu)成兩段。請(qǐng)重新排列數(shù)組使其變?yōu)閇x1, y1, x2, y2, ..., xn, yn]并返回該新數(shù)組。本題出現(xiàn)在本倉(cāng)庫(kù)的周賽歸檔目錄 leetcode/weekly/192/ 中對(duì)應(yīng) 2020 年 6 月的力扣第 192 場(chǎng)周賽 A 題同場(chǎng)次的 B/C/D 題如 1472.md 的瀏覽器歷史記錄設(shè)計(jì)題也歸檔在相鄰目錄中方便整套周賽復(fù)盤(pán)。歸檔結(jié)構(gòu)遵循本倉(cāng)庫(kù)統(tǒng)一的「題目編號(hào) 題解 md 解法源碼 測(cè)試文件」模式詳見(jiàn)下文。方法一創(chuàng)建新數(shù)組雙指針線性填充這是最直觀、最容易寫(xiě)對(duì)的解法時(shí)間復(fù)雜度 O(n)空間復(fù)雜度 O(n)。算法過(guò)程創(chuàng)建一個(gè)長(zhǎng)為 2n 的數(shù)組ans作為答案。根據(jù)題意對(duì)于 i 0, 1, ..., n-1把nums[i]前半段第 i 個(gè)元素填入ans[2i]偶數(shù)下標(biāo)把nums[ni]后半段第 i 個(gè)元素填入ans[2i1]奇數(shù)下標(biāo)。本質(zhì)上是「兩個(gè)指針 一個(gè)目標(biāo)下標(biāo)」的線性掃描指針 i 同時(shí)遍歷前、后兩段寫(xiě)入位置每次 2。各語(yǔ)言實(shí)現(xiàn)要點(diǎn)原題解文檔給出了 Python3 / Java / C / C / Go / JavaScript / Rust 七種語(yǔ)言的等價(jià)實(shí)現(xiàn)。核心差異僅在語(yǔ)法層面Python3ans [0] * (2 * n)預(yù)分配然后ans[i * 2] nums[i]; ans[i * 2 1] nums[n i]。Java / C以n * 2為長(zhǎng)度構(gòu)造新數(shù)組循環(huán)內(nèi)同樣按2i與2i1雙寫(xiě)。C需要額外通過(guò)*returnSize輸出數(shù)組長(zhǎng)度*returnSize n * 2;由調(diào)用方負(fù)責(zé)釋放malloc的內(nèi)存。Go本倉(cāng)庫(kù)中的實(shí)現(xiàn) a.gofunc shuffle1(nums []int, n int) []int { ans : make([]int, n*2) for i, x : range nums[:n] { ans[i*2] x ans[i*21] nums[ni] } return ans }這里用range nums[:n]直接迭代前半段切片配合nums[ni]取后半段元素寫(xiě)法比按下標(biāo)循環(huán)更簡(jiǎn)潔同時(shí)make([]int, n*2)保證了寫(xiě)入ans[i*21]時(shí)下標(biāo)不越界當(dāng) i n-1 時(shí)i*21 2n-1 恰好是數(shù)組最后一個(gè)下標(biāo)。JavaScriptconst ans Array(n * 2);預(yù)留長(zhǎng)度后按位寫(xiě)入。Rust注意n是i32需要先let n n as usize;再用于切片下標(biāo)與vec![0; n * 2]。復(fù)雜度分析時(shí)間復(fù)雜度O(n)單趟循環(huán)完成全部 2n 個(gè)元素的填入?？臻g復(fù)雜度O(n)額外的新數(shù)組ans。方法二原地交換置換環(huán) 符號(hào)位標(biāo)記方法二把空間復(fù)雜度壓縮到 O(1)核心思想是把下標(biāo)變換看成置換利用置換環(huán)一次性歸位所有元素。這是本文最有價(jià)值的進(jìn)階技巧。下標(biāo)變換的置換結(jié)構(gòu)設(shè) f(i) 為「下標(biāo) i 處的元素在答案中的下標(biāo)」。由題意若 i n前半段則 f(i) 2i若 i n后半段則 f(i) (i - n) * 2 1。原題解以 n 4 為例給出了完整的環(huán)結(jié)構(gòu)nums[0]的目標(biāo)就是 0不變環(huán) 11 → 2 → 4 → 1即nums[1]移到下標(biāo) 2nums[2]移到下標(biāo) 4nums[4]移到下標(biāo) 1環(huán) 23 → 6 → 5 → 3nums[7]的目標(biāo)就是 7不變。示例 2 的nums [1,2,3,4,4,3,2,1]按上述過(guò)程執(zhí)行結(jié)果為[1,4,2,3,3,2,4,1]與官方示例輸出完全一致該用例同樣收錄在倉(cāng)庫(kù)測(cè)試文件中見(jiàn)下文。如何判斷元素是否已訪問(wèn)如果按樸素思路用布爾數(shù)組vis記錄訪問(wèn)過(guò)的下標(biāo)額外空間依然是 O(n)與方法一無(wú)異。原題解給出了一個(gè)更省空間的巧妙做法本題nums[i]都是正數(shù)可以把訪問(wèn)過(guò)的數(shù)加個(gè)負(fù)號(hào)變成相反數(shù)當(dāng)作「已訪問(wèn)」標(biāo)記。遍歷到一個(gè)負(fù)數(shù)時(shí)直接跳過(guò)最后把所有數(shù)取反復(fù)原成正數(shù)即為答案。具體流程遍歷nums跳過(guò)值為負(fù)數(shù)的下標(biāo)已被標(biāo)記過(guò)從當(dāng)前下標(biāo)cur i出發(fā)反復(fù)計(jì)算目標(biāo)下標(biāo)nxt cur n ? cur * 2 : (cur - n) * 2 1若nxt i說(shuō)明走完了一個(gè)環(huán)把當(dāng)前元素取負(fù)寫(xiě)回nums[i]后 break否則把當(dāng)前元素 x 填入nums[nxt]寫(xiě)入負(fù)數(shù)-x以標(biāo)記訪問(wèn)同時(shí)把nums[nxt]原來(lái)的值正值作為新的 x 繼續(xù)走環(huán)全部環(huán)處理完后把數(shù)組整體取反復(fù)原。答疑為什么每個(gè)元素恰好被標(biāo)記一次原題解附帶了一個(gè)關(guān)鍵答疑值得單獨(dú)強(qiáng)調(diào)問(wèn)這個(gè)做法是否會(huì)把一個(gè)元素標(biāo)記多次取反多次或者有元素沒(méi)有被標(biāo)記答設(shè) f(i) 是下標(biāo)為 i 的元素在答案中的下標(biāo)。根據(jù)題意f 是[0, 1, 2, ..., 2n-1]的一個(gè)置換。由于置換可以拆分成若干個(gè)環(huán)所以每個(gè)元素恰好被標(biāo)記一次。這解釋了算法正確性置換的環(huán)分解保證「從任意未訪問(wèn)元素出發(fā)沿 f 走必然回到起點(diǎn)并恰好覆蓋環(huán)上所有元素一次」從而既不會(huì)漏標(biāo)也不會(huì)重復(fù)取反。Go 實(shí)現(xiàn)本倉(cāng)庫(kù) a.gofunc shuffle(nums []int, n int) []int { for i, x : range nums { if x 0 { // 已訪問(wèn) continue } for cur : i; ; { // 元素 x 要填入 nums[nxt] nxt : cur * 2 if cur n { nxt (cur-n)*2 1 } if nxt i { // 回到起點(diǎn) nums[i] -x // 用負(fù)數(shù)表示訪問(wèn)過(guò) break } // 把 x 填入 nums[nxt]用負(fù)數(shù)表示訪問(wèn)過(guò) // 同時(shí)把原來(lái)位于 nxt 的數(shù)記為 x x, nums[nxt] nums[nxt], -x cur nxt } } // 復(fù)原 for i, x : range nums { nums[i] -x } return nums }注意 Go 版本在計(jì)算nxt時(shí)沒(méi)有使用三目運(yùn)算符而是用if cur n分支這是 Go 語(yǔ)法限制下的等價(jià)寫(xiě)法。Python、Java、C、C、JavaScript 版本邏輯完全一致其中 C 使用swap(x, nums[nxt])后對(duì)nums[nxt]取負(fù)語(yǔ)義相同。復(fù)雜度分析時(shí)間復(fù)雜度O(n)。雖然代碼看起來(lái)是二重循環(huán)外層遍歷 內(nèi)層走環(huán)但每個(gè)元素「被標(biāo)記為負(fù)數(shù)」只會(huì)發(fā)生恰好一次內(nèi)層循環(huán)在所有環(huán)上的總步數(shù)之和為 n因此總循環(huán)次數(shù)是 O(n)?？臻g復(fù)雜度O(1)只使用若干臨時(shí)變量復(fù)用原數(shù)組完成重排。倉(cāng)庫(kù)源碼與測(cè)試驗(yàn)證解法源碼的歸檔形態(tài)本題解在倉(cāng)庫(kù)中以「題解 實(shí)現(xiàn) 測(cè)試」三位一體的方式歸檔在 leetcode/weekly/192/a/ 目錄1470.md本文講解的完整題解文檔方法一 方法二 答疑 相似題目a.go包含shuffle1方法一與shuffle方法二兩個(gè)實(shí)現(xiàn)函數(shù)簽名與力扣要求的func shuffle(nums []int, n int) []int一致a_test.go自動(dòng)生成的單元測(cè)試。同名文件a.go中同時(shí)保留兩種解法且注釋直接引用題解中的「已訪問(wèn) / 回到起點(diǎn)」標(biāo)記邏輯代碼與 1470.md 的算法描述一一對(duì)應(yīng)便于對(duì)照閱讀。測(cè)試用例與運(yùn)行方式a_test.go 由倉(cāng)庫(kù)的測(cè)試生成器copypasta/template/leetcode/generator_test.go自動(dòng)生成其測(cè)試數(shù)據(jù)覆蓋了力扣官方全部示例輸入 numsn期望輸出[2,5,1,3,4,7]3[2,3,5,4,1,7][1,2,3,4,4,3,2,1]4[1,4,2,3,3,2,4,1][1,1,2,2]2[1,2,1,2][0,1,2,3,4,5]3[0,1,2,3,4,5][0,1,2,3,4,5,6,7]4[0,1,2,3,4,5,6,7]后兩組「輸入恰好是答案」的用例很有價(jià)值它們專(zhuān)門(mén)用來(lái)驗(yàn)證原地算法不會(huì)破壞已有序的數(shù)組例如 n4 時(shí)[0,1,2,3,4,5,6,7]的每個(gè)環(huán)都是自環(huán)元素本就該留在原位若環(huán)處理邏輯有誤如重復(fù)取反就會(huì)立刻暴露。測(cè)試調(diào)用的是倉(cāng)庫(kù)統(tǒng)一的測(cè)試框架testutil.RunLeetCodeFuncWithExamples定義于 leetcode/testutil/leetcode.go該框架通過(guò)反射解析測(cè)試數(shù)據(jù)examples每行的前 fNumIn 個(gè)字符串作為輸入、后 fNumOut 個(gè)作為期望輸出自動(dòng)完成類(lèi)型解析parseRawArg支持 int、slice、string、TreeNode 等類(lèi)型與結(jié)果比對(duì)assert.Equal。運(yùn)行方式為標(biāo)準(zhǔn) Go 測(cè)試命令go test ./leetcode/weekly/192/a/ -run Test_a -v測(cè)試框架還內(nèi)置了超時(shí)檢測(cè)DebugTLE默認(rèn) 2 秒見(jiàn) leetcode/testutil/config.go與答案錯(cuò)誤提示targetCaseNum : 0表示跑全部用例改為正數(shù)可只跑指定用例改為-1則跑最后一個(gè)用例。測(cè)試框架與周賽歸檔流水線理解測(cè)試文件的開(kāi)頭注釋「Code generated by copypasta/template/leetcode/generator_test.go」能幫你更好地利用本倉(cāng)庫(kù)倉(cāng)庫(kù)作者通過(guò) generator_test.go 中的TestWeekly/TestBiweekly自動(dòng)獲取下一場(chǎng)周賽/雙周賽的題目信息登錄使用環(huán)境變量LEETCODE_USERNAME_ZH、LEETCODE_PASSWORD_ZH可自定義LEETCODE_COMMENT注釋自動(dòng)生成a.go、a_test.go與測(cè)試數(shù)據(jù)并按leetcode/weekly/場(chǎng)次/題號(hào)/的約定歸檔。這意味著每周賽題發(fā)布后題解、實(shí)現(xiàn)與測(cè)試會(huì)被一次性補(bǔ)齊——本文分析的 1470.md 正是這一流水線的產(chǎn)物之一。相似題目與延伸原題解末尾給出了兩道思路相近的經(jīng)典題目可用于鞏固「置換 / 排列類(lèi)數(shù)組操作」這一主題1920. 基于排列構(gòu)建數(shù)組同樣是「按下標(biāo)重排數(shù)組」的直接應(yīng)用用新數(shù)組或原地技巧均可解。41. 缺失的第一個(gè)正數(shù)經(jīng)典原地哈希題同樣依賴「把數(shù)組元素的值作為下標(biāo)信息、用正負(fù)號(hào)標(biāo)記狀態(tài)」的思想與本題「負(fù)數(shù)標(biāo)記已訪問(wèn)」異曲同工。從這兩道題可以提煉出一個(gè)通用套路當(dāng)題目要求數(shù)組重排、去重或狀態(tài)標(biāo)記且元素值域允許「符號(hào)翻轉(zhuǎn)」或「取負(fù)取反」時(shí)?？梢杂梅?hào)位代替 O(n) 的輔助數(shù)組把空間復(fù)雜度壓到 O(1)。這也是排列、置換環(huán)、原地哈希一類(lèi)題目的核心考點(diǎn)。小結(jié)圍繞「重新排列數(shù)組」這道周賽 A 題本文完整覆蓋了原題解文檔的兩個(gè)解法方法一創(chuàng)建新數(shù)組雙指針線性填充O(n) 時(shí)間、O(n) 空間邏輯直白、最適合作為保底寫(xiě)法方法二原地交換將下標(biāo)變換視作置換、沿環(huán)歸位元素并用「負(fù)數(shù)標(biāo)記訪問(wèn)」省去 vis 數(shù)組O(n) 時(shí)間、O(1) 空間是值得反復(fù)體會(huì)的進(jìn)階技巧配合倉(cāng)庫(kù)中 a.go 的源碼與 a_test.go 的 5 組測(cè)試用例兩種算法均可在本地直接驗(yàn)證。掌握「置換環(huán) 符號(hào)位標(biāo)記」后你不只能 AC 這一道題還能將其遷移到缺失的第一個(gè)正數(shù)、數(shù)組輪轉(zhuǎn)、原地哈希等一系列排列類(lèi)問(wèn)題中這也是本倉(cāng)庫(kù)將題解、源碼與測(cè)試統(tǒng)一歸檔的價(jià)值所在。贊分享科學(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)推薦把數(shù)組當(dāng)棧與雙指針交換LeetCode 283 移動(dòng)零的兩種原地解法精講codeforces-go 倉(cāng)庫(kù)題解把數(shù)組當(dāng)棧與雙指針交換LeetCode 283 移動(dòng)零的兩種原地解法精講codeforces go 倉(cāng)庫(kù)題解 導(dǎo)讀 本文圍繞本倉(cāng)庫(kù)題解文檔 leetcod科學(xué)計(jì)算LogicStack-LeetCode 刷穿 LeetCode1470. 重新排列數(shù)組簡(jiǎn)單—— 雙指針模擬的入門(mén)范本LogicStack LeetCode 刷穿 LeetCode1470. 重新排列數(shù)組簡(jiǎn)單—— 雙指針模擬的入門(mén)范本 本篇題解以 LogicStack L教程文檔LeetCode-Go 第 27 題 Remove Element原地刪除數(shù)組元素的交換雙指針解法與全量測(cè)試驗(yàn)證LeetCode Go 第 27 題 Remove Element原地刪除數(shù)組元素的交換雙指針解法與全量測(cè)試驗(yàn)證 本篇基于 LeetCode Go 倉(cāng)庫(kù)中 l示例工程創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考