LeetCode 45 跳躍遊戲2

給定一個非負整數數組，你最初位于數組的第一個位置。

數組中的每個元素代表你在該位置可以跳躍的最大長度。

你的目标是使用最少的跳躍次數到達數組的最後一個位置。

思路

這一條題目有兩思路，一個是 貪心算法，還有一個是轉化為圖的形式考慮，使用bfs算法，我先寫下bfs思路，greedy 我還有點問題。

bfs

此題就相當于将這個序列轉化為樹，每個節點能到達的範圍就是每一層的節點個數。而跳躍次數就相當于樹的層數。

對于每個元素A，有一個最大步數，在此範圍内的元素就相當于A的鄰結點，從第一個節點開始，掃描它的鄰結點，使用一個值curMaxIndex來記錄目前節點的鄰結點最大下标（就是從目前點所能到達的最遠元素的下标），然後用一個值furMaxIndex來記錄目前鄰結點所能到達的最大下标，然後更新curMaxIndex為furMaxIndex，再進入下一層，重複操作，直到某一層滿足furMaxIndex>=nums.length-1,說明目前節點的鄰結點所能到達的最大位置已經等于或者超過了最後一個元素位置，則說明成功，則傳回目前層數+1。

代碼

public class Jump_Game_2 {
    /**
     * @return int
     * @author chy
     * @creed: Talk is cheap,show me the code
     * @date 25/4/2019 7:49 PM
     * @desc: 45 跳躍遊戲2 給定一個非負整數數組，你最初位于數組的第一個位置。
     * <p>
     * 數組中的每個元素代表你在該位置可以跳躍的最大長度。
     * <p>
     * 你的目标是使用最少的跳躍次數到達數組的最後一個位置。
     */
    public int jump(int[] nums) {
        int len = nums.length, i = 0, level = 0, curMaxIndex = 0;//level 表示目前的層數，即跳躍步數，curMaxIndex表示目前層的所能到達的最大下标
        if (len <= 1) return 0;
        while (i <= curMaxIndex) {
            int furMaxIndex = curMaxIndex;//表示下一層所能到達的最大下标，首先初始化為目前層的最大下标，循環結束後将下一層在更新到目前層，這樣表示向下一層搜尋。
            for (; i <= curMaxIndex; i++) {//對目前層的節點進行搜尋，對每個節點進行判斷不斷更新下一層所能到達的最大下标
                furMaxIndex = Math.max(furMaxIndex, nums[i] + i);
                if (furMaxIndex >= len - 1) return level + 1;//如果下一層的最大下标超過或者等于最後最後一個元素下标，則表示已經到達最後一個元素可以進行傳回
            }
            level++;
            curMaxIndex = furMaxIndex;
        }
        return -1;
    }


    public static void main(String argc[]) {
        System.out.print(new Jump_Game_2().jump(new int[]{2, 3, 1, 1, 4}));
    }
}