สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มที่ไม่ติดลบ เราอยู่ในตำแหน่งแรกที่ดัชนีแรกของอาร์เรย์ แต่ละองค์ประกอบในอาร์เรย์ที่กำหนดจะแสดงความยาวการกระโดดสูงสุดที่ตำแหน่งนั้น เราต้องพิจารณาว่าเราสามารถเข้าถึงดัชนีสุดท้ายได้หรือไม่ ดังนั้นหากอาร์เรย์เป็นเหมือน [2,3,1,1,4] ผลลัพธ์จะเป็นจริง มันเหมือนกับกระโดดหนึ่งก้าวจากตำแหน่ง 0 ไปที่ 1 จากนั้นอีกสามก้าวจากตำแหน่งที่ 1 ไปจนสุด
ให้เราดูขั้นตอน -
- n :=ความยาวของอาร์เรย์ A – 1
- สำหรับ i :=n – 1, ลงไปที่ -1
- ถ้า A[i] + i> n แล้ว n :=i
- คืนค่า จริง เมื่อ n =0 มิฉะนั้น เท็จ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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
