昨天的 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];
    }

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料