[LeetCode] 점프 게임 (1 차원 동적 계획 + 선형 스 캔)
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example: A =
[2,3,1,1,4] , return true . A =
[3,2,1,0,4] , return false . 자바 코드: 이 문 제 는 처음에 DP 로 생각 하 는 방향 이 뚜렷 합 니 다. DP [i] 를 설정 합 니 다. = i 번 째 위치 부터 마지막 위치 까지 갈 수 있 습 니까? 그러면 방정식 을 옮 기 는 것 이 좋 습 니 다.
dp[A.length - 1] = true; 코드 를 보 세 요. 하지만 시간 을 초과 할 수 있 습 니 다. 복잡 도 는 O (n ^ 2) 이기 때 문 입 니 다.
public boolean canJump(int[] A)
{
if(A.length <= 1)
return true;
if(A[0] >= (A.length - 1))
return true;
boolean[] dp = new boolean[A.length];
dp[A.length - 1] = true;
for(int i = A.length - 2; i >= 0; i--)
{
if(i + A[i] >= A.length - 1)
{
dp[i] = true;
continue;
}
for(int j = i + 1; j < A.length - 1; j++)
{
if(i + A[i] >= j)
{
dp[i] |= dp[j];
if(dp[i] == true)
break;
}
}
}
boolean res = false;
if(dp[0] == true)
res = true;
dp = null;
return res;
}다음은 O (n) 의 알고리즘 을 드 립 니 다.
우 리 는 maxlength 로 시작 위치 에서 도착 할 수 있 는 가장 먼 거 리 를 유지 한 다음 에 현재 위치 에서 마지막 위치 와 현재 위치 가 도달 할 수 있 는 지 판단 합 니 다. 만약 에 두 가지 조건 이 모두 만족 하면 true 로 돌아 갑 니 다. 만약 에 현재 위치 가 0 이 고 가장 먼 거리 가 현재 위 치 를 초과 할 수 없다 면 false 로 돌아 가 가장 먼 거 리 를 업데이트 할 수 밖 에 없습니다.
java code : 416ms
public class Solution {
public boolean canJump(int[] A) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if(A.length <= 1)
return true;
if(A[0] >= (A.length - 1))
return true;
int maxlength = A[0];
if(maxlength == 0)
return false;
for(int i = 1; i < A.length - 1; i++)
{
if(maxlength >= i && (i + A[i]) >= A.length - 1)
return true;
if(maxlength <= i && A[i] == 0)
return false;
if((i + A[i]) > maxlength)
maxlength = i + A[i];
}
return false;
}
}참고 로 토론 구역 에 이런 알고리즘 이 붙 어 있 고 지나 간 것 같 습 니 다.
4. 567913. 이 알고리즘 은 잘못된 것 입 니 다. 반 열 이 있 기 때 문 입 니 다. A = {5, 4, 0, 0, 0, 0} 은 분명히 false 로 돌아 가 야 합 니 다.
leetcode 의 데 이 터 는 여전히 약간 약 하 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
