LeetCode - Jump Game I
5181 ワード
問題の説明
配列numsが与えられた場合、nums[i]の値に従って現在のiをジャンプすることができる.
上記の場合nums.長さ-1が達成できるかどうかの問題.
可能であればtrueを返さなければなりません.そうでなければfalseを返します.
入力例は次のとおりです.
solution([2, 3, 1, 1, 4]); // true
solution([3, 2, 1, 0, 4]); // false
ソースコード
function solution(arr) {
let last = arr.length - 1;
// 배열의 마지막 인덱스부터 루프를 돈다.
for (let i = last; i >= 0; i--) {
// 4 ... last === 4
// 3 ... 3 + 1 >= last(4) ? last = 3
// 2 ... 2 + 1 >= last(3) ? last = 2
// 1 ... 1 + 2 >= last(2) ? last = 1
// 0 ... 0 + 2 >= last(1) ? last = 0
if (i + arr[i] >= last) {
// if문의 조건이 참일시, last를 매번 최신화시켜준다.
// i + arr[i] 가 last 보다 크거나 같다면, arr[i]는 last에 점프가 가능한(도달할 수 있는) 것이다.
// 즉 i + nums[i]를 통해서 어디까지 점프할 수 있는 지 알 수 있다.
last = i;
};
};
// last 값이 0 이라면 배열의 last element까지 점프가 가능한 것이므로 true를 반환한다.
return last === 0 ? true : false;
}
solution([2, 3, 1, 1, 4]); // true
// solution([3, 2, 1, 0, 4]); // false
以上のソースコードの時間的複雑度はO(n)である.YouTubeにはJump Gameのリクエストを詳しく説明した動画があります.
これを参照として,問題の意図を正しく理解した.
ビデオリンクは次のとおりです.
Youtube | Jump Game
Reference
この問題について(LeetCode - Jump Game I), 我々は、より多くの情報をここで見つけました https://velog.io/@alsghk9701/LeetCode-Jump-Gameテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol