程序检查我们是否可以通过它的当前总和来更新列表索引以达到目标,或者无法在python中达到目标
假设我们有一个称为目标的数字列表。现在,让我们考虑与给定列表具有相同长度的列表X,并且X用1填充。我们可以根据需要多次执行以下操作:取X中的任何索引i并将X[i]设置为X的当前总和。最后检查X是否可以变成目标。
因此,如果输入类似于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:=所有数字的总和
好的:=正确
当确定为真时,
x:=从堆中删除元素并取反
d:=s-x
x2:=xmodd如果d>1否则为1
s:=s+x2-x
好的:=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