[leetCode] Top Interview 150: Jump Game

リンク

https://leetcode.com/problems/jump-game/?envType=study-plan-v2&envId=top-interview-150

概要

• 各マスごとに、進める最大値を記した配列numsが与えられる
  • たとえば3なら、 1, 2, 3 マスのいずれか進むことができる
• 最終マスにたどり着くことが可能かどうかを真偽値で返す

解法

線形探索法で書くことができる。
各マスから飛ぶことができる最大値を変数reachableに保存し、これがnums.length^1 = 最終マスを超えていればtrueを返すようにする。また、どう頑張っても配列内の0のマスに落ち着いてしまうテストケースも考えられるため、reachableがこれ以上更新できない（i > reachable）ときはfalseを返すようにする。
計算量は$O(N)$となる。

class Solution {
    public boolean canJump(int[] nums) {
        int reachable = 0;
        for(int i=0; i<nums.length; i++) {
            if(reachable > nums.length-1) return true;
            if(i > reachable) return false;
            reachable = Math.max(reachable, i+nums[i]);
        }
        return true;
    }
}