检查Python中数组和能否通过三种操作变为K

假设我们有一个名为nums的数字列表和一个正值K。我们可以在nums上执行以下三种操作中的任何一种：

• 将一个数字取负；
• 将数字本身加上其索引（从索引1开始）；
• 从数字本身减去其索引。

最后，我们必须检查是否可以通过仅对每个元素执行一次这些操作来转换给定数组，使其数组的和变为k。

因此，如果输入类似于nums = [1,2,3,7] k = 8，则输出将为True，因为我们可以从2和3中减去2和3的索引，以使数组类似于[1, 0, 0, 7]，因此现在的和是8 = k。

为了解决这个问题，我们将遵循以下步骤：

• size := 100
• 定义一个函数is_ok()。这将接收i、total、k、nums和table。
• n := nums的大小
• 如果total <= 0，则
  • 返回False
• 如果i >= n，则
  • 如果total等于k，则
    • 返回True
• 返回False
• 如果table[i, total]不等于-1，则
  • 返回table[i, total]
• table[i, total] := 当(is_ok(i+1, total - 2 * nums[i], k, nums, table) 非零 或 is_ok(i+1, total, k, nums, table) 非零)时为1，否则为0
• table[i, total] := 当(is_ok(i+1, total -(i+1) , k, nums, table) 或 table[i, total])时为1，否则为0
• table[i, total] := 当(is_ok(i+1, total + i + 1, k, nums, table) 或 table[i, total])时为1，否则为0
• 返回table[i, total]
• 在主方法中执行以下操作：
• total := nums中所有元素的和
• table := 一个与size长度相同的数组，并填充-1
• 对于i从0到size的范围，执行
  • table[i] := 一个与size长度相同的数组，并填充-1
• 返回is_ok(0, total, k, nums, table)

让我们看看下面的实现，以便更好地理解：

示例

在线演示

size = 100
def is_ok(i, total, k, nums, table):
   n = len(nums)
   if total <= 0:
      return False
   if i >= n:
      if total == k:
         return True
      return False
   if table[i][total] != -1:
      return table[i][total]
   table[i][total] = is_ok(i+1, total - 2 * nums[i], k, nums, table) or is_ok(i+1, total, k, nums, table)
   table[i][total] = is_ok(i+1, total - (i+1), k, nums, table) or table[i][total] table[i][total] = is_ok(i+1, total + i + 1, k, nums, table) or table[i][total]
   return table[i][total]
def solve(nums, k):
   total = sum(nums)
   table = [-1]*size
   for i in range(size):
      table[i] = [-1]*size
   return is_ok(0, total, k, nums, table)
nums = [1,2,3,7]
k = 8
print(solve(nums, k))

输入

[1,2,3,7], 8

输出

True

Arnab Chakraborty

更新于：2020-12-30

87 次浏览

开启您的职业生涯

完成课程获得认证

开始学习