โปรแกรมหาขั้นตอนน้อยสุดไปถึง index สุดท้ายใน Python

สมมติว่ามีรายการ nums เริ่มที่ index 0 แต่ละขั้นเดินได้ i+1, i-1, หรือ j ที่ nums[i] == nums[j] ต้องการขั้นตอนน้อยสุดไป index สุดท้าย

ตัวอย่าง: nums = [4,8,8,5,4,6,5] ผลลัพธ์ 3: 0→4 (ค่า 4), 4→3 (ค่า 5), 3→6 (ค่า 5)

ขั้นตอนการแก้ปัญหา

1. สร้าง map pos เก็บ index ของแต่ละค่า
2. BFS: q = deque([(0,0)]), visited[0] = True
3. วนลูปながら q:
   • u, d = q.popleft()
   • ถ้า u == n-1: คืน d
   • เพิ่มเพื่อนบ้าน: pos[nums[u]] + [u-1, u+1] ถ้ายังไม่เยี่ยม
   • ลบ pos[nums[u]] (ป้องกัน revisit ค่าเดิม)

ตัวอย่างโค้ด

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]

เอาต์พุต

3