原题链接:http://oj.leetcode.com/problems/jump-game-ii/这道题是Jump
Game的扩展,区别是这道题不仅要看能不能到达终点,而且要求到达终点的最少步数。其实思路和Jump
Game还是类似的,只是原来的全局最优现在要分成step步最优和step-1步最优(假设当前步数是step)。当走到超过step-1步最远的位置时,说明step-1不能到达当前一步,我们就可以更新步数,将step+1。时间复杂度仍然是O(n),空间复杂度也是O(1)。代码如下:public int jump(int[] A) {
if(A==null || A.length==0)
return 0;
int lastReach = 0;
int reach = 0;
int step = 0;
for(int i=0;i<=reach&&i<A.length;i++)
{
if(i>lastReach)
{
step++;
lastReach = reach;
}
reach = Math.max(reach,A[i]+i);
}
if(reach<A.length-1)
return 0;
return step;
}
动态规划是面试中特别是onsite中非常重要的类型,一般面试中模型不会过于复杂,所以大家可以熟悉一下比较经典的几个题,比如Jump
Game,Maximum
Subarray等。
分享到:
相关推荐
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Article-Views-II-LeetCode.png 平均工资-部门-VS-公司-LeetCode.png 平均销售价格-LeetCode.png 每台机器平均处理时间 LeetCode.png Bank-Account-Summary-II-LeetCode.png Bank-Account-Summary-LeetCode.png 大国...
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
锈cauly-rust-leetcode-utils 这个项目为用 rust 语言编写 leetcode 提供了一些帮助。 如何使用 方法一: [Folk and] 克隆这个 repo。 在你的 leetcode cargo.toml 中,添加: [dependencies] cauly-rust-leetcode-...
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Swif-LeetCode-Utils:在LeetCode上快速创建和打印ListNode和TreeNode的方式
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
RandomPickWithWeight-LeetCode-528-源码.rar
Java-Leetcode-杨辉三角
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
lru缓存leetcode Go 中解决的一些 Leetcode 问题 大批 ...jump-game-0055 最长公共子序列1143 最长公共子串 最长递增子序列0300 最大积子阵列0152 最大子阵列-0053 唯一路径-0062 word-break-0139 图形
前端大厂最新面试题-leetcode-interview-ts.docx
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
leetcode 答案 -leetcode- leetcode刷题指南 不只是答案 更多的是过程 更重要的是纠错的过程
Algorithm-LeetCode-NOTES.zip,利特码,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)