5213 玩筹码 leetcode

简介: 5213 玩筹码 leetcode

数轴上放置了一些筹码,每个筹码的位置存在数组 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


```cpp

class Solution {

public:

   int minCostToMoveChips(vector<int>& chips) {

       int d=0,s=0;

       for(int i=0;i<chips.size();i++)

       {     int p=chips[i];

              if(p%2)

                  d++;

              else

                  s++;

       }

       return min(d,s);

   }

};

```

提示:题意重点《 将第 i 个筹码向左或者右移动 2 个单位,代价为 0。

将第 i 个筹码向左或者右移动 1 个单位,代价为 1 》

可以把他们分为奇数与偶数,奇数类或者偶数类内部之间互相移动不会消耗,我们就可以把问题分解为求 min(奇数,偶数),小的移到大的上就够了

目录
相关文章
|
6天前
leetcode-1219:黄金矿工
leetcode-1219:黄金矿工
41 0
leetcode 827 最大人工岛
leetcode 827 最大人工岛
46 0
leetcode 827 最大人工岛
leetcode 283 移动零
leetcode 283 移动零
38 0
|
算法
【LeetCode】这么简单的题,豆编又不会!
【LeetCode】这么简单的题,豆编又不会!
109 0
leetcode第55题
当自己按照 45 题的思路写完的时候,看 Solution 的时候都懵逼了,这道题竟然这么复杂?不过 Solution 把问题抽象成动态规划的思想,以及优化的过程还是非常值得学习的。
leetcode第55题
|
算法
leetcode第45题
时间复杂度:O(n)。 空间复杂度:O(1)。 这里要注意一个细节,就是 for 循环中,i < nums.length - 1,少了末尾。因为开始的时候边界是第 0 个位置,steps 已经加 1 了。如下图,如果最后一步刚好跳到了末尾,此时 steps 其实不用加 1 了。如果是 i < nums.length,i 遍历到最后的时候,会进入 if 语句中,steps 会多加 1 。
leetcode第45题
leetcode第39题
对回溯法又有了更深的了解,一般的架构就是一个大的 for 循环,然后先 add,接着利用递归进行向前遍历,然后再 remove ,继续循环。而解法二的动态规划就是一定要找到递进的规则,开始的时候就想偏了,导致迟迟想不出来。
leetcode第39题
leetcode第13题
解法一 先来一种不优雅的,也就是我开始的想法。就是遍历字符串,然后转换就可以,但同时得考虑 IV,IX 那些特殊情况。
leetcode第13题
leetcode第21题
总 递归看起来,两个字,优雅!但是关于递归的时间复杂度,空间复杂度的求法,先留个坑吧。
leetcode第21题