LeetCode 1217 题解：Minimum Cost to Move Chips to The Same Position（奇偶性贪心，Go 实现）

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），仅供参考