题目概述
解题思路
我开始想到的做法是贪心。首先维护两个指针i和cur,i用于顺序遍历,cur用来指向上一次可以跳到的最远的位置。维护一个一维数组,用来记录跳到每个位置需要的最短步数。然后考虑当前能跳到的最远距离是否超过了cur,如果超过,就把cur+1~i+A[i]这些位置的值都置为dp[i]+1;否则就不操作。我们可以保证dp[i]的值就是跳到每个位置所需最短步数,因为当dp[i]被赋值的时候,这个值被第一次访问,之后如果还有别的方法能访问到该值,其步数也必定不少于第一次访问。这个做法的时空复杂度均为O(n)。
考虑这道题的特殊性:跳跃的步数是从1~A[i]连续的,而不是只有A[i]这一个值,因此我们其实只需要维护一个变量,记录当前所能跳到的最远位置即可。如果当前可以跳到超过数组长度的位置,那么必定能跳到数组的末端位置。这样空间复杂度就变为O(1)啦。
方法性能
示例代码
时空复杂度O(n)版:
class Solution {
public:
/**
*
* @param A int整型一维数组
* @param n int A数组长度
* @return int整型
*/
int jump(int* A, int n)
{
// write code here
int *dp = new int[n];
memset(dp, 0, sizeof(int) * n);
int cur = 0;
for(int i = 0; i < n;++i)
{
if(i + A[i] > cur)
{
for(int j = min(i + A[i], n-1); j > cur;--j)
dp[j] = dp[i] + 1;
cur = i + A[i];
if(cur >= n)
break;
}
}
return dp[n-1];
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)