Pythonの最後の石の重さ

いくつかの岩があると仮定します。各岩は正の整数の重みを持っています。各ターンで、2つの最も重い岩を取り、それらを一緒に粉砕します。石の重みがxとyでx<=yであると考えてください。このスマッシュの結果は2つのタイプになります。

• 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の2つの石を選択します。その後、両方が破棄されるため、配列は[1]になります。これが答えです

これを解決するには、次の手順に従います-

• 石の重み配列Wに要素がない場合は、0を返します
• Wに要素が1つしかない場合は、W [0]
を返します。
• Wには複数の要素があります-
  • 並べ替えW
  • s1：=Wの最後の要素、s2：=Wの最後から2番目の要素
  • s1 =s2の場合、Wからs1とs2を削除します
  • それ以外の場合、s1：=| s1 – s2 |、Wから最後の要素を削除し、s1をWの最後の要素として設定します
• Wに要素が1つある場合はその要素を返し、そうでない場合は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