leetcode-1046-最后一块石头的重量 题解
题目描述
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。 最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回0。
示例
示例 1:
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 1000 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/last-stone-weight/
解题思路
题解1 苯办法， 做递归。
题解1:
执行用时：44 ms, 在所有 Python3 提交中击败了42.77%的用户 内存消耗：14.8 MB, 在所有 Python3 提交中击败了38.92%的用户
import heapq
class Solution:
def top_two(self, stones):
result = heapq.nlargest(2, stones)
return max(result), min(result)
def lastStoneWeight(self, stones: List[int]) -> int:
if len(stones) == 0:
return 0
elif len(stones) == 1:
return stones[0]
elif len(stones) > 1:
max, min = self.top_two(stones)
if max == min:
stones.remove(max)
stones.remove(min)
if len(stones) == 1:
return stones[0]
elif len(stones) > 1:
return self.lastStoneWeight(stones)
elif len(stones) == 0:
return 0
else:
stones.append(max-min)
stones.remove(max)
stones.remove(min)
if len(stones) == 1:
return stones[0]
return self.lastStoneWeight(stones)本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-01-30，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
