【Leetcode】1046. Last Stone Weight（第137周周赛）（优化）

超、凢脫俗 2022-01-30 12:17 141阅读 0赞

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose the two **heaviest** rocks and smash them together. Suppose the stones have weights `x` and `y` with `x <= y`. The result of this smash is:

*  If `x == y`, both stones are totally destroyed;
 *  If `x != y`, the stone of weight `x` is totally destroyed, and the stone of weight `y` has new weight `y-x`.

At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

**Example 1:**

Input: [2,7,4,1,8,1]
    Output: 1
    Explanation: 
    We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
    we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
    we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
    we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

**Note:**

1.  `1 <= stones.length <= 30`
2.  `1 <= stones[i] <= 1000`

题目大意：

给出一堆石头的重量，我们每次从这堆石头中取出最重的两个，将其按照以下规则进行处理：

1. x == y，两个石头同时消失。

2. x != y，生成一个新石头，y-x

求出最后剩下的石头大小。

解题思路：

以后看题多看Note，Leetcode很少会出思路很直的题。求出后每次排序肯定不行，既然我们看到石头的重量在1到1000之间。所以我们可以记录下每个重量下出现的次数，从后向前遍历数组，记录当前生成石头的大小，如果上一个没有完全抵消那么下一个下一次生成的石头可能会比当前的大或者小，如果小可以直接在本位置+1，但是如果是大则我们将新石头标记为新值，当前这堆个数-1，再次遍历这个位置。

class Solution {
    public:
        int lastStoneWeight(vector<int>& stones) {
            int nums[1100];
            memset(nums, 0, sizeof(nums));
            for(int i=0;i<stones.size();i++){
                nums[stones[i]]++;
            }
            int tmp=-1;
            for(int j=1000;j>=1;j--){
                if(nums[j]==0){
                    continue;
                }else{
                    if(nums[j]){
                        if(nums[j]%2==1){
                            if(tmp==-1){
                                nums[j]=0;
                                tmp=j;
                            }else{
                                if(tmp-j>=j){
                                    tmp = tmp-j;
                                    nums[j]--;
                                    j++;
                                }else{
                                    nums[j]=0;
                                    nums[tmp-j]++;
                                    tmp=-1;
                                }
                            }
                        }else{
                            if(tmp==-1){
                                nums[j]=0;
                            }else{
                                if(tmp-j>=j){
                                    tmp = tmp-j;
                                    nums[j]--;
                                    j++;
                                }else{
                                    nums[j]=0;
                                    nums[tmp-j]++;
                                    tmp=j;
                                }
                            }
                        }
                    }
                }
            }
            
            return tmp==-1?0:tmp;
            
        }
    };