- 浏览: 130192 次
文章分类
- 全部博客 (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.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
[分析] 暴力做法是在每个位置 i, 跳 1 到 nums[i]步,看是否能够达到最后,妥妥超时。超时的case正好是无数的 1, 让我想到如果数组中的元素全部是正数,则必然可以跳到最后,因此关键是查看数组中的那些 0 是否可以被跳过,于是产生了方法2,觉得肯定有更优的。翻看自己的历史记录,代码上都比自己精简,更让人气愤的是不理解,orz。网上找了大神们的解析,理解了,而且发现自己之前被Accept的3种做法仅剩1种现在还能被Accept,其余一种就是http://blog.csdn.net/kenden23/article/details/17242835 这篇博客指出的leetcode老test case的漏网之鱼,一种是递归的实现导致statck overflow。非常赞同该博客指出的此题关键是明确结束条件,方法2的结束条件是判断所有的 0 是否可以被跳过,效率是O(n^2), 两篇参考博客中的方法均是O(n),方法4的结束条件是:
记录lastJump的位置,循环i到lastJump,所有位置,找出其中的最大值maxJump =max{ i+A[i]};如果这个区间内的最大值maxJump <= lastJump,那么就返回假,因为没有任何一个位置可以跳出这个位置。 如果没有这样的位置,一直可以跳到最后,那么就返回为真。
方法3, 我的理解,贪婪地往前跳,循环结束的条件是要么到最后了要么无法继续往前跳了。
[PS] ref2博主Code_Ganker认为这题属于DP,希望自己对各种算法思想的理解在不断练习中加深。发现巧妙的解法是一件让人开心的事儿。
[ref]
http://blog.csdn.net/kenden23/article/details/17242835
http://blog.csdn.net/linhuanmars/article/details/21314059
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
[分析] 暴力做法是在每个位置 i, 跳 1 到 nums[i]步,看是否能够达到最后,妥妥超时。超时的case正好是无数的 1, 让我想到如果数组中的元素全部是正数,则必然可以跳到最后,因此关键是查看数组中的那些 0 是否可以被跳过,于是产生了方法2,觉得肯定有更优的。翻看自己的历史记录,代码上都比自己精简,更让人气愤的是不理解,orz。网上找了大神们的解析,理解了,而且发现自己之前被Accept的3种做法仅剩1种现在还能被Accept,其余一种就是http://blog.csdn.net/kenden23/article/details/17242835 这篇博客指出的leetcode老test case的漏网之鱼,一种是递归的实现导致statck overflow。非常赞同该博客指出的此题关键是明确结束条件,方法2的结束条件是判断所有的 0 是否可以被跳过,效率是O(n^2), 两篇参考博客中的方法均是O(n),方法4的结束条件是:
记录lastJump的位置,循环i到lastJump,所有位置,找出其中的最大值maxJump =max{ i+A[i]};如果这个区间内的最大值maxJump <= lastJump,那么就返回假,因为没有任何一个位置可以跳出这个位置。 如果没有这样的位置,一直可以跳到最后,那么就返回为真。
方法3, 我的理解,贪婪地往前跳,循环结束的条件是要么到最后了要么无法继续往前跳了。
[PS] ref2博主Code_Ganker认为这题属于DP,希望自己对各种算法思想的理解在不断练习中加深。发现巧妙的解法是一件让人开心的事儿。
[ref]
http://blog.csdn.net/kenden23/article/details/17242835
http://blog.csdn.net/linhuanmars/article/details/21314059
public class Solution { // Method 4: O(n) // http://blog.csdn.net/kenden23/article/details/17242835 public boolean canJump (int[] nums) { int lastJump = 0, maxJump = 0; for (int i = 0; i < nums.length - 1; i++) { maxJump = Math.max(maxJump, i + nums[i]); if (i == lastJump) { if (maxJump == lastJump) return false; lastJump = maxJump; } } return true; } // Method 3: O(n), DP // http://blog.csdn.net/linhuanmars/article/details/21314059 public boolean canJump3(int[] nums) { if (nums == null || nums.length == 0) return true; int maxJump = 0; int last = nums.length - 1; for (int i = 0; i <= maxJump && i < last; i++) { maxJump = Math.max(maxJump, i + nums[i]); } if (maxJump < last) return false; else return true; } // Method 2: O(n^2), 依次判断数组中0是否可以被跳过 public boolean canJump2(int[] nums) { int lastZero = -1, currZero = -1; int i = 0; int N = nums.length; while (i < N) { int j = 0; // index which is expected to jump pass currZero while ( j < currZero) { if ((currZero != N - 1 && nums[j] > (currZero - j)) || (currZero == N - 1 && nums[j] >= (currZero - j))) { // currZero can be skipped lastZero = currZero; break; } else { j++; } } if (j == currZero) return false; // search the next zero position while (i < N) { if (nums[i] == 0) { currZero = i; break; } else { i++; } } i++; } return true; } // Method 1: time out public boolean canJump1(int[] nums) { return jump(nums, 0, nums.length - 1); } private boolean jump(int[] nums, int pos, int last) { if (pos >= last) return true; for (int step = 1; step <= nums[pos]; step++) { if (jump(nums, pos + step, last)) return true; } return false; } }
发表评论
-
Leetcode - Ugly Number II
2015-08-24 22:54 1116[分析] 暴力的办法就是从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 462Given a 2D binary matrix filled ... -
Leetcode - Paint House
2015-08-16 10:48 1112There are a row of n houses, ea ... -
Leetcode - Largest Number
2015-08-15 20:16 544Given a list of non negative in ... -
Leetcode - Different Ways to Add Parentheses
2015-07-29 20:21 1150Given 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 563There are N gas stations along ... -
Jump Game II
2015-07-05 16:49 498Given an array of non-negative ... -
Leetcode - Interleaving String
2015-06-07 11:41 564Given s1, s2, s3, find whe ... -
Leetcode - Wildcard Matching
2015-06-06 20:01 948Implement wildcard pattern ma ... -
Leetcode - Maximal Square
2015-06-04 08:25 586Given a 2D binary matrix fille ... -
Leetcode - Palindrome Partition II
2015-05-21 21:15 636Given a string s, partition ... -
Leetcode - Palindrome Partition
2015-05-21 09:56 746Given a string s, partition s s ... -
Leetcode - House Robber II
2015-05-20 22:34 727Note: This is an extension of ... -
Leetcode - Maximum Rectangle
2015-05-20 08:58 460Given a 2D binary matrix fill ... -
Leetcode - Scramble String
2015-05-17 14:22 539Given a string s1, we may repre ... -
Leetcode - Regular Expression Matching
2015-05-16 16:31 383Implement regular expression ma ... -
Leetcode - Distinct Subsequences
2015-05-01 16:56 461Given a string S and a string T ... -
Leetcode - Best Time to Buy and Sell Stock IV
2015-05-01 16:11 576Say you have an array for which ...
相关推荐
1.贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一步之前的最优解则不作保留 2.由(1)中的介绍,可以知道贪
lru缓存leetcode Go 中解决的一些 Leetcode 问题 大批 ...jump-game-0055 最长公共子序列1143 最长公共子串 最长递增子序列0300 最大积子阵列0152 最大子阵列-0053 唯一路径-0062 word-break-0139 图形
leetcode卡跳跃游戏-IV 在这里找到了 Jump Game IV 的解决方案: 该解决方案适用于小型测试用例,但不适用于非常大的测试用例——仍在进行中。
leetcode 71 Python用 Python 编写 Leetcode (数据科学家的解决方案) - 易于理解的最佳解决方案,可以通过所有 Leetcode 测试用例,对于非 ...Game II (HARD) Leetcode 51. N-Queens (HARD) Leetcode 52. N-
lru缓存leetcode 已解决问题列表 (224) 1两和容易 5最长回文子串中 7反转整数简单 8字符串到整数 (atoi)中 15 3Sum中 20个有效括号简单 21轻松合并两个排序列表 第33章在旋转排序数组中搜索 35搜索插入位置容易 36个...
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode ...LeetCode ...Jump Game 56 Merge Intervals 64 Minimum Path Sum 73
II](./Array/jump-game-ii.md) [0053 最大子序和](./Array/maximum-subarray.md) [0041 缺失的第一个整数](./Array/first-missing-positive.md) [0042 接雨水](./Array/trapping-rain-water.md) [0048 旋转图像](./...
Jump Game II - 二叉树 前序遍历判断二叉树:98. Validate Binary Search Tree - 二分查找 二分查找 + 数据缓存:1095. Find in Mountain Array 链表 有序链表合并:21. Merge Two Sorted Lists 回文 双指针判断回文...
题目来源:https://leetcode-cn.com/problems/jump-game 题目 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1...
leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题
leetcode 和 oj 使用Javascript的算法练习 随着 Javascript 越来越流行,有很多 ...我把它们放在/LeetCode/目录下,例如如果你想运行LeetCode的JumpGame拼图,你只需要在shell中输入: node LeetCode/JumpGam
加油站 leetcode 力扣_实践 标签: leetcode 我的 LeetCode 练习从 2020 年开始 ...Leetcode ...55_Jump_Game 45_Jump_Game_II 121_Best_Time_to_Buy_and_Sell_Stock 122_Best_Time_to_Buy_and_Sell_Stock_
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
lru缓存leetcode 随机任务 任务来自: 中等的: - 313 项测试中 311 项的时间限制 :( 第 1 周: 第 2 周: - 中等难度! 第 3 周: [Leftmost Column with at Least a One]() - 尚未上传 第 4 周: [Subarray Sum ...
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 ...