昨天的 Tree 實在是燒掉我不少腦細胞,今天的 1046. Last Stone Weight 小小的療癒了一下,果然一次AC成就感滿滿。
今天的題目是給定一個陣列,每次挑出最重的兩個石頭,如果兩個一樣重就都碎掉;不然就碎掉小的石頭,把大石頭和小石頭的差放回去。重複這個過程直到回傳最後一個石頭的重量(如果沒石頭了就回傳 0 )
Input: [2,7,4,1,8,1] Output: 1 Explanation: We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then, we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then, we combine 2 and 1 to get 1 so the array converts to [1,1,1] then, we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.
秉持著一個 vector 打天下的理念,實作如下。
小小紀錄用到的API:max_element,用法就是傳入 begin/end,回傳最大值的 Iterator 給你。
int lastStoneWeight(vector<int>& stones) {
while(stones.size() > 1){
int first, second;
vector<int>::iterator it;
it = max_element(stones.begin(), stones.end());
first = *it;
stones.erase(it);
it = max_element(stones.begin(), stones.end());
second = *it;
stones.erase(it);
if(first - second)
stones.push_back(first - second);
}
if(stones.empty())
return 0;
else
return stones[0];
}