題目:
數(shù)軸上放置了一些籌碼,每個(gè)籌碼的位置存在數(shù)組 chips 當(dāng)中。
你可以對(duì) 任何籌碼 執(zhí)行下面兩種操作之一(不限操作次數(shù),0 次也可以):
將第 i 個(gè)籌碼向左或者右移動(dòng) 2 個(gè)單位,代價(jià)為 0。
將第 i 個(gè)籌碼向左或者右移動(dòng) 1 個(gè)單位,代價(jià)為 1。
最開始的時(shí)候,同一位置上也可能放著兩個(gè)或者更多的籌碼。
返回將所有籌碼移動(dòng)到同一位置(任意位置)上所需要的最小代價(jià)。
示例 1:
輸入:chips = [1,2,3]
輸出:1
解釋:第二個(gè)籌碼移動(dòng)到位置三的代價(jià)是 1,第一個(gè)籌碼移動(dòng)到位置三的代價(jià)是 0,總代價(jià)為 1。
示例 2:
輸入:chips = [2,2,2,3,3]
輸出:2
解釋:第四和第五個(gè)籌碼移動(dòng)到位置二的代價(jià)都是 1,所以最小總代價(jià)為 2。
思路一:
題意讀了半天沒(méi)讀懂,參照題友寫的題意。
先理解題意:有的人可能理解錯(cuò)題意了,這里的chips數(shù)組里存放的是第i個(gè)籌碼存放的位置,不是第i個(gè)位置存放了多少個(gè)籌碼,這個(gè)概念
搞清楚了就簡(jiǎn)單多了。比如chips = [2,2,2,3,3]]表示第1個(gè)籌碼放第2個(gè)位置,第2個(gè)籌碼放第2個(gè)位置,第3個(gè)籌碼放第2個(gè)位置,第4個(gè)籌碼
放第3個(gè)位置,第5個(gè)籌碼放第3個(gè)位置,那么這就表示,第2個(gè)位置上有3個(gè)籌碼,第3個(gè)位置上有2個(gè)籌碼,其它位置上沒(méi)有籌碼,可以把
第3個(gè)位置上的2個(gè)籌碼移動(dòng)到第2個(gè)位置上,所以代價(jià)是2.
再理解思路:因?yàn)橐苿?dòng)2個(gè)位置不需要代價(jià),那么奇數(shù)位置移到奇數(shù)位置不用代價(jià),偶數(shù)位置移到偶數(shù)位置不用代價(jià),那就分別統(tǒng)計(jì)奇數(shù)
位置和偶數(shù)位置的個(gè)數(shù),相當(dāng)于把所有奇數(shù)放一起,所有偶數(shù)的放一起,然后比較奇數(shù)的少還是偶數(shù)的少,將少的個(gè)數(shù)移到多的個(gè)數(shù)位置
上去就可以了。
鏈接:https://leetcode-cn.com/problems/minimum-cost-to-move-chips-to-the-same-position/solution/xian-li-jie-ti-yi-zai-li-jie-dai-ma-si-lu-by-athen/
代碼如下:
public int minCostToMoveChips(int[] position) {
int eventCount = 0;
int addCount = 0;
for (int p : position) {
if (p % 2 == 0) {
eventCount++;
} else {
addCount++;
}
}
return Math.min(eventCount, addCount);
}
-------------------------------小白學(xué)算法