1046 最后一块石头的重量(模拟、大根堆)

1. 问题描述:

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

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

最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 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. 1 <= stones.length <= 30
  2. 1 <= stones[i] <= 1000

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/last-stone-weight

2. 思路分析:

① 分析题目最容易想到的是模拟的办法,根据题目的描述来模拟整个过程,一开始的时候先对stones数组进行排序,可以使用python中的sort()函数对其排序,然后遍历stones数组遍历的时候分为两种情况处理,第一种情况是数组中最大的两个元素相等,那么这个时候弹出列表中最大的两个元素即可,第二种情况是当最大的两个元素不等的时候那么需要将较小的元素修改为两个元素的差值,并且弹出列表中最大的那个元素然后需要重新排序,下一次执行相同的操作,主要还是模拟整个过程

② 除了①中的方法之外,还可以使用大根堆的方法进行处理,因为是python语言,所以可以使用heapq模块中的heapify方法创建大根堆(默认创建的是小根堆但是我们可以在为列表的元素添加一个负号相当于创建的是大根堆只是其中的处理细节是不一样的),heapq模块中的heapify方法可以将一个列表初始化为一个小根堆,而且python存储元素是非常方便的,所以调用这个方法可以轻松地将列表转换为一个小根堆,然后我们使用heappop方法弹出堆顶的两个元素,因为在初始化列表的时候添加了负号,所以弹出的是相当于是大根堆中两个较大的元素,然后我们模拟整个过程即可,当弹出的两个元素不相等的时候那么将两个元素的差值添加到堆中,并且heapq模块中的弹出堆顶元素的heappop方法与往堆中添加元素heappush的方法都会维持堆的不变性所以来说非常方便,我们只需要模拟整个过程即可

3. 代码如下:

模拟:

from typing import List


class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        n = len(stones) - 1
        # 排序
        stones.sort()
        while n > 0:
            if stones[n] == stones[n - 1]:
                stones.pop()
                stones.pop()
            else:
                stones[n - 1] = stones[n] - stones[n - 1]
                stones.pop()
                # 重新排序
                stones.sort()
            n = len(stones) - 1
        return 0 if n < 0 else stones[0]

大根堆:

import heapq
from typing import List


class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # heapq模块构建一个小根堆(添加了负号相当于是大根堆)
        stones = [-stone for stone in stones]
        heapq.heapify(stones)
        # 当堆中只有两个元素的时候那么执行循环最终堆中会只剩下一个元素或者是0个元素
        while len(stones) > 1:
            # 弹出堆中较大的两个元素
            poll1 = heapq.heappop(stones)
            poll2 = heapq.heappop(stones)
            # poll1肯定是小于poll2的因为之前是在元素的前面添加了负号所以相减之后还是负值
            if poll1 != poll2:
                heapq.heappush(stones, poll1 - poll2)
        if len(stones) > 0: return -stones[0]
        else: return 0

 

上一篇:Codeforces 328A-IQ Test(数列)


下一篇:1046 A^B Mod C