리 트 코드 (LeetCode) 는 음수 가 아 닌 배열 을 지정 합 니 다. 당신 은 처음에 배열 의 첫 번 째 위치 에 있 었 습 니 다.
마이너스 정수 가 아 닌 배열 을 지정 합 니 다. 당신 은 처음에 배열 의 첫 번 째 위치 에 있 었 습 니 다.배열 의 모든 요 소 는 이 위치 에서 점프 할 수 있 는 최대 길 이 를 나타 낸다.네가 마지막 위치 에 도달 할 수 있 는 지 없 는 지 를 판단 해라.
예제 1: 입력: [2, 3, 1, 1, 4] 출력: true 설명: 우 리 는 먼저 한 걸음 뛰 고 위치 0 에서 위치 1 에 도착 한 다음 에 위치 1 에서 3 걸음 뛰 어 마지막 위치 에 도착 할 수 있다.
예제 2: 입력: [3, 2, 1, 0, 4] 출력: false 설명: 어쨌든 색인 이 3 인 위치 에 도착 할 것 입 니 다.그러나 이 위치의 최대 점프 길 이 는 0 이기 때문에 마지막 자리 에 도달 할 수 없다.
방법: 역순 법
우 리 는 이렇게 생각 할 수 있다. 종점 길이: k, 그 중에서 k 의 초기 값 은 Array. count - 1 (아래 표 시 된 0 부터 주의 하 십시오)
//swift
func canJump(_ nums: [Int]) -> Bool {
if nums.count <= 1 {
return true
}
var k = nums.count - 1
var pro = nums.count - 2
while pro >= 0 {
if nums[pro] + pro >= k {
k = pro
}
pro = pro - 1
}
return k == 0 ? true : false
}
복잡 도 분석
시간 복잡 도: O (n), 그 중 n 은 배열 의 크기 입 니 다.nums 배열 에 한 번 만 접근 하면 총 n 개의 위치 가 있 습 니 다.공간 복잡 도: O (1), 추가 공간 비용 이 필요 없습니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
View의 레이아웃 방법을 AutoLayout에서 따뜻한 손 계산으로 하면 성능이 9.26배로 된 이야기이 기사는 의 15 일째 기사입니다. 어제는 에서 이었습니다. 손 계산을 권하는 의도는 없고, 특수한 상황하에서 계측한 내용입니다 화면 높이의 10 배 정도의 contentView가있는 UIScrollView 레이아...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
