找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2502|回复: 7
收起左侧

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

[复制链接]

3

主题

5

精华

272

积分

高级会员

Rank: 3Rank: 3

积分
272
发表于 10-6-2014 09:41 PM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 TeamEditor 于 11-19-2014 10:24 AM 编辑

快速通道:
oj.leetcode.com/submissions/detail/12644830/

题目:

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

Hint:

这道题相对比较简单,基本从左到右扫描数组。记录每一次Jump所能到达的最远index。例如从A[0]出发,第一次Jump最远就能到达A[0] = K. 然后扫描 0 ~ K的数,找到第二Jump 最远能到达的地方。直到到达数组终点为止。

  1. public class Solution {
  2.     public int jump(int[] A) {
  3.         int n = A.length;
  4.         int t = 0, max = A[0], step = 0;
  5.         while (t < n - 1) {
  6.             step++;
  7.             if (max >= n - 1)
  8.                 return step;
  9.             int new_max = max;
  10.             for (int i = t + 1; i <= max; i++)
  11.                 new_max = Math.max(new_max, i + A[i]);
  12.             t = max;
  13.             max = new_max;
  14.         }
  15.         return step;
  16.     }
  17. }
复制代码

复杂度 O(n)


建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)

===============
点此查看汇总贴
===============

本帖被以下淘专辑推荐:

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 11-18-2014 02:50 AM | 显示全部楼层
这题能用动态规划做吗?求解释

补充内容 (11-18-2014 09:25 PM):
渣渣顺便吐槽一下,我咋觉得这题一点也不简单呀
回复 支持 反对

使用道具 举报

3

主题

5

精华

272

积分

高级会员

Rank: 3Rank: 3

积分
272
 楼主| 发表于 11-18-2014 04:39 PM | 显示全部楼层
wenyuanhust 发表于 11-18-2014 02:50 AM
这题能用动态规划做吗?求解释

这题只是从左到右扫描数组一遍,每个数字只访问一次,我觉得应该不会有更低的复杂度了吧。
回复 支持 反对

使用道具 举报

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

本版积分规则

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