关注
解决第三题时的方法和leetcode上45.Jump Game II也很像,都是用到了贪心的思想。 先说leetcode上的那道题,初始化lastMax = 0, curMax = 0两个指针,每次遍历i <= lastMax的所有nums[i]的值,并计算i+nums[i](相当于计算每个i能到达的最大位置下标)取最大的那个,进而更新curMax和lastMax指针。注意当lastMax>=length-1时就得到最终跳跃的步数,而当某一次的while循环中lastMax == curMax说明不可能跳到数组最后一个下标。代码如下: class Solution {
public int jump(int[] nums) {
if(nums == null || nums.length <= 1){
return 0;
}
int step = 0, lastMax = 0, curMax = 0, i = 0;
while(lastMax < nums.length-1){
while(i <= lastMax && i < nums.length){
curMax = Math.max(curMax, i+nums[i]);
i += 1;
}
if(lastMax == curMax){
return -1;
}
step += 1;
lastMax = curMax;
}
return step;
}
} 再说这道题,将每个炮塔的控制范围按照起始点排序以后,每次遍历list.get(i).start <= end(当前区间终点)的所有区间,取终点最大的那个,进而更新end。注意当某一次的while循环中出现end < list.get(i).start的情况时返回-1(这也就是为什么要按照起点排序,因为后面i+1、i+2……的start会更大),另外当遍历结束后的那个end小于l时也返回-1。代码如下: import java.util.Scanner;
import java.util.*;
public class Main {
public static class Pair{
int start, end;
public Pair(int s, int e){
this.start = s;
this.end = e;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int answer = 0;
int n = sc.nextInt();
int l = sc.nextInt();
List<Pair> list = new ArrayList<Pair>();
for(int i = 0; i < n; i++){
int s = sc.nextInt();
int e = sc.nextInt();
Pair p = new Pair(s, e);
list.add(p);
}
Collections.sort(list, new Comparator<Pair>() {
@Override
public int compare(Pair o1, Pair o2) {
if(o1.start != o2.start){
return o1.start - o2.start;
}else{
return o1.end - o2.end;
}
}
});
if(n == 1){
if(list.get(0).start>0 || list.get(0).end<l){
System.out.println(-1);
}else{
System.out.println(1);
}
}else{
int start = list.get(0).start;
int end = list.get(0).end;
if(start > 0){
System.out.println(-1);
}else{
answer += 1;
int i =1;
while(i < n){
if(end >= l){
System.out.println(answer);
return;
}
if(end < list.get(i).start){
System.out.println(-1);
return;
}
int newEnd = -1;
while(i < n && list.get(i).start <= end){
newEnd = Math.max(list.get(i).end, newEnd);
i += 1;
}
answer += 1;
end = newEnd;
}
if(end < l){
System.out.println(-1);
}else{
System.out.println(answer);
}
}
}
}
}
查看原帖
点赞 评论
相关推荐
不愿透露姓名的神秘牛友
04-25 21:47
已编辑
点赞 评论 收藏
转发
点赞 评论 收藏
转发
牛客热帖
- 1... 想来字节技术实习,看我这篇就够了!——保姆级面经大放送1.9W
- 2... 【0429快问快答】99%牛油的疑惑解答(更新至38个问题1.1W
- 3... 【奖💰】🔩通信硬件人笔面经征集②9736
- 4... 【奖】休息放松or学习提升,五一假期和牛牛一起“充充电”🔋8247
- 5... 0实习经验上岸字节,分享一下过程经验8247
- 6... 毕业8051
- 7... 美团后端日常实习一二面(已oc)6766
- 8... 准备去参加自己的婚礼6552
- 9... 为什么我不建议你学C++后端5535
- 10... 【薪资计算】SS Is All You Need4868
正在热议
# 牛友的五一计划 #
27571次浏览 476人参与
# 市场营销面经 #
1841次浏览 82人参与
# 牛客帮帮团来啦!有问必答 #
421841次浏览 8035人参与
# 许愿池 #
67383次浏览 1489人参与
# 晒一晒我的offer #
2869820次浏览 50251人参与
# 2022届毕业生现状 #
287283次浏览 4119人参与
# 你的秋招进展怎么样了 #
450432次浏览 12983人参与
# 如何看待offer收割机的行为 #
198928次浏览 3038人参与
# 互联网公司评价 #
64109次浏览 911人参与
# 硬件人的春招flag #
14787次浏览 203人参与
# 非技术岗薪资爆料 #
11016次浏览 211人参与
# 实习好累,可以辞职全力准备秋招吗 #
2787次浏览 59人参与
# 产品实习,你更倾向大公司or小公司 #
31706次浏览 499人参与
# 找工作,你会甘心进小厂还是猛冲大厂 #
25739次浏览 258人参与
# 秋招开了,你想投哪些公司呢 #
102624次浏览 3134人参与
# 浅聊一下我实习的辛苦费 #
71804次浏览 655人参与
# 在国企工作的人,躺平了吗? #
74702次浏览 916人参与
# 双非本科求职如何逆袭 #
175811次浏览 2640人参与
# 提前批真的不会影响正式批吗 #
18349次浏览 231人参与
# 实习想申请秋招offer,能不能argue薪资 #
4633次浏览 70人参与