LC - 점프 게임 II
제목 설명
마이너스 정수 가 아 닌 배열 을 지정 합 니 다. 당신 은 처음에 배열 의 첫 번 째 위치 에 있 었 습 니 다.
배열 의 모든 요 소 는 이 위치 에서 점프 할 수 있 는 최대 길 이 를 나타 낸다.
당신 의 목 표 는 최소한 의 점프 횟수 를 사용 하여 배열 의 마지막 위치 에 도착 하 는 것 입 니 다.
예시:
: [2,3,1,1,4]
: 2
: 2。
0 1 ， 1 ， 3 。
설명:
만약 당신 이 항상 배열 의 마지막 위치 에 도착 할 수 있다 고 가정 하 세 요.
문제 풀이 의 사고 방향.
개인 AC
욕심
Golang
정방 향 검색 은 도착 할 수 있 는 가장 먼 위 치 를 찾 을 때마다 선형 시간 내 에 가장 적은 점프 횟수 를 얻 을 수 있다.
[외부 체인 이미지 저장 실패, 원본 사이트 에 도 난 방지 체인 메커니즘 이 있 을 수 있 습 니 다. 그림 을 저장 해서 바로 업로드 하 는 것 을 권장 합 니 다 (img - sCosF3Zq - 1588606771879) (LC. 0045. 점프 게임 II. assets / 45 fig1. png)]
구체 적 인 실현 에서 우 리 는 현재 도달 할 수 있 는 최대 아래 표 시 된 위 치 를 유지 하고 경계 로 기록 합 니 다.우 리 는 왼쪽 에서 오른쪽으로 배열 을 옮 겨 다 니 며 경계 에 도 착 했 을 때 경 계 를 업데이트 하고 점프 횟수 를 1 증가 시 킵 니 다.
배열 을 옮 겨 다 닐 때 우 리 는 마지막 요 소 를 방문 하지 않 습 니 다. 이것 은 마지막 요 소 를 방문 하기 전에 우리 의 경 계 는 반드시 마지막 위치 보다 크 고 그렇지 않 으 면 마지막 위치 로 넘 어 갈 수 없 기 때 문 입 니 다.마지막 요 소 를 방문 하면 경계 가 마지막 위치 인 상황 에서 우 리 는 '불필요 한 점프 횟수' 를 한 번 증가 하기 때문에 마지막 요 소 를 방문 할 필요 가 없습니다.
func jump(nums []int) int {
length := len(nums)
steps := 0
maxPosition := 0
end := 0
for i := 0; i < length - 1; i++ {
// ，
if i + nums[i] > maxPosition {
maxPosition = i + nums[i]
}
// ， 1
if i == end {
end = maxPosition
steps++
}
}
return steps
}
시간 복잡 도: O (n) O (n) O (n);
공간 복잡 도: O (1) O (1) O (1).
최 적 화
동상
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
