Last Updated on 2021-12-06 by Clay
題目
We have n chips, where the position of the ith chip is position[i]. We need to move all the chips to the same position. In one step, we can change the position of the ith chip from position[i] to: - position[i] + 2 or position[i] - 2 with cost = 0. - position[i] + 1 or position[i] - 1 with cost = 1. Return the minimum cost needed to move all the chips to the same position.
題目的意思是，我們有 n 個籌碼，第 i 個籌碼位於 position[i] 的位置。現在，我們要試圖將籌碼全部放在同樣的位置堆疊起來，移動一步的消耗（cost）為 1，移動兩步的消耗為 0。試問：我們要如何在最短的消耗內將全部的籌碼放在同樣的位置？
解題思路
一開始我想的辦法是暴力法是將所有位置移動到 0 或 1...... 但後來轉念一想，其實只需要統計位置是奇數或是偶數就行了。因為我們每次移動兩步的消耗是 0，所以可以把奇數位置籌碼無需消耗地放在 1 的位置、偶數位置籌碼無需消耗地放在 0 位置；接著，就是計算哪邊籌碼比較少，用少的那邊消耗 1 移動一步去另外一邊。
| Time complexity | O(n) |
| Space complexity | O(1) |
C++ 範例程式碼
class Solution {
public:
int minCostToMoveChips(vector<int>& position) {
// Init
int odd = 0;
int even = 0;
// Move
for (int i=0; i<position.size(); ++i) {
if (position[i] % 2 == 0) {
++even;
}
else {
++odd;
}
}
return min(odd, even);
}
};Python 範例程式碼
class Solution:
def minCostToMoveChips(self, position: List[int]) -> int:
# Init
odd = 0
even = 0
# Move
for n in position:
if n % 2 == 0: even += 1
else: odd += 1
return min(odd, even)