当前位置：网站首页>leetcode-每日一题1217. 玩筹码(贪心+位运算)

leetcode-每日一题1217. 玩筹码(贪心+位运算)

2022-07-31 05:10:00 【lin钟一】

在这里插入图片描述
题目链接：https://leetcode.cn/problems/minimum-cost-to-move-chips-to-the-same-position/

思路

直接想法
这题要求得到移动到同一格子的最小成本，跳两格的成本是0，跳一格的成本是1，所以我们需要尽量跳两格，发现刚好可以分成下标奇偶两列的棋子，可以把奇偶两列的棋子都移动到相邻的点上(移动到1和2上)，此时我们只需要对比移动那块的棋子成本最低即可

算法

遍历棋子下标 position 数组
- 判断元素的奇偶性，把奇数下标记录在odd 元素里
对比奇数格子上的棋子和偶数格子上的棋子的数量，返回两者最小值即可

代码示例

func minCostToMoveChips(position []int) int {
    
    odd := 0
    for _, v := range position {
    
        if v & 1 == 1{
    
            odd++
        }
    }
    //len(position) - odd表示偶数格子的数量
    if odd > len(position) - odd {
    
        return len(position) - odd
    }
    return odd
}