【leetcode】Jump Game I, II 跳跃游戏一和二
题目:
Jump Game I:
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
.
Jump Game 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.)
Java代码例如以下:
public class Jump_Game { public static void main(String[] args) {
int[] A = { 2, 3, 1, 1, 4 };
int[] B = { 3, 2, 1, 0, 4 }; System.out.println(canJump(A));
System.out.println(canJump(B)); } public static boolean canJump(int[] A) {
boolean[] can = new boolean[A.length];
can[0] = true; for (int i = 1; i < A.length; i++) {
for (int j = 0; j < i; j++) {
if (can[j] && j + A[j] >= i) {
can[i] = true;
break;
}
}
}
return can[A.length - 1];
}
}
public class jump_game_2 { public static void main(String[] args) {
int[] A = { 2, 3, 1, 1, 4 };
int[] B = { 3, 2, 1, 0, 4 }; System.out.println(jump(A));
System.out.println(jump(B));
} public static int jump(int[] A) {
int[] steps = new int[A.length];
steps[0] = 0; for (int i = 1; i < A.length; i++) {
steps[i] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++) {
if (steps[j] != Integer.MAX_VALUE && j + A[j] >= i) {
steps[i] = steps[j] + 1;
break;
}
}
}
return steps[A.length - 1];
}
}
最新文章
- EQueue 2.3.2版本发布(支持高可用)
- Android Sqlite数据库相关——实现 Sqlite 数据库版本升级
- Bootstrap 表格 笔记
- Asp.Net_单点登录
- iOS -数据库网络之xml解析
- 【BZOJ】1191: [HNOI2006]超级英雄Hero(二分图匹配)
- SourceTree工具进行提交合并代码步骤
- HTML5 自动聚焦 属性
- cf D. Maximum Submatrix 2
- HDU-1049
- PullToRrefresh自定义下拉刷新动画
- c语言中malloc realloc 和calloc的联系与区别
- CSS控制文本在一行内显示,若有多余字符则使用省略号表示
- JS面向对象笔记二
- Dijkstra算法 Java实现
- grep -v 反向查找
- CF28D Don&#39;t fear, DravDe is kind
- jrockit静默安装笔记
- win 控制台工作路径切换
- Micro