1046/1049-最后一块石头的重量

LeetCode 1046. 最后一块石头的重量

LeetCode-1046

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 
先选出 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]，这就是最后剩下那块石头的重量。

method: 大根堆

因为每个都要取最大的两个数，所以用大根堆从大到小排序

int lastStoneWeight(vector<int>& stones) {
    priority_queue<int, vector<int>, less<int>> q;
    for (auto n : stones) q.push(n);
    while (q.size() > 1) {  // 至少两个数
        int x1 = q.top();
        q.pop();
        int x2 = q.top();
        q.pop();
        if (x1 > x2) q.push(x1 - x2);
    }
    return q.empty() ? 0 : q.top(); // 非空返回堆首
}

---

LeetCode 1049. 最后一块石头的重量 II

LeetCode-1049

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

Example 1:

输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

method: 01背包

把所有元素分成大小最接近的两堆，类似于416-分割等和子集

用一个sum/2的背包去装，最大能装dp[sum/2]，肯定小于等于另一堆sum - dp[sum/2]，再做差就行

int lastStoneWeightII(vector<int>& nums) {
    int sum = 0;
    for (auto n : nums) sum += n;
    int target = sum / 2;
    vector<int> dp(target + 1);
    for (int i = 0; i < nums.size(); i++) {
        for (int j = target; j >= nums[i]; j--) {
            dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    return (sum - dp[target]) - dp[target];
}