【LeetCode】玩筹码 Java 题解

作者：Albert

2022 年 7 月 09 日
本文字数：915 字
阅读完需：约 3 分钟

题目描述

有 n 个筹码。第 i 个筹码的位置是 position[i] 。

我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个筹码的位置从 position[i] 改变为:

position[i] + 2 或 position[i] - 2 ，此时 cost = 0position[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
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/minimum-cost-to-move-chips-to-the-same-position著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是筹码题目，以数组的形式展现。题目要求把所有的筹码移动到同一位置，移动的规则是每次移动 2 步，cost 是 0, 每次移动 1 步，cost 是 1。需要求出所有筹码移动到同一位置上所需要的最小代价。
我们分析一下示例 2 position = [2,2,2,3,3] 意味着位置 2 有 3 个筹码，位置 3 有 2 个筹码。把所有筹码移动到一个位置，移动两步代价为 0，那其实我就可以把所有“奇数位置”筹码移动到一个点 A（奇数位置），且不必花费任何代价；同理，所有“偶数位置”的筹码移动到点 B（偶数位置）也不需要任何代价。最终就是看 A,B 两点谁的筹码数多，把少的筹码移动到多的筹码的位置，每一个筹码的代价都是 1。
理解了这一层之后，代码就容易实现，具体实现代码如下，请参考。

通过代码

class Solution {    public int minCostToMoveChips(int[] position) {        int oddCnt = 0;        int evenCnt = 0;
        for (int i : position) {            if (i % 2 == 0) {                evenCnt++;            } else {                oddCnt++;            }        }
        return Math.min(oddCnt, evenCnt);    }}