Giả sử chúng ta có một số mảng, trong đó tất cả các phần tử đều dương. Chúng ta đang ở chỉ số 0. Ở đây, 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à đạt đến chỉ số cuối cùng (n-1, trong đó n là kích thước của nums) 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 là num - 1
- xa nhất:=tối đa của xa nhất và nums [i] + i
- nếu tôi ở cuối 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
- lượt nhảy về
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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]))
Đầu vào
[3, 4, 3, 0, 1]
Đầu ra
2