注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex45 Jump Game II  

2015-05-25 21:59:22|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

比Jump Game I多了一个限制条件,要求最短步数跳出去。这个题目不太会做,不过照着别人的思路还是写了两种动态规划的算法。jump1函数里面不是o(n),每次找dp[i]最小值的时候要把前面0-i都要扫描一次,这样复杂度其实就是o(n^2)了,oj不让过。
第二种,jump函数里面其实开始的时候比较难懂,关键就是那个last的问题,只要last能持续跳到当前i,count就不用更新或者+1,一旦last跳转不到i,我们需要做的就是把current的最大跳的步数给last,继续循环,直到我们可以跳出到数组了。

class Solution {
public:
int jump1(vector<int>& nums) {
//适用dp策略 dp[i]维护跳到i所需要的最小步数
//动态规划的超时了,只能用那个线性的了
int len = nums.size();
vector<int>dp(len,INT_MAX);

dp[0] = 0; //第一步不需要跳就行了
int i, j;
for (i = 1; i < len; i++)
{
for (j = 0; j < i; j++)
{
if ((j + nums[j]) >= i)
{
//说明能从j跳到i;这里找最小值就可以了
int tmp = dp[j] + 1;//就是说从0-j再跳一步就可以了
if (tmp < dp[i])
{
dp[i] = tmp; //把最小值赋给dp[i]
break;//这个地方break是因为 dp是一个非递减的,后面的肯定>=前面的
//所以没有必要让j继续往后循环了
}
}
}
}

return dp[len - 1];
}
/*
* 算法可以这么理解,上次能跳的最远距离是last
* 当走到i的时候,如果last比i大的,则跳数不用增加
* 但是还是要维护一下当前能到达的最大距离
* 当last<i了之后就开始更新last 然后跳的步数也要 +1
*/
int jump(vector<int>& nums) {
//http://blog.csdn.net/loverooney/article/details/38455475
//算法不太好懂
int count = 0; //当前跳数
int last = 0; //上一跳可达最远距离
int current = 0; //当前一跳可达最远距
int len = nums.size();
for (int i = 0; i < len; ++i)
{
//无法向前继跳直接返回
if (i>current)
{
return -1;
}
//需要进行下次跳跃,则更新last和当执行的跳数ret
if (i > last)
{
last = current;
count++;
}
//记录当前可达的最远点
current = myMax(current, i + nums[i]);
}
return count;
}
int myMax(int a,int b)
{
return a > b ? a : b;
}
};

参考
http://blog.csdn.net/loverooney/article/details/38455475
http://www.cnblogs.com/ganganloveu/p/3761715.html
  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017