Python程序：查找将X降至零的最少操作次数

假设我们有一个名为nums的数组和另一个值x。在一次操作中，我们可以从数组中删除最左端或最右端的元素，并将该值从x中减去。我们必须找到将x精确地减少到0所需的最少操作次数。如果不可能，则返回-1。

因此，如果输入类似于nums = [4,2,9,1,4,2,3] x = 9，则输出将为3，因为首先我们必须删除最左端的元素4，因此数组将变为[2,9,1,4,2,3]，而x将为5，然后删除最右端的元素3，因此数组将变为[2,9,1,4,2]，而x = 2，然后再次从左侧或右侧删除以使x = 0，数组将变为[2,9,1,4]或[9,1,4,2]。

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

  • n := nums的大小
  • leftMap := 一个新的映射
  • leftMap[0] := -1
  • left := 0
  • 对于范围从0到n-1的i，执行以下操作：
    • left := left + nums[i]
    • 如果left不在leftMap中，则执行以下操作：
      • leftMap[left] := i
  • right := 0
  • ans := n + 1
  • 对于范围从n到0的i（递减），执行以下操作：
    • 如果i < n，则执行以下操作：
      • right := right + nums[i]
    • left := x - right
    • 如果left存在于leftMap中，则执行以下操作：
      • ans := ans和leftMap[left] + 1 + n-i的最小值
  • 如果ans与n + 1相同，则执行以下操作：
    • 返回-1
  • 返回ans

示例

让我们查看以下实现以获得更好的理解：

def solve(nums, x):
   n = len(nums)

   leftMap = dict()
   leftMap[0] = -1
   left = 0
   for i in range(n):
      left += nums[i]
      if left not in leftMap:
         leftMap[left] = i

   right = 0
   ans = n + 1
   for i in range(n, -1, -1):
      if i < n:
         right += nums[i]
      left = x - right
      if left in leftMap:
         ans = min(ans, leftMap[left] + 1 + n - i)
   if ans == n + 1:
      return -1
   return ans

nums = [4,2,9,1,4,2,3]
x = 9
print(solve(nums, x))

输入

[4,2,9,1,4,2,3], 9

输出

3

更新于：2021年10月5日

312 次查看

开启你的职业生涯

通过完成课程获得认证

开始学习
广告

© . All rights reserved.