凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 45. Jump Game II

分类:algorithm| 发布时间:2016-10-12 10:35:00


题目

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.

For example:

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.

题意

给出一个非负的整数数组,每个元素的值表示最多能往前跳几格,求出从数组头跳到数组尾最少需要几步。

解法 1

step 表示步数 distance 表示当前步数下最远能走到哪里 next 表示下一步最远能走到哪里

class Solution {
public:
    int jump(vector<int>& nums) {
        int step = 0;
        int distance = 0;
        int next = 0;
        for(int i = 0; i < nums.size() - 1; ++i) {
            next = max(next, i + nums[i]);
            if (i == distance) {
                ++step
                distance = next;
            }
        }

        return step;
    }
};

解法 2

从后往前迭代,用 path 保存要走过的点, 添加一个新的点时如果发现这个点能前进到 path 中最后的点之前的点时, 表示最后一个点是多余的,可以将其从 path 中删除。

class Solution {
public:
    int jump(vector<int>& nums) {
        const int n = nums.size();

        vector<int> path;
        path.push_back(n-1);
        for (int i = n-2; i >=0; --i) {
            if (i + nums[i] >= path.back()) {
                int sz = path.size();
                while (sz - 2 >= 0 && i + nums[i] >= path[sz - 2]) {  //can reach one node further
                    path.pop_back();
                    --sz;
                }

                path.push_back(i);
            }
        }

        return path.size() - 1;
    }
};