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