LeetCode题解 #45 Jump Game II-leetcode 相关文章-天码营
- 题目大意：给出一个正整数序列，每个序列上的数都代表你到达这个位置后最多可向后跳跃的距离，如果你现在处于序列的头部，那么你最少需要多少次才可以跳到序列的尾部。
题目描述
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的一段的有边界，那么有
Read full article from LeetCode题解 #45 Jump Game II-leetcode 相关文章-天码营
No comments:
Post a Comment