客观题都是比较常规的就不写了，第三道编程题题干太长了可能得有个300字，就压根没看，只做了1，2两道，第二道调了一个小时还是0ac，第一道就剩十分钟去写了，只有25%ac，计算复杂度太大。把我的代码和题目思路都分享一下吧（分享个p...你那破思路还配分享），希望有大佬可以指出一下为什么我的第二题一直0ac，以及第一道该怎么降复杂度。
1.小明上课，由于课程太多，不得不在冲突的时间段一心多用，已知报了N节课，S和E为每节课的起止时间均为整数，求最少需要一心几
由于只有十分钟了，我也想不出什么思路了，就先按起始时间大小排序，然后以每个课程的起始时间+0.5为标准去遍历每一个课程的起始时间，当有起始时间大于的时候就跳出。由于都是整数，即使他们交错了但是起始时间更长不在本次统计当中，也会在下一次统计当中记录，所以最后复杂度是O(N^2)。考完之后立刻又想到，也许滑动窗口可以减少复杂度，遍历一次就行，就是窗口起始为第一个课程的起始时间，终止为其终止时间，然后在课程表中计算大小。之后滑动切换到下一个课程直到到底，但没时间实现了。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
List<List<Integer>> lesson=new ArrayList<List<Integer>>();
for(int i=0;i<N;i++) {
List<Integer> list=new ArrayList<Integer>();
list.add(sc.nextInt());
list.add(sc.nextInt());
lesson.add(new ArrayList<Integer>(list));
}
System.out.println(LessHeart(lesson,N));
}
public static int LessHeart(List<List<Integer>> lesson,int N) {
Comparator<List<Integer>> comparator=new Comparator<List<Integer>>() { @Override public int compare(List<Integer> o1, List<Integer> o2) {
if(o1.get(0)!=o2.get(0))
return o1.get(0)-o2.get(0);
return o1.get(1)-o2.get(1);
}
};
Collections.sort(lesson,comparator);
int start=lesson.get(0).get(0);
int end=lesson.get(N-1).get(1);
int max=0;
for(int i=0;i<N;i++){
double a=lesson.get(0).get(0)+0.5;
int count=0;
for(List<Integer> list:lesson){
if(list.get(0)<a&&list.get(1)>a){
count++;
}
if(list.get(0)>a){
break;
}
}
max=Math.max(max,count);
}
return max;
}
} 2.幼儿园分发奖励券，规则是A先拿到选一个分给其他人，以此类推。最后每个人的奖励是自己的收益加上一部分从你手中分出去的其他人的收益，收益可能为负，但是不选其中一人，则从他手中分出去的券的就无法选择。举例来说是A把BCD券给B，B把CD券给CD，最后A可选的是A，ABCD，AB，ABC，ABD，但是不可选AC或AD。你可以知道的是每个人手里奖励券的大小和来源，最后返回最大收益。第一行是N，表示人数 第2到N+1行是A和B，A是收益，B表示来源（B=0表示他是起始，不然表示他是从第几行的人的手中拿到的，就是B=2的话，就代表他是从第一个人手中拿到的），最后数可能会很大要模1000000003我就是简单的递归思想，每个人能拿到的最大收益肯定是他分出去券的那些人的最大非负收益的和，所以我就认为递归就好了，谁想到15分钟写完了0ac，找了50分钟的错和编案例还是0ac，就放弃了转身去算第一题了。因为我本来以为第一题会是那种求最小个数遍历整个地图的那种想放一下，结果.....
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
List<Integer> gain=new ArrayList<Integer>();
List<Integer> Max=new ArrayList<Integer>();
Map<Integer,List<Integer>> map=new HashMap<Integer, List<Integer>>();
for(int i=0;i<N;i++) {
gain.add(sc.nextInt());
int x=sc.nextInt();
if(x==0){
continue;
}
x-=2;
if(map.containsKey(x)){
List list=map.get(x);
list.add(i);
map.put(x,new ArrayList<Integer>(list));
}else{
List<Integer> list=new ArrayList<Integer>();
list.add(i);
map.put(x,new ArrayList<Integer>(list));
}
}
int max=0;
MaxGain(N,gain,map,0,Max);
for(int i:Max){
max=Math.max(i,max);
}
System.out.print(max);
}
public static int MaxGain(int N,List<Integer> gain, Map<Integer,List<Integer>> map,int start,List<Integer> Max){
if(N==0){
Max.add(0);
return 0;
}
if(map.containsKey(start)) {
List<Integer> list = map.get(start);
int max = 0;
for (int i : list) {
int count = MaxGain(N,gain, map, i,Max);
//System.out.println("start="+start+"count="+count);
if (count > 0) {
max =(max+ count)%1000000003;
}
}
max=(max+gain.get(start))%1000000003;
Max.add(max);
return max;
}else{
Max.add((Math.max(0,gain.get(start)))%1000000003);
return Math.max(0,gain.get(start))%1000000003;
}
}
} 连着两天笔试爆零真的不想继续了，实在不是吃这碗饭的料。最后求问各位大佬，第二题错在哪了可以指教一下吗，跪谢大家
我突然想到一个可能，第一个案例是只有一个奖励，还是个负数，这样的话按照我的解法返回的应该是0，但实际上应该是这个负数....因为只有一个A的情况下必须选择A，不能不兑换。
我突然想到一个可能，第一个案例是只有一个奖励，还是个负数，这样的话按照我的解法返回的应该是0，但实际上应该是这个负数....因为只有一个A的情况下必须选择A，不能不兑换。
好了，我想到了，抽自己1000000000个大嘴巴。传递max的时候还应该每次都max(0,本身)，而我写的.....只有在叶子结点判断了，无数草泥马踏遍我的大脑......什么脑子这是，半天看不出来
全部评论
(2) 回帖