leetcode 1049 最后一块石头的重量II

秒速五厘米 2022-08-28 05:44 191阅读 0赞

## 前言 ##

题目：[1049. 最后一块石头的重量 II][1049. _ II]

参考题解：[最后一块石头的重量II-代码随想录][II-]

## 提交代码 ##

### 贪心-错误 ###

我想到的第一个方法是贪心。

贪心策略：每次取最大的两个石头互相粉碎。

我写完之后，测试用例无法通过。说明贪心策略存在问题。

经测试，存在错误。反例：\[31,26,33,21,40\]—》5？？？

下面是错误思路的代码。

#include <vector>
    #include <set>
    #include <iostream>
    
    using namespace std;
    
    class Solution {
    public:
        int lastStoneWeightII(vector<int>& stones) {
            // 核心思路：贪心。每次取最大的两个石头互相粉碎。
            // 经测试，存在错误。反例：[31,26,33,21,40]---》5？？？
    
            // 将石头从大大小插入multiset
            multiset<int,greater<int>> stones_set;
            for(int i=0; i<stones.size(); i++)
                stones_set.insert(stones[i]);
            
    
            while(stones_set.size()!=0 && stones_set.size()!=1){
                auto it = stones_set.begin();
                int stone1 = *(it);
                stones_set.erase(it);
                cout<<"stone choice: "<<stone1<<"       ";
                it = stones_set.begin();
                int stone2 = *(it);
                stones_set.erase(it);
                cout<<"stone choice: "<<stone2<<"       ";
    
                if(stone1-stone2 != 0){
                    stones_set.insert(stone1 - stone2);
                    cout<<"stone push: "<<stone1-stone2<<"       ";
                }
                cout<<endl;
            }   
    
            if(stones_set.size() == 0)
                return 0;
            return *stones_set.begin();    
        }
    };
    
    int main(void){
        vector<int> stones = {31,26,33,21,40};
        Solution s;
        cout<<s.lastStoneWeightII(stones);
    }

### 动态规划-正确 ###

和[leetcode 416 分割等和子集][leetcode 416]相似。先把石头分成尽量相等的两堆，然后互相粉碎。

代码如下。

#include <vector>
    #include <unordered_set>
    #include <stack>
    #include <iostream>
    
    using namespace std;
    
    class Solution {
    public:
        int lastStoneWeightII(vector<int>& stones) {
            // 核心思想：将石头尽量分成对等的两份；然后，互相消耗
    
            int sum = 0;
            for(int stone : stones)
                sum += stone;
            int bag_weight = sum/2;
            vector<vector<int>> dp(stones.size(),vector<int>(bag_weight+1,0)); 
            // 第一列初始化：当背包空间为0，可以放入的值为0
            // 第一行初始化：因为当无法放入时，需要继承上一行的值，所以需要初始化第一行
            for(int i=stones[0]; i<=bag_weight; i++)
                dp[0][i] = stones[0];
            
            // 尽量把背包装满 == 尽量将石头分为相等的两半
            for(int i=1; i<stones.size(); i++){ // 遍历物品
                for(int j=1; j<=bag_weight; j++){ // 遍历背包
                    if(stones[i]>j) // 无法放入
                        dp[i][j] = dp[i-1][j];
                    else
                        dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]]+stones[i]); // 可以放入，使用max判断是否放入   
                }
            }
    
            // for(auto v : dp){
            //     for(auto i : v)
            //         cout<<i<<" ";
            //     cout<<endl;
            // }
    
            // 统计放入背包中的是哪些时候 == 挑出一半重量的石头
            // 方法：再一件件取出物品
            unordered_set<int> half;
            int i=stones.size()-1;
            int j=bag_weight;
            while(i>=0 && j>=0 && dp[i][j]!=0){
                if(i>=1 && (dp[i][j] == dp[i-1][j])) // i物品并不在背包里面
                    i = i-1;
                else{ // 取出物品
                    half.insert(i);
                    j = j-stones[i];
                    i = i-1;
                }
            }
    
            // 另一半石头的下标
            unordered_set<int> other_half;
            for(i=0; i<stones.size(); i++)
                if(!half.count(i))
                    other_half.insert(i);
            
    
            // 将两堆石头分别放入两个栈中
            stack<int> s1;
            stack<int> s2;
            unordered_set<int>::iterator it;
            for(it=half.begin(); it!=half.end(); it++)
                s1.push(stones[*it]);
            for(it=other_half.begin(); it!=other_half.end(); it++)
                s2.push(stones[*it]);
            
            // 两堆石头互相消耗
            while(!s1.empty() && !s2.empty()){
                int stone1 = s1.top();
                s1.pop();
                int stone2 = s2.top();
                s2.pop();
                if(stone1 == stone2)
                    continue;
                else if(stone1 > stone2)
                    s1.push(stone1 - stone2);
                else
                    s2.push(stone2 - stone1);
            }
    
            // 统计剩余石头
            int result = 0;
            if(s1.empty() && s2.empty())
                ;
            else if(!s1.empty() && s2.empty()){
                while(!s1.empty()){
                    result += s1.top();
                    s1.pop();
                }
            }else{
               while(!s2.empty()){
                   result += s2.top();
                   s2.pop();
               }
            }
            
            return result;
        }
    };
    
    int main(void){
        vector<int> stones = {2,7,4,1,8,1};
        Solution s;
        cout<<s.lastStoneWeightII(stones);
    }

顺利通过之后，我看了下参考题解。想把自己头给打掉了。题目要求给出摩擦剩余的石头，仅此而已。

所以，两边石头的重量直接相减即可。完全不需要统计如何将两边的石头分成两堆。淦。

下面是参考题解的代码。

class Solution {
    public:
        int lastStoneWeightII(vector<int>& stones) {
            vector<int> dp(15001, 0);
            int sum = 0;
            for (int i = 0; i < stones.size(); i++) sum += stones[i];
            int target = sum / 2;
            for (int i = 0; i < stones.size(); i++) { // 遍历物品
                for (int j = target; j >= stones[i]; j--) { // 遍历背包
                    dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
                }
            }
            return sum - dp[target] - dp[target];
        }
    };

[1049. _ II]: https://leetcode-cn.com/problems/last-stone-weight-ii/
[II-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.md
[leetcode 416]: https://blog.csdn.net/sinat_38816924/article/details/120815730