Python에서 마지막 인덱스에 도달하는 최소 단계 수를 찾는 프로그램

<시간/>

nums라는 숫자 목록이 있고 현재 nums[0]에 있다고 가정합니다. 각 단계에서 현재 인덱스 i에서 i + 1 또는 i - 1 또는 j로 이동할 수 있습니다. 여기서 nums[i] ==nums[j]입니다. 최종 색인에 도달하는 데 필요한 최소 단계 수를 찾아야 합니다.

따라서 입력이 nums =[4, 8, 8, 5, 4, 6, 5]와 같은 경우 출력은 3이 됩니다. 값이 둘 다 4이므로 인덱스 0에서 인덱스 4로 점프할 수 있기 때문입니다. 그리고 그런 다음 인덱스 3으로 다시 이동합니다. 마지막으로 두 값이 모두 5이므로 인덱스 3에서 6으로 이동할 수 있습니다.

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

pos :=빈 지도
각 인덱스 i와 값 n(숫자)에 대해 수행
- pos[n] 끝에 i 삽입
n :=숫자 크기
visited :=크기가 n인 목록을 만들고 False로 채웁니다.
방문함[0] :=사실
q가 비어 있지 않은 동안 do
- (u, d) :=q의 왼쪽 요소, 왼쪽 요소 삭제
- u가 n - 1과 같으면
  - 반환 d
- pos[nums[u]] 및 [u - 1, u + 1] 목록의 각 v에 대해 do
  - 0 <=v
  - 방문[v] :=사실
  - q 끝에 쌍(v, d + 1) 삽입
pos[nums[u]] 제거

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

예

class Solution:
   def solve(self, nums):
      from collections import defaultdict, deque
      pos = defaultdict(list)
      for i, n in enumerate(nums):
         pos[n].append(i)
      q = deque([(0, 0)])
      n = len(nums)
      visited = [False] * n
      visited[0] = True
      while q:
         u, d = q.popleft()
         if u == n - 1:
            return d
         for v in pos[nums[u]] + [u - 1, u + 1]:
            if 0 <= v < n and not visited[v]:
               visited[v] = True
               q.append((v, d + 1))
         del pos[nums[u]]
ob = Solution()
nums = [4, 8, 8, 5, 4, 6, 5]
print(ob.solve(nums))

입력

[4, 8, 8, 5, 4, 6, 5]