[LC] 55. Jump Game
2024-09-07 00:38:02
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.
Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Solution 1:
DP
class Solution {
public boolean canJump(int[] nums) {
if (nums == null || nums.length <= 1) {
return true;
}
boolean[] arr = new boolean[nums.length];
arr[0] = true;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] && (j + nums[j] >= i)) {
arr[i] = true;
break;
}
}
}
return arr[nums.length - 1];
}
}
Solution 2:
Greedy
class Solution {
public boolean canJump(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; i++) {
if (i > max) {
return false;
}
max = Math.max(max, i + nums[i]);
}
return true;
}
}
最新文章
- DOM节点属性
- zigbee学习之路(十三):基于协议栈的Usart 实验
- 【转】yahoo前端优化军规
- Xamarin Anroid App访问网站失败
- Android checkbox 自定义点击效果
- Python基础教程【读书笔记】 - 2016/7/7
- NOSQL之【redis的安全策略】
- centos 6.3安装mono和monoDevelop过程
- 【C语言】37个关键字
- 利用Nginx构建负载均衡server
- HDU 6047 Maximum Sequence
- java 线程池 ---- newCachedThreadPool()
- CSS white-space属性详解
- Sql Server 2012 集群配置
- Perl的变量
- Exception:两个类具有相同的 XML 类型名称,请使用 @XmlType.name 和 @XmlType.namespace 为类分配不同的名称
- js 去掉花括号
- 【CF878E】Numbers on the blackboard 并查集
- 图论最短路——spfa
- reduce()方法