LeetCode.1046-最後的石頭重量(Last Stone Weight)

這是小川的第388次更新，第418篇原創

01 看題和準備

今天介紹的是LeetCode算法題中Easy級别的第250題（順位題号是1046）。有一個石頭集合，每個石頭都有一個正整數重量值。

每次，我們選擇兩塊最重的岩石并将它們粉碎在一起。假設石頭的重量為x和y，x <= y。粉碎的結果是：

• 如果x == y，兩塊石頭都被完全粉碎;
• 如果x != y，重量為x的石頭被完全粉碎，重量為y的石頭具有新的重量y-x。

最後，剩下最多1塊石頭。傳回這塊石頭的重量（如果沒有留下石頭，則傳回0）。

例如：

輸入：[2,7,4,1,8,1]

輸出：1

說明：

我們将7和8結合起來得到1，是以數組轉換為[2,4,1,1,1]，

然後我們将2和4結合起來得到2，是以數組轉換為[2,1,1,1]，

然後我們将2和1結合起來得到1，是以數組轉換為[1,1,1]，

然後我們将1和1組合起來得到0，是以數組轉換為[1]，那就是最後一塊石頭的重量值。

注意：

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

02 第一種解法

根據題目的意思，我們需要幹兩件事情，第一，每次找到數組中最大的兩個數進行值替換，比較大小，相等就全幹掉，不相等就把較大的值替換為兩者的內插補點，再把較小的幹掉；第二，重複第一步，直到所有元素都被幹掉或者最後隻剩下一個元素。

思路：先将數組排序，統計其中值為0的元素個數，因為

stones[i]

的範圍在[1,1000]，循環進行值替換（替換為0），直到最後數組中值為0的元素個數等于

stones.length

或者

stones.length-1

，才結束循環。如果數組最後一個元素不等于0，就傳回此元素的值，反之傳回0。

public int lastStoneWeight(int[] stones) {
    int n = stones.length;
    while (!(checkStones(stones) == n || checkStones(stones) == n-1)) {
        if (stones[n-2] == stones[n-1]) {
            stones[n-2] = 0;
            stones[n-1] = 0;
        } else {
            stones[n-1] -= stones[n-2];
            stones[n-2] = 0;
        }
    }
    // 全是0，或者隻有最後一個元素不為0
    return stones[n-1] == 0 ? 0 : stones[n-1];
}

/**
 * 統計數組stones中值為0的元素個數
 * @param stones
 * @return
 */
public int checkStones(int[] stones) {
    Arrays.sort(stones);
    int count = 0, n = stones.length;
    for (int i=0; i<n; i++) {
        if (stones[i] == 0) {
            count++;
        }
    }
    return count;
}
           

03 第二種解法

我們可以将第一種解法再簡化下，不去計數的個數，依舊按照題目的規則進行替換0操作，效果一樣。

public int lastStoneWeight2(int[] stones) {
    int n = stones.length;
    for (int i=0; i<n-1; i++) {
        Arrays.sort(stones);
        if (stones[n-2] == stones[n-1]) {
            stones[n-2] = 0;
            stones[n-1] = 0;
        } else {
            stones[n-1] -= stones[n-2];
            stones[n-2] = 0;
        }
    }
    // 全是0，或者隻有最後一個元素不為0
    return stones[n-1] == 0 ? 0 : stones[n-1];
}
           

04 第三種解法

在第一種解法和第二種解法中，每次循環都需要重新排序數組，能不能将此步驟省掉？

答案是可以的，利用優先隊列來實作。

在初始化優先隊列時，選擇有

Comparator

作為參數的構造方法，選擇其

reverseOrder

方法，倒序排序（從大到小），将數組中的元素入隊列，然後開始循環處理。因為優先隊列會自動排序，最大值永遠在隊首，第二大的值次之，将兩者取出相減，如果兩者之差大于0，就将內插補點入隊列。最後判斷隊列是否為空，為空就傳回0，不為空就傳回隊首的元素值。

public int lastStoneWeight3(int[] stones) {
    PriorityQueue<Integer> pq = new 
            PriorityQueue<>(Comparator.reverseOrder());
    for (int stone : stones) {
        pq.offer(stone);
    }
    while (pq.size() > 1) {
        int num = pq.poll() - pq.poll();
        if (num > 0) {
            pq.offer(num);
        }
    }
    return pq.isEmpty() ? 0 : pq.peek();
}
           

05 小結

算法專題目前已連續日更超過七個月，算法題文章256+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！