科學計算【免費下載鏈接】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) 符號位標記訪問」兩類經(jīng)典數(shù)組重排技巧并能直接在本倉庫的周賽目錄結(jié)構(gòu)中復(fù)現(xiàn)與擴展這類題解。題目概述與問題背景題目要求給定數(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ù)下標把nums[ni]后半段第 i 個元素填入ans[2i1]奇數(shù)下標。本質(zhì)上是「兩個指針 一個目標下標」的線性掃描指針 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)用方負責釋放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]取后半段元素寫法比按下標循環(huán)更簡潔同時make([]int, n*2)保證了寫入ans[i*21]時下標不越界當 i n-1 時i*21 2n-1 恰好是數(shù)組最后一個下標。JavaScriptconst ans Array(n * 2);預(yù)留長度后按位寫入。Rust注意n是i32需要先let n n as usize;再用于切片下標與vec![0; n * 2]。復(fù)雜度分析時間復(fù)雜度O(n)單趟循環(huán)完成全部 2n 個元素的填入。空間復(fù)雜度O(n)額外的新數(shù)組ans。方法二原地交換置換環(huán) 符號位標記方法二把空間復(fù)雜度壓縮到 O(1)核心思想是把下標變換看成置換利用置換環(huán)一次性歸位所有元素。這是本文最有價值的進階技巧。下標變換的置換結(jié)構(gòu)設(shè) f(i) 為「下標 i 處的元素在答案中的下標」。由題意若 i n前半段則 f(i) 2i若 i n后半段則 f(i) (i - n) * 2 1。原題解以 n 4 為例給出了完整的環(huán)結(jié)構(gòu)nums[0]的目標就是 0不變環(huán) 11 → 2 → 4 → 1即nums[1]移到下標 2nums[2]移到下標 4nums[4]移到下標 1環(huán) 23 → 6 → 5 → 3nums[7]的目標就是 7不變。示例 2 的nums [1,2,3,4,4,3,2,1]按上述過程執(zhí)行結(jié)果為[1,4,2,3,3,2,4,1]與官方示例輸出完全一致該用例同樣收錄在倉庫測試文件中見下文。如何判斷元素是否已訪問如果按樸素思路用布爾數(shù)組vis記錄訪問過的下標額外空間依然是 O(n)與方法一無異。原題解給出了一個更省空間的巧妙做法本題nums[i]都是正數(shù)可以把訪問過的數(shù)加個負號變成相反數(shù)當作「已訪問」標記。遍歷到一個負數(shù)時直接跳過最后把所有數(shù)取反復(fù)原成正數(shù)即為答案。具體流程遍歷nums跳過值為負數(shù)的下標已被標記過從當前下標cur i出發(fā)反復(fù)計算目標下標nxt cur n ? cur * 2 : (cur - n) * 2 1若nxt i說明走完了一個環(huán)把當前元素取負寫回nums[i]后 break否則把當前元素 x 填入nums[nxt]寫入負數(shù)-x以標記訪問同時把nums[nxt]原來的值正值作為新的 x 繼續(xù)走環(huán)全部環(huán)處理完后把數(shù)組整體取反復(fù)原。答疑為什么每個元素恰好被標記一次原題解附帶了一個關(guān)鍵答疑值得單獨強調(diào)問這個做法是否會把一個元素標記多次取反多次或者有元素沒有被標記答設(shè) f(i) 是下標為 i 的元素在答案中的下標。根據(jù)題意f 是[0, 1, 2, ..., 2n-1]的一個置換。由于置換可以拆分成若干個環(huán)所以每個元素恰好被標記一次。這解釋了算法正確性置換的環(huán)分解保證「從任意未訪問元素出發(fā)沿 f 走必然回到起點并恰好覆蓋環(huán)上所有元素一次」從而既不會漏標也不會重復(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 // 用負數(shù)表示訪問過 break } // 把 x 填入 nums[nxt]用負數(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ù)雜度O(n)。雖然代碼看起來是二重循環(huán)外層遍歷 內(nèi)層走環(huán)但每個元素「被標記為負數(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中同時保留兩種解法且注釋直接引用題解中的「已訪問 / 回到起點」標記邏輯代碼與 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。運行方式為標準 Go 測試命令go test ./leetcode/weekly/192/a/ -run Test_a -v測試框架還內(nèi)置了超時檢測DebugTLE默認 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ù)組同樣是「按下標重排數(shù)組」的直接應(yīng)用用新數(shù)組或原地技巧均可解。41. 缺失的第一個正數(shù)經(jīng)典原地哈希題同樣依賴「把數(shù)組元素的值作為下標信息、用正負號標記狀態(tài)」的思想與本題「負數(shù)標記已訪問」異曲同工。從這兩道題可以提煉出一個通用套路當題目要求數(shù)組重排、去重或狀態(tài)標記且元素值域允許「符號翻轉(zhuǎn)」或「取負取反」時?？梢杂梅栁淮?O(n) 的輔助數(shù)組把空間復(fù)雜度壓到 O(1)。這也是排列、置換環(huán)、原地哈希一類題目的核心考點。小結(jié)圍繞「重新排列數(shù)組」這道周賽 A 題本文完整覆蓋了原題解文檔的兩個解法方法一創(chuàng)建新數(shù)組雙指針線性填充O(n) 時間、O(n) 空間邏輯直白、最適合作為保底寫法方法二原地交換將下標變換視作置換、沿環(huán)歸位元素并用「負數(shù)標記訪問」省去 vis 數(shù)組O(n) 時間、O(1) 空間是值得反復(fù)體會的進階技巧配合倉庫中 a.go 的源碼與 a_test.go 的 5 組測試用例兩種算法均可在本地直接驗證。掌握「置換環(huán) 符號位標記」后你不只能 AC 這一道題還能將其遷移到缺失的第一個正數(shù)、數(shù)組輪轉(zhuǎn)、原地哈希等一系列排列類問題中這也是本倉庫將題解、源碼與測試統(tǒng)一歸檔的價值所在。贊分享科學計算【免費下載鏈接】codeforces-go算法競賽模板庫 by 靈茶山艾府 項目地址https://gitcode.com/GitHub_Trending/co/codeforces-go點擊查看免費下載相關(guān)推薦把數(shù)組當棧與雙指針交換LeetCode 283 移動零的兩種原地解法精講codeforces-go 倉庫題解把數(shù)組當棧與雙指針交換LeetCode 283 移動零的兩種原地解法精講codeforces go 倉庫題解 導(dǎo)讀 本文圍繞本倉庫題解文檔 leetcod科學計算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），僅供參考