1217. 玩筹码
大约 2 分钟
1217. 玩筹码
- 标签:贪心、数组、数学
- 难度:简单
题目大意
描述:给定一个数组 position
代表 n
个筹码的位置,其中 position[i]
代表第 i
个筹码的位置。现在需要把所有筹码移到同一个位置。在一步中,我们可以将第 i
个芯片的位置从 position[i]
改变为:
position[i] + 2
或position[i] - 2
,此时cost = 0
;position[i] + 1
或position[i] - 1
,此时cost = 1
。
即移动偶数位长度的代价为 0
,移动奇数位长度的代价为 1
。
要求:返回将所有筹码移动到同一位置上所需要的 最小代价 。
说明:
- 。
- 。
示例:
- 示例 1:
输入:position = [2,2,2,3,3]
输出:2
解释:我们可以把位置3的两个芯片移到位置 2。每一步的成本为 1。总成本 = 2。
解题思路
思路 1:贪心算法
题目中移动偶数位长度是不需要代价的,所以奇数位移动到奇数位不需要代价,偶数位移动到偶数位也不需要代价。
则我们可以想将所有偶数位都移动到下标为 0
的位置,奇数位都移动到下标为 1
的位置。
这样,所有的奇数位、偶数位上的人都到相同或相邻位置了。
我们只需要统计一下奇数位和偶数位的数字个数。将少的数移动到多的数上边就是最小代价。
则这道题就可以通过以下步骤求解:
- 遍历数组,统计数组中奇数个数和偶数个数。
- 返回奇数个数和偶数个数中较小的数即为答案。
思路 1:贪心算法代码
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)