โปรแกรมหาจำนวนครั้งที่ต้องกระโดดน้อยที่สุดเพื่อถึงปลายอาร์เรย์ใน Python

สมมติว่าเรามีอาร์เรย์ nums ค่าทุกตัวเป็นบวก เริ่มที่ index 0 แต่ละค่าแทนความยาวกระโดดสูงสุดที่ตำแหน่งนั้น เป้าหมายคือถึง index สุดท้าย (n-1) ด้วยจำนวนครั้งน้อยที่สุด

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

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

1. end = 0, jumps = 0, farthest = 0
2. วนลูป i จาก 0 ถึง len(nums)-1:
   • farthest = max(farthest, nums[i] + i)
   • ถ้า i == end และ i != len(nums)-1:
     • jumps += 1
     • end = farthest
3. คืนค่า jumps

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

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([3, 4, 3, 0, 1]))  # Output: 2

อินพุต / เอาต์พุต

Input: [3, 4, 3, 0, 1]

Output: 2