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
思路
- 读题
移动奇数次位置代价为1, 移动偶数次位置代价为0, 寻找一个位置, 距离其他位置的距离尽量都是偶数
思路一 遍历所有位置, 选取最小代价
使用HashMap<Integer, Integer>存储位置和该位置上的元素个数
循环变量, 每个位置与其他位置的距离, 加上其他位置的元素个数, 从而计算出代价
选出最小代价输出
- 最坏时间复杂度 O(n^2) n=100 (chips.length <= 100) 位置个数
思路二 取出奇数位置和偶数位置的元素个数最小
因为不需要将结果位置输出, 并且偶数次移动是没有代价的
所有同是奇数或同是偶数, 它们之间移动是没有代价的, 而对应的其他非奇数或非偶数的元素, 就是需要付出的代价
选出需要付出最小的代价, 即奇或偶数位置上元素个数最小的
思路三 可以不使用HashMap 直接暴力枚举
基本思路同思路一, 但不进行记录位置与位置上元素个数, 直接循环暴力枚举(因为数据量不大 chips.length <= 100)
代码实现
思路一
class Solution {
public int minCostToMoveChips(int[] chips) {
// maps 存储位置和该位置上元素个数
Map<Integer, Integer> maps = new HashMap<>(chips.length);
for (int i : chips) {
if (!maps.containsKey(i)) {
maps.put(i, 0);
}
maps.put(i, maps.get(i) + 1);
}
//System.out.println("maps: " + maps);
// keys 存储所有位置信息
Set<Integer> keys = maps.keySet();
// cost 所有元素移动到当前位置的代价
// step 其他位置到当前位置的距离(绝对值)
// minCost 所有位置中的最小代价
int cost, step, minCost = Integer.MAX_VALUE;
for (Integer cur : keys) {
cost = 0;
step = 0;
for (Integer next : keys) {
if (!cur.equals(next)) {
// 将next位置上的筹码移动到cur位置上
step = Math.abs(next - cur);
// 距离为偶数 则代价为0 否则代价为1
cost += (step % 2 == 1 ? 1 : 0) * maps.get(next);
//System.out.println(String.format("%d(%d) --> %d, step:%d, cost:%d",
// next, maps.get(next), cur, step, cost));
}
}
// 比较当前代价和所存储的最小代价 选出全局最小代价
minCost = minCost > cost ? cost : minCost;
}
return minCost;
}
}
思路二
class Solution {
public int minCostToMoveChips(int[] chips) {
// cnt 存放奇数和偶数位置上元素个数
int[] cnt = {0, 0};
for (int i : chips) {
// 通过i&1 为0则为偶数 为1则为奇数
cnt[i&1]++;
}
return Math.min(cnt[0], cnt[1]);
}
}
思路三
class Solution {
public int minCostToMoveChips(int[] chips) {
int res = Integer.MAX_VALUE;
int n = chips.length;
for (int i = 0; i < n; i++) {
int cur = 0;
for (int j = 0; j < n; j++) {
// 距离为奇数则加一
cur += Math.abs(chips[j] - chips[i]) % 2;
}
res = res > cur ? cur : res;
}
return res;
}
}
参考资源
第 157 场周赛 全球排名
【算法实况】体验使用 iPadOS 打算法竞赛 - 力扣周赛 - LeetCode Weekly 157
力扣周赛录屏-leetcode-weekly-contest-157