原題目網址: 1046. Last Stone Weight
題目描述
給你一堆石頭,每顆石頭都有正整數重量(weight)。每一輪都要挑兩顆最重的石頭把它們粉碎。假設這兩顆石頭分別具有重量 x
跟 y
且 x <= y
。
- 如果
x == y
,兩顆石頭都會被粉碎。 - 如果
x != y
,重量x
的石頭會被粉碎,重量y
的石頭則會有新的重量y - x
。
最後最多只會剩下一顆石頭,return 這顆石頭的重量。(如果沒有剩下任何石頭的話就 return 0)
解題思路
把 input array 建成 Max Heap 就可以輕鬆解決這一題。這一題比較容易忽略的就是 x <= y
這個條件,沒看清楚題目會以為 x
是最重的石頭, y
則是第二重的石頭。
以下為用 C 語言實作的程式碼:
// maximum heap
int maximum(int *stones) {
return stones[0];
}
int parent(int x) {
return x / 2;
}
int left_child(int x) {
return 2 * x;
}
int right_child(int x) {
return 2 * x + 1;
}
void heapify(int *heap, int heapSize, int root) {
int largest = root;
int left = left_child(root);
int right = right_child(root);
if (left <= heapSize) {
if (heap[largest - 1] < heap[left - 1]) {
largest = left;
}
}
if (right <= heapSize) {
if (heap[largest - 1] < heap[right - 1]) {
largest = right;
}
}
if (largest != root) {
int temp = heap[root - 1];
heap[root - 1] = heap[largest - 1];
heap[largest - 1] = temp;
heapify(heap, heapSize, largest);
}
}
void build_heap(int *heap, int heapSize) {
for (int i = parent(heapSize); i >= 1; i--) {
heapify(heap, heapSize, i);
}
}
void heap_insert(int *heap, int *heapSize, int key) {
*heapSize += 1;
heap[*heapSize - 1] = key;
int p = parent(*heapSize);
int i = *heapSize;
while (i > 1 && heap[p - 1] < key) {
heap[i - 1] = heap[p - 1];
i = p;
p = parent(p);
}
heap[i - 1] = key;
}
void remove_max(int *heap, int *heapSize) {
if (*heapSize == 0) {
return;
}
if (*heapSize == 1) {
*heapSize = 0;
return;
}
heap[0] = heap[*heapSize - 1];
*heapSize -= 1;
heapify(heap, *heapSize, 1);
}
int lastStoneWeight(int* stones, int stonesSize){
build_heap(stones, stonesSize);
int heapSize = stonesSize;
while (heapSize > 0) {
if (heapSize == 1) {
return maximum(stones);
}
int y = maximum(stones);
int x = stones[left_child(1) - 1];
int right = right_child(1);
if (right <= heapSize && stones[right - 1] > x) {
x = stones[right - 1];
}
if (x == y) {
remove_max(stones, &heapSize);
remove_max(stones, &heapSize);
} else {
remove_max(stones, &heapSize);
remove_max(stones, &heapSize);
heap_insert(stones, &heapSize, y - x);
}
}
return 0;
}