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:\t" + 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