LeetCode 1217 題解Minimum Cost to Move Chips to The Same Position奇偶性貪心Go 實現【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go導讀本文圍繞 LeetCode 第 1217 題「移動籌碼到同一位置的最低成本」Minimum Cost to Move Chips to The Same Position展開基于 LeetCode-Go 倉庫中該題的解法和測試用例完整講解題目含義、奇偶性拆解的核心思路、Go 源碼實現與復雜度分析。讀完本文你將掌握一類「移動兩格免費、移動一格收費」問題的通用解法只需統計奇偶位置籌碼數量并取較小值即可在線性時間內得到答案。題目描述數軸上有一些籌碼其中第i個籌碼的位置是chips[i]。你可以對任意一個籌碼執行下面兩種操作操作次數不限可以為 0 次將第i個籌碼向左或向右移動2 個單位代價為0。將第i個籌碼向左或向右移動1 個單位代價為1。初始時同一個位置上可能放著兩個或更多的籌碼。要求返回將**所有籌碼移動到同一位置可以是任意位置**所需的最小代價。示例 1Input: chips [1,2,3] Output: 1 Explanation: 把第 2 個籌碼移動到位置 3代價為 1第 1 個籌碼移動到位置 3代價為 0。總代價為 1。示例 2Input: chips [2,2,2,3,3] Output: 2 Explanation: 把第 4、5 個籌碼移動到位置 2各花費代價 1總代價為 2。約束條件1 chips.length 1001 chips[i] 10^9題目大意數軸上放置了一些籌碼每個籌碼的位置存放在數組chips中。核心規則只有兩條向左或向右移動 2 個單位代價為0免費移動向左或向右移動 1 個單位代價為1付費移動。最終需要把全部籌碼聚攏到數軸上的某一個位置該位置可以是任意整數坐標求最小總代價。解題思路奇偶性拆解這是本題的關鍵所在也是整道題從「看似需要搜索所有可能目標位置」變為「一行公式」的突破口。第一步免費移動意味著什么移動 2 個單位代價為 0意味著改變的位置奇偶性不變x ± 2與x同奇偶。也就是說偶數位置上的籌碼可以零代價移動到任意其他偶數位置奇數位置上的籌碼可以零代價移動到任意其他奇數位置。反過來只有跨越奇偶邊界x ± 1的那一步才需要花費 1。第二步把問題壓縮成兩摞籌碼利用上述規則我們可以把所有籌碼無代價地分別摞在同一個奇數位置和同一個偶數位置上。此時全場的籌碼被歸約為兩摞一摞在某個奇數位置一摞在某個偶數位置這兩摞的間距為 1相鄰因為任意一個奇數與任意一個偶數之間都可以通過選擇合適的位置讓它們緊鄰例如把奇數摞放在位置k、偶數摞放在位置k1。第三步最后一步合并最后只需要把相鄰的這兩摞籌碼合并到同一位置。由于奇偶相鄰合并必走一步「移動 1 個單位」代價為 1且每移動一個籌碼收 1。所以最優策略不言自明移動籌碼數量較少的那一摞。即統計所有籌碼中位于奇數位置的個數odd統計所有籌碼中位于偶數位置的個數even答案是min(odd, even)。至此本題從「枚舉目標位置」降維成「數一次奇偶」時間復雜度 O(n)。Go 源碼實現倉庫中本題的實現位于 leetcode/1217.Minimum-Cost-to-Move-Chips-to-The-Same-Position/1217. Minimum Cost to Move Chips to The Same Position.go源碼如下package leetcode func minCostToMoveChips(chips []int) int { odd, even : 0, 0 for _, c : range chips { if c%2 0 { even } else { odd } } return min(odd, even) } func min(a int, b int) int { if a b { return b } return a }實現要點一次遍歷完成統計對chips中的每個位置值c做c % 2判斷0歸入偶數計數1歸入奇數計數不需要對位置本身做任何排序或建圖大值位置無影響約束中chips[i]最大可達10^9但算法只關心奇偶性因此數值范圍再大也不影響正確性與性能就地返回無額外數組、無哈希表僅使用兩個int計數變量空間復雜度 O(1)。測試用例驗證倉庫為本題配套了測試文件 leetcode/1217.Minimum-Cost-to-Move-Chips-to-The-Same-Position/1217. Minimum Cost to Move Chips to The Same Position_test.go采用「參數 期望答案」的結構化表格風格組織用例與題目給出的兩個示例一一對應輸入chips期望輸出過程[1, 2, 3]1奇數位置籌碼 2 個1、3偶數位置籌碼 1 個2min(2, 1) 1[2, 2, 2, 3, 3]2偶數位置籌碼 3 個奇數位置籌碼 2 個min(3, 2) 2測試入口Test_Problem1217會逐條執行用例并打印輸入輸出例如fmt.Printf(【input】:%v 【output】:%v\n, p, minCostToMoveChips(p.arr))運行方式在倉庫根目錄執行go test -v -run Test_Problem1217 ./leetcode/1217.Minimum-Cost-to-Move-Chips-to-The-Same-Position/整個倉庫以 100% 測試覆蓋率為目標根目錄的 gotest.sh 腳本使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性為所有 LeetCode 題目生成原子模式的覆蓋率報告本文件同樣被納入該覆蓋范圍項目使用 Go 1.19見 go.mod。復雜度分析時間復雜度O(n)只需對chips數組做一次線性掃描n為chips.length約束上限為 100。空間復雜度O(1)僅使用兩個常數級計數器。無論籌碼分布在多少個位置、坐標值多大求解過程都不會隨輸入規模產生額外內存開銷。邊界情況與思維延伸所有籌碼同奇偶例如[2, 4, 6]此時even 3, odd 0答案為 0——它們可以零代價聚攏到任意一個偶數位置。只有一個籌碼odd與even中必有一個為 1、一個為 0答案為 0無需任何移動。答案為什么與目標位置無關因為兩摞籌碼可以零代價各自聚攏到相鄰的奇偶位置上最終「哪摞少就移動哪摞」代價只取決于奇偶兩類的數量差與具體坐標無關。這是本題最反直覺也最優雅的一點。進一步可以把本題抽象為一種通用模式當某類操作這里是移動 2 格的成本為 0 時先按不變量奇偶性把狀態空間壓縮成等價類再在等價類之間做最小代價的歸并。同類思想也常見于其他「按位/按模分組」的貪心題中。若想查看更多按專題分類的題目總結可瀏覽倉庫 topic 目錄下的專題圖如位運算、雙指針等。【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考