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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1217-play-with-chips-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

LEETCODE 1217. Play with Chips 解题思路分析》有1条回应

    发表评论

    您的电子邮箱地址不会被公开。