[leetCode] Top Interview 150: Jump Game II

リンク

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

概要

• 各マスごとに、進める最大値を記した配列numsが与えられる
  • たとえば3なら、 1, 2, 3 マスのいずれか進むことができる
• 最終マスにたどり着くまでに必要な最小の手数を求める
• 必ず最後のマスにたどり着けることが保証されている

解法

前問の考え方を応用する。
前提として、最後のマスにたどり着けることは制約で保障されているので、今回は気にしない。

コードはこんな感じ。

class Solution {
    public int jump(int[] nums) {
        int step = 0;
        int end = 0;
        int reachable = 0;

        for(int i=0; i<nums.length-1; i++) {
            
            // 最大到達地点を更新する
            reachable = Math.max(reachable, i + nums[i]);

            // ゴールにたどり着けそうなら step + 1 して終わる
            if(reachable >= nums.length - 1) {
                step++;
                break;
            }

            // 深さを更新する
            if(i == end) {
                step++;
                end = reachable;
            }
        }

        return step;
    }
}

reachableで今届く最大の位置を保存するのは前回と同じ。
今回違うのは、stepで飛んだ回数をカウントし、返さなくてはいけないところ。

たとえば [2,3,1,1,4] という配列があったとき、以下のように考えることができる。

1. i=0 のとき、i=1,2 のいずれかに飛ぶことができる
   a. i=1 に飛んだ場合、最大で i=4 まで飛べる
   b. i=2 に飛んだ場合、最大で i=3 まで飛べる
2. i=0 から飛べる場所のうち、より遠くに飛べる場所は i=1 なので、ここに飛ぶ
3. i=1 から飛べる最大の位置は配列の最後なので、ここに飛ぶ（終了）

ここで大事なのは 1~2 の考え方で、飛べる位置をひとつずつ確認し、より先へ飛べる地点を探して飛ぶことを繰り返すことで、最小のジャンプ数でゴールに到達することができる。