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+ 瀏覽量

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告