Python에서 X를 0으로 줄이는 최소 연산을 찾는 프로그램

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 :=숫자 크기
• leftMap :=새 지도
• leftMap[0] :=-1
• 왼쪽 :=0
• 0 ~ n - 1 범위의 i에 대해
  • 왼쪽 :=왼쪽 + 숫자[i]
  • left가 leftMap에 없으면
    • leftMap[왼쪽] :=나
• 오른쪽 :=0
• an :=n + 1
• n에서 0 사이의 i에 대해 1만큼 감소, do
  • 내가
  • 오른쪽 :=오른쪽 + 숫자[i]
• 왼쪽 :=x - 오른쪽
• leftMap에 왼쪽이 있으면
  • ans :=ans 및 leftMap[left] + 1 + n-i의 최소값

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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