題目: LeetCode - 1046. Last Stone Weight
題目說明
給一個陣列,每次找出最大及次大的值,若是兩者相同則消除,否則消除小的,而大的值改為兩者相減。
解題思路
參考解法
解法一:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| class Solution { public: pair<int, int> findMax(vector<int>& stones) { pair<int, int> max; max = {stones[0], 0}; for(int i = 1; i < stones.size(); ++i) if(stones[i] > max.first) max = {stones[i], i}; stones[max.second] = 0; return max; } int lastStoneWeight(vector<int>& stones) { pair<int, int> x, y; do { y = findMax(stones); x = findMax(stones); if(y != x) stones[y.second] = y.first - x.first; }while(x.first != 0); return y.first; } };
|
解法二:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public: int lastStoneWeight(vector<int>& stones) { int y, x; priority_queue<int> maxheap; for(auto& i : stones) maxheap.push(i); while(maxheap.size() > 1) { y = maxheap.top(); maxheap.pop(); x = maxheap.top(); maxheap.pop(); if(y != x) maxheap.push(y - x); } return maxheap.empty() ? 0 : maxheap.top(); } };
|