LeetCode 75 Level 1 - Day 15 Heap

1046. Last Stone Weight

• 題目連結
• 難易度：Easy

題目敘述

You are given an array of integers stones where stones[i] is the weight of the stone.
We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are destroyed, and
• If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
  At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

預設函數

int lastStoneWeight(int* stones, int stonesSize){

}

題目限制

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

解題過程及程式碼

本題輸入給一個陣列，內容是1~1000的整數表示你手上每顆石頭的重量，現在請你找出最重的2顆石頭來互敲，依這2顆石頭的重量有不同的結果：

• 若2顆石頭重量相同，則2個石頭都消失。
• 若2顆石頭重量不同，則最重和次重的石頭互敲後，最重石頭的重量會變成 (最重重量 - 次重重量)，次重的那顆則會消失。
• 一直進行直到剩下1顆石頭為止，請回傳剩下那顆石頭的重量，若最後敲到沒有石頭了則回傳0。

想法就是找出陣列中最大的數再找出陣列次大的數：

• 如果2個數相等則石頭數量少2。
• 如果不相等則石頭數量少1，最大數 = 最大數 - 次大數。
• 重複這個過程直到石頭數量剩最後一個或沒剩下。

程式碼上傳

int lastStoneWeight(int* stones, int stonesSize){
    int max, max_index, submax, submax_index;
    int i;
    int stones_num = stonesSize;

    if (stonesSize == 1) {
        return stones[0];
    }

    while (stones_num > 1) {
        /* 找出最大的元素 */
        max_index = findMax(stones, stonesSize);
        max = stones[max_index];
        stones[max_index] = 0;

        /* 找出次大的元素 */
        submax_index = findMax(stones, stonesSize);
        submax = stones[submax_index];
        stones[submax_index] = 0;

        /* 互敲後2顆都消失 */
        if (max == submax) {
            stones_num -= 2;
        /* 互敲後次重的消失，最重的變小 */
        } else {
            stones[max_index] = abs(max - submax);
            stones_num -= 1;
        }
    }

    for (i=0; i<stonesSize; i++) {
        if (stones[i] != 0) {
            return stones[i];
        }
    }
    return 0;
}

int findMax(int *lst, int num) {
    int max = 0;
    int max_i = 0;
    for (int i=0; i<num; i++) {
        if (lst[i] >= max) {
            max = lst[i];
            max_i = i;
        }
    }
    return max_i;
}

題目延伸

本題可以透過將輸入陣列調整為資料結構Heap來加速找最大值和次大值的計算，像今天的方法每次都用for迴圈從頭開始找最大值也是相當沒效率，相關Heap的作法會在明天那題來詳細說明。

終於到倒數第二篇啦，感謝大家看到這裡。