【LeetCode每日一题】——1217.玩筹码

一【题目类别】

• 贪心算法

二【题目难度】

• 简单

三【题目编号】

• 1217.玩筹码

四【题目描述】

• 有 n 个筹码。第 i 个筹码的位置是 position[i] 。
• 我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个筹码的位置从 position[i] 改变为:
  • position[i] + 2 或 position[i] - 2 ，此时 cost = 0
  • position[i] + 1 或 position[i] - 1 ，此时 cost = 1
• 返回将所有筹码移动到同一位置上所需要的 最小代价 。

五【题目示例】

• 示例 1：

  • 
  • 输入：position = [1,2,3]
  • 输出：1
  • 解释：第一步:将位置3的筹码移动到位置1，成本为0。第二步:将位置2的筹码移动到位置1，成本= 1。总成本是1。

• 示例 2：

  • 
  • 输入：position = [2,2,2,3,3]
  • 输出：2
  • 解释：我们可以把位置3的两个筹码移到位置2。每一步的成本为1。总成本= 2。

• 示例 3:

  • 输入：position = [1,1000000000]
  • 输出：1

六【解题思路】

• 这个题目有点脑筋急转弯的意思
• 我们注意到，差偶数位的移动不需要耗费成本，只有差奇数位的移动需要耗费成本
• 那我们只需要分别统计奇数位的个数和偶数位的个数
• 因为奇数位的元素移动不需要耗费成本，同理偶数位的元素移动也不需要耗费成本。所以我们只需要取两者的最小值，把其移动到奇数位即可，这样就是我们需要耗费的最小成本
• 最后返回结果即可

七【题目提示】

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

八【时间频度】

• 时间复杂度：$O(n)$，其中$n$为数组大小
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

package GreedyAlgorithm;

/**
 * @Author: IronmanJay
 * @Description: 1217.玩筹码
 * @CreateTime: 2022-11-09  09:10
 */
public class p1217_PlayingChips {

    public static void main(String[] args) {
        int[] position = {1, 2, 3};
        int res = minCostToMoveChips(position);
        System.out.println("res = " + res);
    }

    public static int minCostToMoveChips(int[] position) {
        int even = 0;
        int odd = 0;
        for (int i = 0; i < position.length; i++) {
            if (position[i] % 2 == 0) {
                even++;
            } else {
                odd++;
            }
        }
        return Math.min(even, odd);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

2. C语言版

#include
#include

int minCostToMoveChips(int* position, int positionSize)
{
	int even = 0;
	int odd = 0;
	for (int i = 0; i < positionSize; i++)
	{
		if (position[i] % 2 == 0)
		{
			even++;
		}
		else
		{
			odd++;
		}
	}
	return fmin(even, odd);
}

/*主函数省略*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

十【提交结果】

1. Java语言版
   

2. C语言版