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 \le chips.length \le 100$。
- $1 \le chips[i] \le 10^9$。
示例:
- 示例 1:
|
|
解题思路 #
思路 1:贪心算法 #
题目中移动偶数位长度是不需要代价的,所以奇数位移动到奇数位不需要代价,偶数位移动到偶数位也不需要代价。
则我们可以想将所有偶数位都移动到下标为 0
的位置,奇数位都移动到下标为 1
的位置。
这样,所有的奇数位、偶数位上的人都到相同或相邻位置了。
我们只需要统计一下奇数位和偶数位的数字个数。将少的数移动到多的数上边就是最小代价。
则这道题就可以通过以下步骤求解:
- 遍历数组,统计数组中奇数个数和偶数个数。
- 返回奇数个数和偶数个数中较小的数即为答案。
思路 1:贪心算法代码 #
|
|