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 次檢視

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告