Python程式檢查是否可以透過將列表索引更新為其當前總和來達到目標

假設我們有一個名為target的數字列表。現在讓我們考慮一個與給定列表長度相同的列表X，並且X填充了1。我們可以執行以下操作任意多次：在X中取任意索引i，並將X[i]設定為X的當前總和。最後檢查X是否可以轉換為target。

因此，如果輸入類似於target = [5, 9, 3]，則輸出將為True，因為最初X = [1, 1, 1]，然後用總和3更新它，陣列將為[1, 1, 3]，當前總和為5，更新它[5, 1, 3]，當前總和為9，因此列表將為[5, 9, 3]，它是目標。

為了解決這個問題，我們將遵循以下步驟

  • 如果nums只有一個元素，則
    • 當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
    • 將-x插入堆q中
  • 當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

更新於: 2020年11月26日

91 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始
廣告