問題

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

例子

Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note:
You can assume that you can always reach the last index.

分析

首先考慮dp，空間復(fù)雜度為O(n)，時間復(fù)雜度為O(n^2)，超時；
再考慮bfs，先列出從起點(diǎn)出發(fā)能跳到的節(jié)點(diǎn)，再列出從這些節(jié)點(diǎn)出發(fā)能跳到的節(jié)點(diǎn)......直到跳到終點(diǎn)。記錄bfs的層數(shù)。

要點(diǎn)

dp/dfs

時間復(fù)雜度

O(n)

空間復(fù)雜度

O(1)

代碼

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() < 2) return 0;
        // i:數(shù)組下標(biāo) level: bfs層數(shù)
        // curRange: 當(dāng)前能跳到的最遠(yuǎn)范圍
        // nextRange: 下一步能跳到的最遠(yuǎn)范圍
        int i = 0, level = 0, curRange = 0, nextRange = 0;
        while (i <= curRange) {
            level++;
            for (; i <= curRange; i++) {
                nextRange = max(nextRange, i + nums[i]);
                if (nextRange >= nums.size() - 1) return level;
            }
            curRange = nextRange;
        }
        return 0;
    }
};

擴(kuò)展

如果問題中數(shù)組的元素表示只能跳的步數(shù)（原題目為能跳的最大步數(shù)），那么可能會有一些節(jié)點(diǎn)會跳不到，但還可以用bfs在O(n)時間內(nèi)解決。