Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 패리티가 다른 값에 도달하는 데 필요한 최소 점프를 찾는 프로그램

<시간/>

nums라는 숫자 목록이 제공된다고 가정합니다. 여기에서 값이 목록에 있는 경우 인덱스 i + 숫자[i] 또는 인덱스 i에서 i − 숫자[i]로 점프할 수 있습니다. 따라서 입력 순서를 변경하지 않고 유지하면서 패리티가 다른 다른 값에 도달하는 데 필요한 점프 수를 찾아야 합니다. 패리티가 다른 다른 번호에 연결할 수 없으면 -1로 설정됩니다.

따라서 입력이 숫자 =[7, 3, 4, 5, 6, 9, 6, 7]과 같으면 출력은 [−1, 1, 2, −1, −1, −1, 1이 됩니다. , -1].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • bfs() 함수를 정의합니다. 이 시간이 걸립니다

    • q :=(i, 0) 쌍이 있는 새로운 양방향 대기열

    • 본 :=새로운 세트

    • q가 비어 있지 않은 동안 수행

      • (j, d) :=q의 가장 왼쪽 요소 및 q에서 가장 왼쪽 항목 삭제

      • 본에 j 추가

      • (nums[i] + nums[j]) mod 2가 0이 아닌 경우

        • 리턴 d

      • [j + nums[j], j − nums[j]]의 각 k에 대해 수행

        • 0 <=k <숫자의 크기이고 k가 표시되지 않으면

          • q의 오른쪽 끝에 (k, d + 1) 삽입

    • 10^10을 반환

  • 주요 방법에서 다음을 수행하십시오 -

  • ans :=새 목록

  • 범위 0에서 숫자 크기까지의 i에 대해

    • 본 :=새로운 세트

    • x :=bfs(i)

    • x <10^10일 때 ans에 x를 추가하고 그렇지 않으면 -1

      을 추가합니다.
  • 반환

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

from collections import deque
class Solution:
   def solve(self, nums):
      def bfs(i):
         q = deque([(i, 0)])
         seen = set()
         while q:
            j, d = q.popleft()
            seen.add(j)
            if (nums[i] + nums[j]) % 2:
               return d
            for k in [j + nums[j], j − nums[j]]:
               if 0 <= k < len(nums) and k not in seen:
                  q.append((k, d + 1))
         return 10 ** 10
      ans = []
      for i in range(len(nums)):
         seen = set()
         x = bfs(i)
         ans.append(x if x < 10 ** 10 else −1)
      return ans
ob = Solution()
print(ob.solve([7, 3, 4, 5, 6, 9, 6, 7]))

입력

numbers = [7, 3, 4, 5, 6, 9, 6, 7]

출력

[−1, 1, 2, −1, −1, −1, 1, −1]