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