โปรแกรมค้นหาจำนวนการกระโดดขั้นต่ำที่จำเป็นในการไปถึงตำแหน่งสิ้นสุดใน Python

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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• จบ :=0, กระโดด :=0, ไกลที่สุด :=0
• สำหรับ i ในช่วง 0 ถึงความยาวของ nums – 1
  • ไกลที่สุด :=สูงสุดของที่ไกลที่สุดและ nums[i] + i
  • ถ้าฉันสิ้นสุด และฉันไม่ใช่ความยาวของ nums – 1 แล้ว
    • เพิ่มการกระโดดขึ้น 1
    • จบ :=ไกลที่สุด
• กระโดดกลับ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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]))

อินพุต

[3, 4, 3, 0, 1]

ผลลัพธ์

2