找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1887|回复: 5
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Jump Game】-【刷题第一弹】

[复制链接]

24

主题

9

精华

602

积分

超级会员

Rank: 4

积分
602
发表于 10-23-2014 06:27 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-7-2014 12:44 AM 编辑

快速通道:
https://oj.leetcode.com/problems/jump-game/

=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================


思路:max表示可以到达的最远的位置,如果坐标imax大,则无法到达i,返回false


java代码:
  1. public boolean canJump(int[] A) {
  2.                 int max = A[0];
  3.                 int i = 0;
  4.                 for (; i < Math.min(A.length, max + 1); ++i) {
  5.                         if (max < A【i】 + i) {
  6.                                 max = A【i】 + i;
  7.                         }
  8.                         if (max >= A.length - 1)
  9.                                 return true;
  10.                 }
  11.                 return false;
  12.         }
复制代码


复杂度:O(n)

本帖被以下淘专辑推荐:

7

主题

1

精华

710

积分

超级会员

Rank: 4

积分
710
发表于 10-24-2014 12:47 AM | 显示全部楼层
同学昨天Facebook on campus 面试,原题。

点评

看来还是需要多刷题啊  发表于 11-18-2014 01:14 AM
回复 支持 反对

使用道具 举报

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 11-18-2014 01:13 AM | 显示全部楼层
本帖最后由 MengMa 于 12-22-2014 12:04 AM 编辑

来个动态规划的,设f[ i ]为在A [ i ]处剩余的最大步数,则f[ i ] = max(f[i - 1], A[i - 1]) - 1,时间复杂度O(n),空间复杂度O(n)
  1.     bool canJump(int A[], int n) {
  2.         vector<int> f(n, 0);
  3.         
  4.         for(int i = 1; i < n; i++){
  5.             f【i】 = max(f[i - 1], A[i - 1]) - 1;
  6.             if(f【i】 < 0) return false;
  7.         }
  8.         return f[n - 1] >= 0;
  9.     }
复制代码
最后一行直接return true;不需要比较f[n - 1] >= 0

补充内容 (3-16-2015 09:23 PM):
根据状态转移方程,优化后空间复杂度可以降到O(1)
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表