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