CTF of Z2BNS
0%

最后一块石头的重量

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 990 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

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

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

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例：

1
2
3
4
5
6
7
输入：[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
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

根据题目描述进行模拟，遍历n-1次，每次遍历对石头堆按重量从大到小排序（石头堆石头最多30块），取前两块石头相减。

c++代码：(执行用时4ms，击败44.52%，内存消耗6M，击败95.96%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    static int cmp(int a,int b){ 
        return a>b;
    }
    int lastStoneWeight(vector<int>& stones) {
        int n=stones.size();
        for(int i=0;i<n-1;i++){
            sort(stones.begin(),stones.end(),cmp);
            stones[0]=stones[0]-stones[1];
            stones[1]=0;
        }
        return stones[0];        
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：最大堆
将所有石头的重量放入最大堆中。每次依次从队列中取出最重的两块石头 $a$ 和 $b$，必有$a≥b$。如果 $a>b$，则将新石头 放回到最大堆中；如果 $a=b$，两块石头完全被粉碎，因此不会产生新的石头。重复上述操作，直到剩下的石头少于 2 块。

最终可能剩下 1 块石头，该石头的重量即为最大堆中剩下的元素，返回该元素；也可能没有石头剩下，此时最大堆为空，返回 0。

c++代码：(执行用时0ms，击败100.00%，内存消耗6M，击败95.00%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> q;
        for (int s: stones) {
            q.push(s);
        }

        while (q.size() > 1) {
            int a = q.top();
            q.pop();
            int b = q.top();
            q.pop();
            if (a > b) {
                q.push(a - b);
            }
        }
        return q.empty() ? 0 : q.top();
    }
};

复杂度分析

  • 时间复杂度：$O(nlogn)$，其中 $n$ 是石头数量。每次从队列中取出元素需要花费 $O(logn)$ 的时间，最多共需要粉碎 $n−1$ 次石头。

  • 空间复杂度：$O(n)$。

⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

一个多月没学习了，忘了好多，没想起来使用queue容器，好在石头数量不大使用多次sort排序也可以满足题目要求。

------------- THE END! THANKS! -------------