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.)
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.)
看题中的意思貌似是不会出现0元素,因此总是可以走到头的,就暂不考虑这样的边界了。拿到这倒题的第一思路是从后往前DP,我们用step[i]表示第i个元素到终点的最小跳数,则
step[ i ] = 0;(i == A.length - 1)
step[ i ] = min{ step[ j ] : i < j <= min(i+ A[ j ],A.length -1) } + 1
因此不难写出这样的代码
public int jump(int[] A) { int length = A.length; int[] step = new int[length]; step[length - 1] = 0; for(int i = length - 2; i >= 0 ; i--){ int min = Integer.MAX_VALUE; for(int j = i + 1; j < length && j <= i + A[i]; j++){ if(step[j] < min){ min = step[j]; } } step[i] = min + 1; } return step[0]; }
时间复杂度自然是O(N*N) 面对这样的case:
[25000,24999,24998,24997,24996,24995....5,4,3,2,1]对每一个元素都要重复计算前面的所有元素,超时是自然的。
花费了一个半小时才AC,囧!由于本题并没有要求我们计算出跳跃路径,因此我们可以单纯的求跳数, 采取贪心的算法,比如2,3,4,1,0,5对于2,其覆盖范围是3,4,,因此我们只需要求3,4,的最大覆盖范围即可,既然在4的覆盖范围中求下一跳的最大覆盖范围。每一次更新覆盖范围,就说明要进行一跳。代码如下:
public int jump(int[] A) { int step = 0; int cover = A[0]; for (int i = 1; i < A.length; ) { int max = cover; while (i <= cover && i < A.length) { if (A[i] + i > max) { max = A[i] + i; } i++; } cover = max; step++; } return step; }
我去。。看了别人的算法,竟然发现惊人的相似o(╯□╰)o。。。。。
相关推荐
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
vs code LeetCode 插件
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
leetcode中文版
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
100个leetCode详细解答
(C++)LeetCode刷题题解答案
LeetCode 刷题笔记
LeetCode 刷题汇总1
LeetCode 选讲1
leetcode高频面试笔试题150+道,亲身总结。
Leetcode题解.pdf 刷题合集 Leecode大部分题目及答案
LeetCode-Swift, 快速LeetCode解决方案 LeetCodeLeetCode在线判断是一个包含很多收费算法的网站。 them Google Google Google Google LinkedIn this this repo 。 请免费参考并收费STAR以支持这个 repo,
leetcode全套解答python版本。包括更新到10月份的的leetcode
LeetCode 刷题