Jump Game ใน Python - ตรวจสอบการกระโดดถึงจุดสิ้นสุด

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มที่ไม่ใช่ลบ เราอยู่ที่ดัชนีแรกของอาร์เรย์ แต่ละองค์ประกอบแทนความยาวการกระโดดสูงสุดที่ตำแหน่งนั้น เราต้องตรวจสอบว่าสามารถถึงดัชนีสุดท้ายได้หรือไม่ ตัวอย่างเช่น อาร์เรย์ [2,3,1,1,4] จะได้ผลลัพธ์ True เพราะกระโดด 1 ขั้นจากตำแหน่ง 0 ถึง 1 แล้วกระโดด 3 ขั้นจากตำแหน่ง 1 ถึงจุดสิ้นสุด

ขั้นตอนการทำงาน

1. n := length of array A - 1
2. วนลูป i := n - 1 ลงถึง -1:
   • ถ้า A[i] + i > n ให้ n := i
3. คืนค่า true เมื่อ n = 0 มิฉะนั้น false

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

class Solution(object):
    def canJump(self, nums):
        n = len(nums) - 1
        for i in range(n-1, -1, -1):
            if nums[i] + i >= n:
                n = i
        return n == 0

ob1 = Solution()
print(ob1.canJump([2,3,1,1,4]))

อินพุต

[2,3,1,1,4]

เอาต์พุต

True