Python中的最后一块石头重量

假设我们有一些石头，每块石头都有一个正整数重量。每一轮，我们将取两块最重的石头并将它们一起粉碎。假设石头的重量分别为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]))

输入

[2,7,4,1,6,1]

输出

1

更新于：2020年4月28日

1K+ 浏览量

开启您的职业生涯

完成课程获得认证

开始学习
广告