[LeetCode 解題筆記] Last Stone Weight

原題目網址： 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;
}