LeetCode - Jump Game I


問題の説明


配列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