Cho mảng số nguyên dương, bắt đầu tại chỉ số 0. Mỗi phần tử là độ nhảy tối đa tại vị trí đó. Tìm số nhảy tối thiểu để đến cuối mảng. Ví dụ: [2,3,1,1,4] -> 2 (nhảy từ 0 đến 1, rồi 1 đến 4).
Các bước giải quyết (Greedy O(n)):
- end = 0, jumps = 0, farthest = 0
- Duyệt i từ 0 đến n-1: farthest = max(farthest, nums[i] + i)
- Khi i == end và i != n-1: jumps++, end = farthest
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([2, 3, 1, 1, 4]))
Đầu vào
[2, 3, 1, 1, 4]
Đầu ra
2