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

Mô tả bài toán

Cho danh sách nums, bắt đầu tại chỉ số 0. Mỗi bước có thể nhảy sang i+1, i-1 hoặc bất kỳ j nào có nums[j] == nums[i]. Tìm số bước tối thiểu để đến chỉ số cuối cùng.

Ví dụ: nums = [4,8,8,5,4,6,5] → đầu ra 3 (0→4 (giá trị 4), 4→3 (giá trị 5), 3→6 (giá trị 5)).

Giải thuật (BFS trên đồ thị ngầm)

1. Xây dựng ánh xạ pos: giá trị → danh sách chỉ số.
2. Khởi tạo hàng đợi q với (0,0) (chỉ số, khoảng cách), mảng visited.
3. BFS: lấy (u,d) từ hàng đợi.
   • Nếu u == n-1: trả về d.
   • Xét các hàng xóm: u-1, u+1 và tất cả chỉ số cùng giá trị pos[nums[u]].
   • Nếu hợp lệ và chưa thăm: đánh dấu, đẩy vào hàng đợi với d+1.
   • Sau khi xử lý xóa pos[nums[u]] để tránh lặp lại.

Ví dụ mã Python

from collections import defaultdict, deque

class Solution:
    def solve(self, nums):
        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