• 关键字:贪心
  • 难度:难
  • 题目大意:给出一个正整数序列,每个序列上的数都代表你到达这个位置后最多可向后跳跃的距离,如果你现在处于序列的头部,那么你最少需要多少次才可以跳到序列的尾部。

题目描述

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.)

解法

看完这道题目,可能大部分的读者都能够想出这样一个相对简单的解法:将每个位置都看作一个点,并从第i个点向它之后的nums[i]个点都连一条长度为1的有向边,而现在的问题就是从0号点到达size-1号点需要的最短距离,这就是一个很简单的最短路问题,实际上由于边的长度均为1,而且不存在环,我们可以用宽度优先搜索(时间复杂度为O(n^2),即边数)来进行相关的计算。

但是这样一道难度为Hard的题会让我们就这么简单通过么?笔者觉得是不会的,所以这题肯定还存在着一些优化。

不难发现,这道题目转换出的最短路问题存在三个条件:

  • 边的长度均为1
  • 不存在环
  • 连出的边是连续的

我们是不是可以用这三个“很强”的条件来做一些优化呢,答案自然是肯定的!

——如果令f[i]表示从0号点到达i号点的最短路径,那么对于任意i<j,有f[i]<=f[j],即f是非递减的,这个结论的证明是显然的,在此不作过多赘述。

在有了这样的结论之后,我们就会发现,其实对于f数组来说,它会是一段段的存在,先是一个0,然后是一段1,然后是一段2,依此类推,那么现在问题来了,每一段的长度是多少呢?

这个问题很好回答,如果我们令l[k]表示f数组中值为k的一段的左边界,r[k]表示f数组中值为k的一段的有边界,那么有

  • l[k] = r[k - 1] + 1,这是显然的
  • r[k] = max{i + nums[i] | l[k - 1] <= i <= r[k - 1]},由于f值为k的位置一定是从f值为k-1的位置走来的,所以只需要看从所有f值为k-1的位置里最远可以到达的地方即可。

也就是说,我们可以在对nums的一遍扫描中,依次求出所有的l[k]和r[k],而f数组也就自然求解出来了——答案也就得到了。

这道题目虽然在LeetCode上标记为Hard,但是最后得出的解决方法也不算特别的复杂,主要是利用转换后最短路问题的一些特殊性质得到了非常有用的结论,来加速了整个最短路径的计算。

参考代码

class Solution {
public:
    int jump(vector<int>& nums) {
        // 初始化l[0], r[0]
        int k = 0, l = 0, r = 0;
        // 当最后位置的f值没有计算出时保持计算
        while (r < nums.size() - 1) {
            int next_r = r;
            // 遍历l[k]到r[k],计算r[k+1]
            for (int i = l; i <= r; i++) next_r = max(next_r, i + nums[i]);
            // 替换到k+1,以进行之后的计算
            k++; l = r + 1; r = next_r;
        }
        // 返回最后一个位置的f值
        return k;
    }
};

登录发表评论 注册

反馈意见