- 浏览: 130613 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
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.)
[分析] 自己的暴力方法仍然超时,搬大牛的解法,能理解正确性但目测现在还不能类似地举一反三,多练习几遍,我想慢慢会领悟其中的奥妙。
[ref]
1. http://blog.csdn.net/linhuanmars/article/details/21356187
2. 很生动的解释:http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html
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.)
[分析] 自己的暴力方法仍然超时,搬大牛的解法,能理解正确性但目测现在还不能类似地举一反三,多练习几遍,我想慢慢会领悟其中的奥妙。
[ref]
1. http://blog.csdn.net/linhuanmars/article/details/21356187
2. 很生动的解释:http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html
public class Solution { // Method 2: O(n) // http://blog.csdn.net/linhuanmars/article/details/21356187 public int jump(int[] nums) { if (nums == null || nums.length <= 1) return 0; int N = nums.length; int lastReach = 0, reach = 0; int steps = 0; for (int i = 0; i <= reach && i < N; i++) { if (i > lastReach) { steps++; lastReach = reach; } reach = Math.max(reach, i + nums[i]); } return steps; } // Method 1: timeout public int jump1(int[] nums) { if (nums == null || nums.length <= 1) return 0; int N = nums.length; int[] dp = new int[N]; dp[0] = 0; for (int i = 1; i < N; i++) { dp[i] = Integer.MAX_VALUE; for (int j = 0; j < i; j++) { if (j + nums[j] >= i) dp[i] = Math.min(dp[i], dp[j] + 1); } } if (dp[N - 1] < Integer.MAX_VALUE) return dp[N - 1]; else return -1; } }
发表评论
-
Leetcode - Ugly Number II
2015-08-24 22:54 1119[分析] 暴力的办法就是从1开始检查每个数是否是丑数,发现丑数 ... -
Leetcode - Paint House II
2015-08-20 20:37 1572There are a row of n houses, ea ... -
Leetcode - Maximum Square
2015-08-16 13:33 465Given a 2D binary matrix filled ... -
Leetcode - Paint House
2015-08-16 10:48 1114There are a row of n houses, ea ... -
Leetcode - Largest Number
2015-08-15 20:16 545Given a list of non negative in ... -
Leetcode - Different Ways to Add Parentheses
2015-07-29 20:21 1154Given a string of numbers and o ... -
Candy
2015-07-05 21:22 340There are N children standing i ... -
Leetcode - Gas Station
2015-07-05 19:51 566There are N gas stations along ... -
Leetcode - Jump Game
2015-07-05 15:52 489Given an array of non-negative ... -
Leetcode - Interleaving String
2015-06-07 11:41 566Given s1, s2, s3, find whe ... -
Leetcode - Wildcard Matching
2015-06-06 20:01 951Implement wildcard pattern ma ... -
Leetcode - Maximal Square
2015-06-04 08:25 588Given a 2D binary matrix fille ... -
Leetcode - Palindrome Partition II
2015-05-21 21:15 639Given a string s, partition ... -
Leetcode - Palindrome Partition
2015-05-21 09:56 748Given a string s, partition s s ... -
Leetcode - House Robber II
2015-05-20 22:34 731Note: This is an extension of ... -
Leetcode - Maximum Rectangle
2015-05-20 08:58 463Given a 2D binary matrix fill ... -
Leetcode - Scramble String
2015-05-17 14:22 542Given a string s1, we may repre ... -
Leetcode - Regular Expression Matching
2015-05-16 16:31 386Implement regular expression ma ... -
Leetcode - Distinct Subsequences
2015-05-01 16:56 464Given a string S and a string T ... -
Leetcode - Best Time to Buy and Sell Stock IV
2015-05-01 16:11 579Say you have an array for which ...
相关推荐
1.贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一步之前的最优解则不作保留 2.由(1)中的介绍,可以知道贪
jumpgame untiy项目源码
Jump Game II Best Time to Buy and Sell Stock Best Time to Buy and Sell Stock II Longest Substring Without Repeating Characters Container With Most Water Patching Array 动态规划 Triangle Maximum ...
跳一跳辅助,适用于IOS及安卓系统,安卓模拟器可用
通过python脚本实现微信跳一跳小游戏自动跳跃
跳一跳源代码包,实现手机自动玩跳一跳,可以看一看学习一下,转自别人
leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题
一个小小的跳跃游戏,比较简单。希望大家喜欢
JumpGame
本简易版 跳一跳使用Cocos来完成编写。 (使用js进行逻辑编写) 对应csdn博客链接:https://blog.csdn.net/weixin_43388844/article/details/96730842
leetcode卡跳跃游戏-IV 在这里找到了 Jump Game IV 的解决方案: 该解决方案适用于小型测试用例,但不适用于非常大的测试用例——仍在进行中。
本文件WECHAT-Jump-JumpSharp-master.rar,微信跳一跳的源码。
可以说是它的加强版,谢谢!操作方法:按 ← → 键控制弹板,接住小球。 等级平均数值: 1级:平民:78.5% 高手:100% 2级:平民:52.1% 高手:83.6% ... 3级:平民:12.2% 高手:36.7% ... 4级:平民:5.4% 高手:...
Jump Game II - 二叉树 前序遍历判断二叉树:98. Validate Binary Search Tree - 二分查找 二分查找 + 数据缓存:1095. Find in Mountain Array 链表 有序链表合并:21. Merge Two Sorted Lists 回文 双指针判断回文...
Doodle Jump game for calc
Yaaa,您喜欢Jumping Game,所以现在就玩在线Doodle Jump游戏[更新]嬉皮乐使您跃入Doodle Jump榜首。 嬉皮在Doodle Jump中跳到顶部。 这款激动人心的平台游戏可让您向上跳跃到无限远,抓住助力,避免途中遇到野兽。 ...
and want to jump head first into the world of video game development. It’s also great follow-up book for readers of Foundation Game Design with HTML5 and JavaScript (by the same author) who want to ...
Have you ever wanted to jump on the mobile app bandwagon? Developing a mobile game has never been so fun and easy, and with the vast amount of smartphone users, it may also become a profitable thing ...
you will learn how to write the code required to set everything up, get some graphics on screen, and then jump into the fun part of adding gameplay to turn a graphics sample into a proper game....
leetcode 71 Python用 Python 编写 Leetcode (数据科学家的解决方案) - 易于理解的最佳解决方案,可以通过所有 Leetcode 测试用例,对于非 ...Game II (HARD) Leetcode 51. N-Queens (HARD) Leetcode 52. N-