选择题
1.知道树的中序和后序 求前序
忘得差不多了，反正不难，就是分值大，5分一道
编程题
1.汽车载客trips = {{2,1,4}{4,2,6}}，capacity = 5 输出 = 2
trips[i][0]是乘客数量，trips[i][1]是上车地点，trips[i][2]是下车地点。capacity是车的最大容量，求最少需要多少车？
按照上车时间从小到大排序。创建一个优先队列，按照最早的下车时间进队的，看上车的人数是不是超过capacity，超过就count++。AC!
public int minCarCount (int[][] trips, int capacity){
Arrays.sort(trips, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
int count = 1;
PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) {
return o1[2] - o2[2];
}
});
int sum = 0;
for (int i = 0; i < trips.length; i++) {
boolean flag = true;
while(q.size() > 0 && flag){
int[] t = q.peek();
if(trips[i][1] >= t[2]){
int[] temp = q.poll();
sum -= temp[0];
}
else flag = false;
}
q.add(trips[i]);
sum += trips[i][0];
if(sum > capacity){
count++;
}
}
return count;
}
2.打怪，level = 1，level表示初始层级，x = 2,x表示需要做的任务数， tasks={{0,1},{1,2},{1,3}} 只有level>=tasks[i][0]，level才能+=tasks[i][1]，求level最大是多少？
没做完。感觉也是用贪心来做。
全部评论
(1) 回帖