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