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

HT·生活

123

 
 
 

日志

 
 

ex55 Jump Game  

2015-05-18 21:49:58|  分类: 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.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

开始看题目的时候以为,比如跳到i的时候,就只能走nums[i]步,后来一看原来是最多走nums[i]步。写了一个递归求解的过程,但是oj不给过,代码如下

bool traverse(int* nums, int numsSize, int index)
{
//写了一个递归程序 超时了
int maxStep = nums[index];
if ((index + maxStep) >= (numsSize - 1))
{
return true;
}
else
{
bool mark = false;
int nextIndex = index;

for (int i = maxStep; i >= 1; i--)
{
//nextIndex= nums[index];
//nextIndex += i;
mark = traverse(nums, numsSize, nextIndex + i);
if (mark)
return true;
}
return false;
}
}

bool canJump1(int* nums, int numsSize) {

int nextIndex = 0;
int i = 0, j;
bool mark = traverse(nums, numsSize, 0);

return mark;
}

参考网上的思路,有人用贪心算法来做,不过不是特别理解是否能找到最优解,但是oj让通过了。
刚开始step = A[0],到下一步step--, 并且取step = max(step, A[1]),这样step一直是保持最大的能移动步数,局部最优也是全局最优。见c代码

bool canJump(int* nums, int numsSize)
{
/*
* 用贪心策略,刚开始step = A[0],到下一步step--,
* 并且取step = max(step, A[1]),这样step一直是保持最大的能移动步数,局部最优也是全局最优。
*/

if (numsSize == 0)
return false;
int step = nums[0];

for (int i = 1; i < numsSize; i++)
{
if (step > 0)
{
step--;
step = step> nums[i]?step:nums[i];
}
else
return false;
}
return true;
}

后来分析了一下,结果应该是对的。维护一个maxstep,表示前一时刻能到的最大地方,到了当前位置maxstep肯定要-1,接着获得nums[i],如果maxstep比nums[i]小的话,maxstep就更新。这样,在这一过程中maxstep始终维护最大跳的步数。其中,如果出现maxstep +i 大于length的话,说明就能跳到最后了。


参考
http://blog.csdn.net/loverooney/article/details/38455475
http://www.cnblogs.com/remlostime/archive/2012/11/12/2765894.html
  评论这张
 
阅读(10)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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