모든 요소가 양수인 하나의 배열 num이 있다고 가정합니다. 우리는 인덱스 0에 있습니다. 여기에서 배열의 각 요소는 해당 위치에서 최대 점프 길이를 나타냅니다. 우리의 목표는 더 적은 수의 점프로 최종 인덱스(n-1, 여기서 n은 숫자의 크기)에 도달하는 것입니다. 따라서 배열이 [2,3,1,1,4]와 같으면 출력은 2가 됩니다. 0에서 인덱스 1로 점프한 다음 마지막 인덱스인 인덱스 4로 점프할 수 있기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 끝 :=0, 점프 :=0, 가장 멀리 :=0
- 0에서 숫자 길이 – 1까지 범위에 있는 i의 경우
- farthest :=가장 먼 것과 nums[i] + i의 최대값
- i가 끝이고 i가 숫자의 길이가 아닌 경우 – 1이면
- 점프 1 증가
- end :=가장 멀리
- 리턴 점프
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
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