LEETCODE 1217. Play with Chips 解题思路分析

题目大意：

玩筹码

数轴上放置了一些筹码，每个筹码的位置存在数组 chips 当中。

你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：

• 将第 i 个筹码向左或者右移动 2 个单位，代价为 0。
• 将第 i 个筹码向左或者右移动 1 个单位，代价为 1。

最开始的时候，同一位置上也可能放着两个或者更多的筹码。

返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。

示例 1：

输入：chips = [1,2,3]
输出：1
解释：第二个筹码移动到位置三的代价是 1，第一个筹码移动到位置三的代价是 0，总代价为 1。

示例 2：

输入：chips = [2,2,2,3,3]
输出：2
解释：第四和第五个筹码移动到位置二的代价都是 1，所以最小总代价为 2。

提示：

• 1 <= chips.length <= 100
• 1 <= chips[i] <= 10^9

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1217

解题思路分析：

题目说的很清楚，移动1步的cost为1，移动2步cost为0。进而可以推出，移动奇数步的cost为1，因为奇数可以由N个2和1个1组成。同理移动偶数步的cost为0（偶数由N个2组成）。再思考一下，其实题目就可以理解为，奇数位移动到偶数位cost为1，偶数位移动到奇数位cost也为1，奇数位之间或者偶数位之间移动不需要cost。

这样理解后问题就清晰了，我们只要分别统计出奇数位和偶数位的数字各有多少，将少的向多的位置移动一定是最优解。举个例子：比如偶数位有10个数字，奇数位有5个数字，将所有偶数位移动到奇数位需要10个cost，反之只需要5个cost。因此最终答案应该是个数较小的那个值。

看下完整代码：

public int minCostToMoveChips(int[] chips) {
    int oddCount=0,evenCount=0; // 分别统计奇数位与偶数位的元素个数
    for(int i=0;i<chips.length;i++){ // 循环数组
        if(chips[i] % 2 == 1){ // 如果是奇数
            oddCount++; // 奇数位个数加一
        }
    }
    evenCount = chips.length - oddCount; // 计算出偶数位的个数
    // 返回一个较小的数值
    return oddCount > evenCount ? evenCount : oddCount;
}

本题解法运行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Play with Chips.

Memory Usage: 34.6 MB, less than 100.00% of Java online submissions for Play with Chips.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1217-play-with-chips-解题思路分析/