『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

题解

【玩筹码】枚举&找规律

枚举

简单的想法是枚举所有可能的最终位置，分别统计移动所需代价，容易证明，最终可能的位置，必定是已经有筹码的位置，所以只需枚举所有筹码的位置作为最终位置即可，对于简单题这样的简单想法是可行的。

# Code language: Python
class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:
        return min(sum((p1 - p2) % 2 == 1 for p2 in position) for p1 in position)

// Code language: Java
class Solution {
    public int minCostToMoveChips(int[] position) {
        int n = position.length, ans = n;
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            for (int j = 0; j < n; ++j) {
                if (Math.abs(position[i] - position[j]) % 2 == 1) ++cnt;
            }
            ans = Math.min(ans, cnt);
        }
        return ans;
    }
}

// Code language: C++
class Solution {
public:
    int minCostToMoveChips(vector<int>& position) {
        int n = position.size(), ans = 200;
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            for (int j = 0; j < n; ++j) {
                if (abs(position[i] - position[j]) % 2 == 1) ++cnt;
            }
            ans = min(ans, cnt);
        }
        return ans;
    }
};

/** Code language: JavaScript
 * @param {number[]} position
 * @return {number}
 */
var minCostToMoveChips = function(position) {
    let ans = 200, n = position.length;
    for (let i = 0; i < n; ++i) {
        let cnt = 0;
        for (let j = 0; j < n; ++j) {
            if (((position[i] % 2 + position[j] % 2)) % 2 == 1) ++cnt;
        }
        if (cnt < ans) ans = cnt;
    }
    return ans;
};

时间复杂度: \(O(n^2)\)
空间复杂度: \(O(1)\)

找规律

容易发现，移动两个位置的时候没有代价，而移动一个位置的时候代价为 1, 简而言之，从奇数位置移动到偶数为和从偶数位置移动到奇数位置的代价为 1, 否则代价为 0.

那么所有筹码可以分为两类，在奇数位置和在偶数位置的，同类间移动没有代价，而将奇数位置移动到偶数位置的代价与在奇数位置的筹码数量成正比，偶数位置同理，所以只需统计奇数和偶数位置的筹码数量进行比较即可得到最小移动代价。

# Code language: Python
class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:
        return min(sum(p % 2 == i for p in position) for i in (0, 1))

// Code language: Java
class Solution {
    public int minCostToMoveChips(int[] position) {
        int a = 0, b = 0;
        for (int p: position) {
            if (p % 2 == 0) ++a;
            else ++b;
        }
        return Math.min(a, b);
    }
}

// Code language: C++
class Solution {
public:
    int minCostToMoveChips(vector<int>& position) {
        int a = 0, b = 0;
        for (int p: position) {
            if (p % 2 == 0) ++a;
            else ++b;
        }
        return min(a, b);
    }
};

/** Code language: JavaScript
 * @param {number[]} position
 * @return {number}
 */
var minCostToMoveChips = function(position) {
    var a = 0, b = 0;
    for (let i = 0, n = position.length; i < n; ++i) {
        if (position[i] % 2 == 0) ++a;
        else ++b;
    }
    return a > b ? b : a;
};

// Code language: C
int minCostToMoveChips(int* position, int positionSize){
    int a = 0, b = 0;
    for (int i = 0; i < positionSize; ++i) {
        if (position[i] % 2 == 0) ++a;
        else ++b;
    }
    return a > b ? b : a;
}

时间复杂度: \(O(n)\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』1217 玩筹码

题目

标签

题解

枚举

找规律