算法(5)Jump Game
2024-08-30 16:07:28
题目：非负数的数组，每个数组元素代表这你能最大跨越多少步，初始在0的位置，问，能不能正好调到数组的最后一位！
https://leetcode.com/problems/jump-game/#/description
思路1：从尾部记录每个元素能不能到达末尾，算法复杂度O(n*n)【当时想出这个算法，还自以为不错，但是leetcode说算法超时呀，被分分钟教做人】
思路2：对这整个数组中的数据结构深刻的理解！（参考：http://blog.csdn.net/linhuanmars/article/details/21354751），首先明白一个问题：只要数组中不含有0，那么这个数组肯定是可以跳过去的！==> 得到一个结论是：只要能跳到数组外面，那么我们就一定能够跳到最后一个位置！所以就看下从数组中第一个位置开始，最远能跳到哪里就好了！之前的疑惑包括：1）怎么确定从第一个下标开始能跑多远呢？难道我们不需要递归这一路上所有的步数可能吗？万一路上遇到一个0，那不直接盼死刑，我们就得退一步，然后求少走的这条路啊！这就是之前的症结所在，是一种线性思维！于是有了参考网页中的算法：我们同时记录全局最优和局部最优。全局最优，实时更新，全局最优之间的每一个节点，目前都是可以到达的知道吗！呃呃呃，需要分析的东西好多，并且这些东西都是解题思路的关键呢！那么只要在这个范围之内的节点能够到达更远的地方，那么全局的最远的点就应该被更新！
答案：
https://github.com/honpey/codebox/blob/master/leetcode/array/p55.cpp
最新文章
- 抛弃jQuery：Why?
- [PHP]Yii2框架的坑
- Scrum Meeting 2-20151202
- cannot find -lgcc_s
- Linux How to add a new disk to LVM
- ofstream的问题
- 开扒php内核函数，第一篇 bin2hex
- ***iOS 项目的目录结构能看出你的开发经验
- Android Studio删除工程里面无用的代码和资源
- HDU 4521 小明系列问题——小明序列 (线段树维护DP)
- win7提示Xshell5提示缺少msvcp110.dll解决办法
- Example012点击修改属性
- Java入门篇（一）——如何编写一个简单的Java程序
- [国嵌攻略][061][2440LCD驱动设计]
- bzoj 4870: [Shoi2017]组合数问题 [矩阵乘法优化dp]
- 传输层的端口与TCP标志中的URG和PSH位
- 音频 m4a 转 wav
- Intellij Idea 解决字符乱码、设定颜色主题、字体
- 聚类——K-means
- Rsync的一般使用需求