- 浏览: 136957 次
文章分类
- 全部博客 (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 1160[分析] 暴力的办法就是从1开始检查每个数是否是丑数,发现丑数 ... -
Leetcode - Paint House II
2015-08-20 20:37 1599There are a row of n houses, ea ... -
Leetcode - Maximum Square
2015-08-16 13:33 499Given a 2D binary matrix filled ... -
Leetcode - Paint House
2015-08-16 10:48 1145There are a row of n houses, ea ... -
Leetcode - Largest Number
2015-08-15 20:16 586Given a list of non negative in ... -
Leetcode - Different Ways to Add Parentheses
2015-07-29 20:21 1198Given a string of numbers and o ... -
Candy
2015-07-05 21:22 378There are N children standing i ... -
Leetcode - Gas Station
2015-07-05 19:51 603There are N gas stations along ... -
Leetcode - Jump Game
2015-07-05 15:52 528Given an array of non-negative ... -
Leetcode - Interleaving String
2015-06-07 11:41 606Given s1, s2, s3, find whe ... -
Leetcode - Wildcard Matching
2015-06-06 20:01 989Implement wildcard pattern ma ... -
Leetcode - Maximal Square
2015-06-04 08:25 617Given a 2D binary matrix fille ... -
Leetcode - Palindrome Partition II
2015-05-21 21:15 682Given a string s, partition ... -
Leetcode - Palindrome Partition
2015-05-21 09:56 783Given a string s, partition s s ... -
Leetcode - House Robber II
2015-05-20 22:34 767Note: This is an extension of ... -
Leetcode - Maximum Rectangle
2015-05-20 08:58 495Given a 2D binary matrix fill ... -
Leetcode - Scramble String
2015-05-17 14:22 581Given a string s1, we may repre ... -
Leetcode - Regular Expression Matching
2015-05-16 16:31 413Implement regular expression ma ... -
Leetcode - Distinct Subsequences
2015-05-01 16:56 503Given a string S and a string T ... -
Leetcode - Best Time to Buy and Sell Stock IV
2015-05-01 16:11 614Say you have an array for which ...
相关推荐
java java_leetcode题解之Jump Game II.java
1.贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一步之前的最优解则不作保留 2.由(1)中的介绍,可以知道贪
标题中的"wechat_jump_game-master.rar"暗示了这是一个关于微信热门小游戏“跳一跳”的辅助工具项目。这个压缩包包含了用于安卓系统和模拟器的游戏辅助资源,帮助玩家在游戏中获得更好的成绩。 首先,我们来了解...
jumpgame untiy项目源码
java java_leetcode题解之Jump Game.java
js js_leetcode题解之45-jump-game-ii.js
c语言入门 C语言_leetcode题解之45-jump-game-ii.c
而“wechat_jump_game-master.zip_JUMP_py_wechat_jump_game_跳一跳”这个压缩包,提供了一个用Python编写的自动游玩“跳一跳”的源代码,对于想要学习自动化控制、图像识别和游戏策略的开发者来说,是一份宝贵的...
第45题“跳跃游戏II”(Jump Game II)是一道典型的动态规划问题,它要求我们找到在给定数组中达到最后一个元素的最小跳跃次数。在这道题目中,每个元素代表我们可以前进的最大步数,我们需要找到一个最优策略来最小...
【微信跳一跳小游戏Python实现详解】 微信跳一跳是一款风靡一时的微信小程序游戏,玩家需要控制小人精准地跳跃到每个平台上,积累分数。本文将深入探讨如何使用Python编程语言来自动化实现微信跳一跳的小游戏过程。...
"Jump!",这个简单的标题暗示着我们即将探讨的是一个关于跳跃的游戏,而“jump!”标签则进一步强调了游戏的核心机制。在这个名为"跳跃游戏"的压缩包文件中,我们可以期待找到一系列用于创建这样一个游戏的资源和代码...
java入门 java_leetcode题解之055_Jump_Game
4. **Jump Game II**:此问题涉及到广度优先搜索(BFS)或深度优先搜索(DFS)策略,以找出在给定限制下到达最远位置的跳跃次数。它考察了图遍历和优化算法性能的能力。 5. **Sliding Window Maximum**:这是一个...
标题中的“wechat_jump_game-master.rar_JUMP_obd_sawhog_跳一跳”表明这是一个关于微信小游戏“跳一跳”的自动化脚本项目。这个项目利用了OBD(Observed Board Data)和Sawhog算法来实现游戏的自动控制,帮助用户在...
leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题
js js_leetcode题解之55-jump-game.js
- Jump Game / Jump Game II: 第一个问题要求判断是否能到达数组的最后一个位置,第二个问题要求求出最小跳跃次数到达最后一个位置。 - Permutations / Permutations II: 生成所有可能的排列组合,考虑重复元素的...
本简易版 跳一跳使用Cocos来完成编写。 (使用js进行逻辑编写) 对应csdn博客链接:https://blog.csdn.net/weixin_43388844/article/details/96730842
这个“wechat_jump_game-master.zip”压缩包就是一个基于Python实现的微信跳一跳辅助脚本项目。该项目旨在通过自动化的方式帮助玩家提高分数,其主要涉及的知识点包括Python编程、图像识别、游戏自动化以及微信小...