Chương trình tìm số bước tối thiểu để đạt được chỉ mục cuối cùng trong Python

Giả sử chúng ta có một danh sách các số được gọi là nums và chúng ta hiện đang được đặt ở vị trí nums [0]. Trên mỗi bước, chúng ta có thể nhảy từ chỉ số hiện tại i sang i + 1 hoặc i - 1 hoặc j trong đó nums [i] ==nums [j]. Chúng tôi phải tìm số bước tối thiểu cần thiết để đạt được chỉ số cuối cùng.

Vì vậy, nếu đầu vào giống như nums =[4, 8, 8, 5, 4, 6, 5], thì đầu ra sẽ là 3, vì chúng ta có thể nhảy từ chỉ số 0 sang chỉ số 4 vì giá trị của chúng đều là 4. Và sau đó chúng ta quay trở lại chỉ mục 3. Cuối cùng, chúng ta có thể nhảy từ chỉ mục 3 sang chỉ số 6 vì cả hai giá trị của chúng đều là 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• pos:=một bản đồ trống
• đối với mỗi chỉ số i và giá trị n tính bằng num, thực hiện
  • chèn i vào cuối pos [n]
• n:=kích thước của nums
• đã thăm:=tạo một danh sách có kích thước n và điền vào đó là Sai
• đã ghé thăm [0]:=True
• trong khi q không trống, hãy thực hiện
  • (u, d):=phần tử bên trái của q và xóa phần tử bên trái
  • nếu u giống với n - 1, thì
    • trả về d
  • đối với mỗi v trong danh sách pos [nums [u]] và [u - 1, u + 1], hãy thực hiện
    • nếu 0 <=v
    • đã thăm [v]:=True
    • chèn cặp (v, d + 1) vào cuối q
• xóa pos [nums [u]]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

3