How to Use Priority Queue in Java or C++ to Compute Last Stone W
- Time:2020-09-10 12:45:51
- Class:Weblog
- Read:32
We have a collection of stones, each stone has a positive integer weight. Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.
At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)Example 1:
Input: [2,7,4,1,8,1]
Output: 1Explanation:
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.Note:
1 <= stones.length <= 30
1 <= stones[i] <= 1000Hints:
Simulate the process. We can do it with a heap, or by sorting some list of stones every time we take a turn.
What is a Priority Queue?
We know a Queue is a First In First Out data structure. The Priority Queue is a special queue that the max or min value of the queue is popped out (dequeue). Therefore, the Priority Queue is usually based on a max/min heap.
Priority Queue in C++ Example
Be default, the priority queue in C++ pops out the max element. Thus the above problem can be solved by simulating the process using a priority queue. Popping out two elements which are the biggest in the array, and push the difference (if it is not zero) back to the priority queue.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution { public: int lastStoneWeight(vector<int>& stones) { if (stones.empty()) return 0; priority_queue<int> pq; for (const auto &n: stones) { pq.push(n); } while (pq.size() > 1) { int s1 = pq.top(); pq.pop(); int s2 = pq.top(); pq.pop(); if (s1 != s2) pq.push(s1 - s2); } return pq.empty() ? 0 : pq.top(); } }; |
class Solution { public: int lastStoneWeight(vector<int>& stones) { if (stones.empty()) return 0; priority_queue<int> pq; for (const auto &n: stones) { pq.push(n); } while (pq.size() > 1) { int s1 = pq.top(); pq.pop(); int s2 = pq.top(); pq.pop(); if (s1 != s2) pq.push(s1 - s2); } return pq.empty() ? 0 : pq.top(); } };
We can declare in C++ a min priority queue, using the following syntax:
1 | priority_queue<int, vector<int>, std::greater<int>> pq; |
priority_queue<int, vector<int>, std::greater<int>> pq;
Priority Queue in Java Example
In Java, we can instantise the abstract Queue type using Priority Queue. By default, the Priority Queue in Java pops out the min element, and thus, we would need to provide the custom comparator:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution { public int lastStoneWeight(int[] stones) { Queue<Integer> pq = new PriorityQueue<Integer>(stones.length, (a, b) -> b - a); for (int x: stones) { pq.offer(x); } while (pq.size() > 1) { int a = pq.peek(); pq.poll(); int b = pq.peek(); pq.poll(); if (a != b) { pq.offer(a - b); } } return pq.isEmpty() ? 0 : pq.peek(); } } |
class Solution { public int lastStoneWeight(int[] stones) { Queue<Integer> pq = new PriorityQueue<Integer>(stones.length, (a, b) -> b - a); for (int x: stones) { pq.offer(x); } while (pq.size() > 1) { int a = pq.peek(); pq.poll(); int b = pq.peek(); pq.poll(); if (a != b) { pq.offer(a - b); } } return pq.isEmpty() ? 0 : pq.peek(); } }
The Priority Queue overloaded constructor takes first parameter as the initial capacity.
–EOF (The Ultimate Computing & Technology Blog) —
Recommend:How You Can Earn More With Bitcoins On Your Blog
Explore New Ways of Online Publishing With Mobirise
Is Working from Home as a Blogger a Good Fit?
Why You Should Handwrite Your Blog Post First
The Good Old Days – 5 Ways To Use Nostalgia Marketing In Ecommer
7 Top Tools to Build Your Blog and Brand Like A Pro
Top Reasons to Start a Blog During Lockdown
3 Tips for Handling a National Crisis – From a Blogging Perspect
6 Best WordPress Plugins for eLearning & Tutorial Websites
A Successful Marketing Chain Examined
- Comment list
-
- Comment add