數(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。
最開(kāi)始的時(shí)候,同一位置上也可能放著兩個(gè)或者更多的籌碼。
返回將所有籌碼移動(dòng)到同一位置(任意位置)上所需要的最小代價(jià)。
示例 1:
輸入:chips = [1,2,3]
輸出:1
解釋:第二個(gè)籌碼移動(dòng)到位置三的代價(jià)是 1,第一個(gè)籌碼移動(dòng)到位置三的代價(jià)是 0,總代價(jià)為
示例 2:
輸入:chips = [2,2,2,3,3]
輸出:2
解釋:第四和第五個(gè)籌碼移動(dòng)到位置二的代價(jià)都是 1,所以最小總代價(jià)為 2
解析思路:首先要思考這個(gè)最小代價(jià)怎么出現(xiàn)?一定是通過(guò)一些操作(并且這些操作的代價(jià)最小)使得最后的籌碼間隔奇數(shù)位置堆疊(這種做法的移動(dòng)代價(jià)是0)。那么這就必然會(huì)出現(xiàn)兩種結(jié)果:一種是最后所有籌碼出現(xiàn)在奇數(shù)位置,二是最后所有籌碼出現(xiàn)在偶數(shù)位置。
那么我們只需要統(tǒng)計(jì)一遍chips,然后判斷奇數(shù)位置籌碼的和和偶數(shù)位置籌碼的和哪個(gè)小即可。
答案: 這邊有一個(gè)計(jì)算奇偶數(shù)的技巧,if x&1=1 ,x是奇數(shù)