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 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始
广告

© . All rights reserved.