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

示例

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

Open Compiler
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

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

3

更新于:2021年10月5日

312 次查看

开启你的职业生涯

通过完成课程获得认证

开始学习
广告