Giả sử chúng ta có một mảng các số nguyên, trong đó tất cả các phần tử đều dương. Điểm xuất phát ban đầu là ở chỉ số 1. Mỗi phần tử trong mảng đại diện cho độ dài bước nhảy tối đa của chúng ta tại vị trí đó. Mục tiêu của chúng tôi là đến ô cuối cùng với số lần nhảy ít hơn. Vì vậy, nếu mảng giống như [2,3,1,1,4], và đầu ra sẽ là 2, vì chúng ta có thể nhảy đến chỉ mục 1 từ 0, sau đó nhảy đến chỉ mục 4, đó là chỉ mục cuối cùng.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
kết thúc:=0, nhảy:=0, xa nhất:=0
-
cho tôi trong phạm vi từ 0 đến độ dài của nums - 1
-
xa nhất:=max of xa nhất và nums [i] + i
-
nếu tôi là kết thúc và tôi không có độ dài là nums - 1, thì
-
tăng số lần nhảy lên 1
-
end:=xa nhất
-
-
-
các bước nhảy trở lại
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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]))
Đầu vào
[2,3,1,1,4]
Đầu ra
2