現在の合計でリストインデックスを更新して、Pythonでターゲットに到達するかどうかを確認するプログラム

targetという番号のリストがあるとします。ここで、指定されたリストと同じ長さのリストXを考えてみましょう。Xは1で埋められています。次の操作は何度でも実行できます。Xの任意のインデックスiを取得し、X [i]を現在のXの合計に設定します。最後に、Xをターゲットに変換できるかどうかを確認します。

したがって、入力がtarget =[5、9、3]のような場合、出力は最初はX =[1、1、1]であるためTrueになり、合計3で更新すると、配列は[1、1 、3]、現在の合計は5、更新[5、1、3]、現在の合計9なので、リストは[5、9、3]になり、ターゲットになります。

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

• numsに要素が1つしかない場合は、
  • numsが1の場合はtrueを返します
• q：=すべての数値が負の値を持つキューnums
• qをヒープとして作成
• s：=nums単位のすべての数値の合計
• ok：=True
• okがTrueの場合、実行します
  • x：=ヒープから要素を削除し、それを無効にします
  • d：=s-x
  • x2：=x mod d（d> 1の場合）それ以外の場合は1
  • s：=s + x2-x
  • ok：=xはx2と同じではありません
  • x：=x2
  • ヒープqに-xを挿入します
• qのすべての要素が-1の場合にtrueを返します

理解を深めるために、次の実装を見てみましょう。

例

class Solution:
   def solve(self, nums):
      if len(nums) == 1:
         return nums == [1]
      from heapq import heapify, heappop, heappush

      q = [-x for x in nums]
      heapify(q)
      s = sum(nums)
      ok = True

      while ok:
         x = -heappop(q)
         d = s - x
         x2 = x % d if d > 1 else 1
         s += x2 - x
         ok = x != x2
         x = x2
         heappush(q, -x)

      return all(x == -1 for x in q)

ob = Solution()
target = [5, 9, 3]
print(ob.solve(target))

入力

[5, 9, 3]

出力

True