โปรแกรมตรวจสอบว่าสามารถถึงปลายลิสต์ได้หรือไม่เมื่อเริ่มจากดัชนี k ใน Python

ให้ลิสต์ nums และดัชนีเริ่มต้น k ที่ตำแหน่ง i กระโดดซ้าย/ขวาได้ nums[i] ขั้น ตรวจสอบว่าถึงดัชนีสุดท้ายได้หรือไม่

ตัวอย่าง: nums=[0,0,2,1,3,3,1,1], k=2 → True (2→4→7)

อัลกอริธึม DFS/Stack

• ใช้ stack tovisit เริ่มจาก k
• pop ดัชนี ถ้าเป็นดัชนีสุดท้าย → True
• ถ้ายังไม่เยี่ยม: mark visited, push ดัชนีใหม่ i±nums[i] ถ้าอยู่ในขอบเขต

การนำไปใช้

class Solution:
    def solve(self, nums, k):
        n = len(nums)
        visited = [0] * n
        tovisit = [k]
        while tovisit:
            i = tovisit.pop()
            if i == n - 1:
                return True
            if visited[i] != 1:
                visited[i] = 1
                up = i + nums[i]
                dn = i - nums[i]
                if up < n:
                    tovisit.append(up)
                if dn >= 0:
                    tovisit.append(dn)
        return False

ob = Solution()
print(ob.solve([0,0,2,1,3,3,1,1], 2))  # True