Jump Game II ใน Python

กำหนดอาร์เรย์จำนวนเต็มบวก เริ่มที่ index 0 แต่ละค่าคือ max jump length จากตำแหน่งนั้น ต้องหาจำนวนกระโดดน้อยที่สุดเพื่อถึง index สุดท้าย

ตัวอย่าง: [2,3,1,1,4] → 2 (กระโดด 0→1 แล้ว 1→4)

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

• end = 0, jumps = 0, farthest = 0
• วน i จาก 0 ถึง n-1: farthest = max(farthest, nums[i] + i)
• ถ้า i == end และ i != n-1: jumps++, end = farthest

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

class Solution(object):
    def jump(self, nums):
        end = 0
        jumps = 0
        farthest = 0
        for i in range(len(nums)):
            farthest = max(farthest, nums[i] + i)
            if i == end and i != len(nums) - 1:
                jumps += 1
                end = farthest
        return jumps

ob = Solution()
print(ob.jump([2,3,1,1,4]))

อินพุต

[2,3,1,1,4]

เอาต์พุต

2