1217. 玩筹码

1217. 玩筹码 #

  • 标签:贪心、数组、数学
  • 难度:简单

题目大意 #

描述:给定一个数组 position 代表 n 个筹码的位置,其中 position[i] 代表第 i 个筹码的位置。现在需要把所有筹码移到同一个位置。在一步中,我们可以将第 i 个芯片的位置从 position[i] 改变为:

  • position[i] + 2position[i] - 2,此时 cost = 0
  • position[i] + 1position[i] - 1,此时 cost = 1

即移动偶数位长度的代价为 0,移动奇数位长度的代价为 1

要求:返回将所有筹码移动到同一位置上所需要的 最小代价 。

说明

  • $1 \le chips.length \le 100$。
  • $1 \le chips[i] \le 10^9$。

示例

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

解题思路 #

思路 1:贪心算法 #

题目中移动偶数位长度是不需要代价的,所以奇数位移动到奇数位不需要代价,偶数位移动到偶数位也不需要代价。

则我们可以想将所有偶数位都移动到下标为 0 的位置,奇数位都移动到下标为 1 的位置。

这样,所有的奇数位、偶数位上的人都到相同或相邻位置了。

我们只需要统计一下奇数位和偶数位的数字个数。将少的数移动到多的数上边就是最小代价。

则这道题就可以通过以下步骤求解:

  • 遍历数组,统计数组中奇数个数和偶数个数。
  • 返回奇数个数和偶数个数中较小的数即为答案。

思路 1:贪心算法代码 #

1
2
3
4
5
6
7
8
9
class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:
        odd, even = 0, 0
        for p in position:
            if p & 1:
                odd += 1
            else:
                even += 1
        return min(odd, even)
本站总访问量  次  |  您是本站第  位访问者