Python 中的最后一块石头的重量

pythonserver side programmingprogramming更新于 2025/11/2 9:48:17

假设我们有一些石头，每块石头的重量都是正整数。每次，我们都会拿出两块最重的石头，然后把它们砸在一起。假设石头的重量分别为 x 和 y，并且 x <= y。这种粉碎的结果可以有两种类型。

如果 x = y，则两块石头都被完全摧毁；
否则，当 x != y 时，重量为 x 的石头被完全摧毁，重量为 y 的石头有新的重量 y-x。

最后，最多剩下 1 块石头。我们必须找到这块石头的重量(没有石头剩余时为 0)。

因此，如果石头重量为 [2,7,4,1,8,1]，则结果将为 1。首先选择 7 和 8，然后得到 1，因此数组将为 [2,4,1,1,1]，其次取 2 和 4。数组将为 [2,1,1,1]，之后选择 2 和 1，数组将为 [1,1,1]，然后选择两块重量为 1 的石头，然后两块都将被销毁，因此数组将为 [1]。这就是答案

为了解决这个问题，我们将遵循以下步骤 −

如果石头重量数组 W 没有元素，则返回 0
如果 W 只有一个元素，则返回 W[0]
当 W 有多个元素时 −
- 对 W 进行排序
- s1 := W 的最后一个元素，s2 := W 的倒数第二个元素
- 如果 s1 = s2，则从 W 中删除 s1 和 s2
- 否则 s1 := |s1 – s2|，从 W 中删除最后一个元素，然后将 s1 设置为 W 的最后一个元素
如果 W 有一个元素，则返回该元素，否则返回 0

示例

让我们看看下面的实现以便更好地理解 −

class Solution(object):
   def lastStoneWeight(self, stones):
      """
      :type stones: List[int]
      :rtype: int
      """
      if len(stones) ==0:
         return 0
      if len(stones) == 1:
         return 1
      while len(stones)>1:
         stones.sort()
         s1,s2=stones[-1],stones[-2]
         if s1==s2:
            stones.pop(-1)
            stones.pop(-1)
         else:
            s1 = abs(s1-s2)
            stones.pop(-1)
            stones[-1] = s1
      if len(stones):
         return stones[-1]
      return 0
ob1 = Solution()
print(ob1.lastStoneWeight([2,7,4,1,6,1]))