【leetcode刷题笔记】Jump Game II
2024-08-29 19:37:39
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.)
题解:跟Jump Game十分相像,把原来的boolean数组改成int型数组,用来记录到达i时候最小的步骤数目,遍历j(j<i),考察从j跳到i需要的步骤数目是否小于当前的reach[i],如果小于,就更新reach[i]。最终返回reach[A.length-1]即可。
代码如下:
public class Solution {
public int jump(int[] A) {
if(A == null || A.length == 0)
return 0; int[] reach = new int[A.length];
Arrays.fill(reach, Integer.MAX_VALUE);
reach[0] = 0; for(int i = 1;i < A.length;i++){
for(int j = 0;j < i;j++){
if(reach[j] != Integer.MAX_VALUE && j+A[j]>=i){
reach[i] = Math.min(reach[i], reach[j]+1);
break;
}
}
} return reach[A.length-1];
}
}
最新文章
- [恶趣味]搞了下局域网内的arp网络欺骗
- 为 Github 创造 Integration
- apache vhost
- UE4在C++中使用OnComponentBeginOverlap之类的时间
- web服务器内置对象,或者说是ServletAPI的实例
- SpringMVC 避免IE执行AJAX时,返回JSON出现下载文件
- Web模板引擎本质前奏
- Android Java混淆(ProGuard)
- php curl_exec optimize
- 线性整流函数(ReLU)
- P3167 [CQOI2014]通配符匹配
- mod_fcgid: HTTP request length 136136 (so far) exceeds MaxRequestLen (131072)
- js判断是否为undefined
- Linux常见目录使用区别
- WebSocket原理分析
- flutter 保存图片到本地
- Android开发-API指南-<;activity>;
- iOS 快速遍历 效率分析 for loop for in enumerateBlock 适用条件
- webpack4.x ,1基本项目构建 详解
- .Net反射机制