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(奇数,偶数),小的移到大的上就够了

目录
相关文章
|
3月前
|
算法
LeetCode第66题加一
LeetCode第66题"加一"的解题方法,通过遍历数组从后向前处理每一位的加法,并考虑进位情况,最终实现给定数字加一的功能。
LeetCode第66题加一
|
6月前
LeetCode
LeetCode
39 0
|
6月前
|
算法
leetcode:389. 找不同
leetcode:389. 找不同
28 0
|
6月前
|
消息中间件 Kubernetes NoSQL
LeetCode 3、28、1351
LeetCode 3、28、1351
LeetCode 389. 找不同
给定两个字符串 s 和 t,它们只包含小写字母。
72 0
LeetCode 283. 移动零
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
86 0
leetcode第39题
对回溯法又有了更深的了解,一般的架构就是一个大的 for 循环,然后先 add,接着利用递归进行向前遍历,然后再 remove ,继续循环。而解法二的动态规划就是一定要找到递进的规则,开始的时候就想偏了,导致迟迟想不出来。
leetcode第39题
|
存储
leetcode第52题
可以发现对于同一条副对角线,row + col 的值是相等的。 对于同一条主对角线,row - col 的值是相等的。 我们同样可以用一个 bool 型数组,来保存当前对角线是否有元素,把它们相加相减的值作为下标。 对于 row - col ,由于出现了负数,所以可以加 1 个 n,由 [ - 3, 3 ] 转换为 [ 1 , 7 ] 。
leetcode第52题
leetcode第53题
解法一和解法二的动态规划,只是在定义的时候一个表示以 i 开头的子数组,一个表示以 i 结尾的子数组,却造成了时间复杂度的差异。问题就是解法一中求出了太多的没必要的和,不如解法二直接,只保存最大的和。
leetcode第53题
leetcode第44题
时间复杂度:text 长度是 T,pattern 长度是 P,那么就是 O(TP)。 空间复杂度:O(TP)。 同样的,和第10题一样,可以优化空间复杂度。
leetcode第44题