注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
第一次刷题经验帖,表达能力比较差,求各位看官请拍。觉得有用的话,顺便求米~~~
第一题:LC1094:car-pooling
https://leetcode.com/problems/car-pooling/
给定一个数据trips,trips[0] , trips[1], trips[2]分表代表上车地点,下车地点和人数,要求返回汽车是否可以一趟运输完所有的乘客。我们可以模拟汽车的行驶过程,记录每一个上车以及下车地点车上的人数,最后判断每个上下车点人数是否超过capacity。由于上下车地点是排序的,可以使用treeMap这种数据结构,代码如下:
[Java] 纯文本查看 复制代码 TreeMap<Integer, Integer> map = new TreeMap();
for (int[] trip : trips) {
map.put(trip[1], map.getOrDefault(trip[1], 0) + trip[0]);
map.put(trip[2], map.getOrDefault(trip[2], 0) - trip[0]);
}
int persons = 0;
for (int k : map.keySet()) {
persons += map.get(k);
if(persons > capacity) return false;
}
return true;
}
第二题:LC253:meeting-room-ii
https://leetcode.com/problems/meeting-rooms-ii/
给定一个会议区间列表,返回需要的会议室数量。
Example 1:
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
和上一题其实很类似,上一题是给定区间trip,trip[2]代表权重。这一题meeting只有两个值,其实最有一个值是默认值1。Meeting[0], meeting[1]代表上下车地点,最有一个值表示每个地点上车1人,返回车上最多一共出现过多少人。代码如下:
第三、四、五题:my-calendar i, ii, iii
https://leetcode.com/problems/my-calendar-i/, 日程不能有冲突
https://leetcode.com/problems/my-calendar-ii/, 日程最多只有一次冲突
https://leetcode.com/problems/my-calendar-iii/, 返回日程最多出现过几次冲突
类似meeting-room-ii,出现最多冲突的日程次数即上一题中,最多需要的会议室:
my-calendar-iii代码如下
[mw_shl_code=java,true]TreeMap<Integer, Integer> map;
public MyCalendar() {
map = new TreeMap();
}
public int book(int start, int end) {
int res = 0, count = 0;
map.put(start, map.getOrDefault(start, 0)+1);
map.put(end, map.getOrDefault(end, 0)-1);
for(int v : map.values()){
count+=v;
res = Math.max(res, count);
}
return res;
}
my-calendar-ii代码:
public boolean book(int start, int end) {
int count = 0;
map.put(start, map.getOrDefault(start, 0)+1);
map.put(end, map.getOrDefault(end, 0)-1);
boolean canBook = true;
for(int v : map.values()){
count+=v;
if(count>2){//最多出现冲突日程不能大于2
canBook = false;
break;
}
}
if(!canBook){
map.put(start, map.get(start)-1);
map.put(end, map.get(end)+1);
}
return canBook;
}
第六题:LC56. Merge Intervals
https://leetcode.com/problems/merge-intervals/
合并区间,一般做法是先排序再合并。如果遇到follow-up,比如intervals是stream形式给出的,排序的解法就处理不了。但是treeMap可以:
代码如下:
[Java] 纯文本查看 复制代码 public int minMeetingRooms(int[][] intervals) {
TreeMap<Integer, Integer> map = new TreeMap();
for (int[] itv : intervals) {
map.put(itv[0], map.getOrDefault(itv[0], 0)+1);
map.put(itv[1], map.getOrDefault(itv[1], 0)-1);
}
int res = 0, count = 0;
for (int v : map.values()) {
count += v;
res = Math.max(res, count);
}
return res;
}[/hide]
第三、四、五题:my-calendar i, ii, iii
[url=https://leetcode.com/problems/my-calendar-i/]https://leetcode.com/problems/my-calendar-i/[/url], 日程不能有冲突
[url=https://leetcode.com/problems/my-calendar-ii/]https://leetcode.com/problems/my-calendar-ii/[/url], 日程最多只有一次冲突
[url=https://leetcode.com/problems/my-calendar-iii/]https://leetcode.com/problems/my-calendar-iii/[/url], 返回日程最多出现过几次冲突
类似meeting-room-ii,出现最多冲突的日程次数即上一题中,最多需要的会议室:
my-calendar-iii代码如下
[mw_shl_code=java,true]TreeMap<Integer, Integer> map;
public MyCalendar() {
map = new TreeMap();
}
public int book(int start, int end) {
int res = 0, count = 0;
map.put(start, map.getOrDefault(start, 0)+1);
map.put(end, map.getOrDefault(end, 0)-1);
for(int v : map.values()){
count+=v;
res = Math.max(res, count);
}
return res;
}
my-calendar-ii代码:
public boolean book(int start, int end) {
int count = 0;
map.put(start, map.getOrDefault(start, 0)+1);
map.put(end, map.getOrDefault(end, 0)-1);
boolean canBook = true;
for(int v : map.values()){
count+=v;
if(count>2){//最多出现冲突日程不能大于2
canBook = false;
break;
}
}
if(!canBook){
map.put(start, map.get(start)-1);
map.put(end, map.get(end)+1);
}
return canBook;
}
第七题:LC1109. Corporate Flight bookings
https://leetcode.com/problems/corporate-flight-bookings/
Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]
给出起止航班号以及订阅数量,返回每个航班的订阅数量:[Java] 纯文本查看 复制代码 public int[][] merge(int[][] intervals) {
if (intervals.length == 0) return new int[0][0];
List<int[]> list = new ArrayList<>();
TreeMap<Integer, Integer> map = new TreeMap<>();
for(int[] itv : intervals){//添加区间节点的过程
map.put(itv[0], map.getOrDefault(itv[0], 0)+1);
map.put(itv[1], map.getOrDefault(itv[1], 0)-1);
}
int count = 0, start = Integer.MAX_VALUE, end = Integer.MIN_VALUE;
for (int k : map.keySet()){
count+=map.get(k);
start = Math.min(start, k);
end = Math.max(end, k);
if (count==0){//关键:count==0代表区间闭合了,需要把刚刚闭合的区间添加到结果集中。可以类比字符串中左右括号的情况,遇到左括号+1,右括号-1。当count==0时,区间的括号是完全匹配的。
list.add(new int[]{start, end});
start = Integer.MAX_VALUE;
end = Integer.MIN_VALUE;
}
}
return list.toArray(new int[list.size()][2]);
}
由于给出的航班数是有限值n,可以使用counting sort代替treeMap进行排序,代码如下:
[Java] 纯文本查看 复制代码 public int[] corpFlightBookings(int[][] bookings, int n) {
int[] res = new int[n];
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int[] booking : bookings){
map.put(booking[0], map.getOrDefault(booking[0], 0)+booking[2]);
map.put(booking[1]+1, map.getOrDefault(booking[1]+1, 0)-booking[2]);
}
int prev = 0;
for (int k : map.keySet()){
map.put(k, map.get(k)+prev);
prev = map.get(k);
}
for (int i=1;i<=n;i++){
Integer booking = map.floorKey(i);
if (booking!=null){
res[i-1] = map.get(booking);
}
}
return res;
}
如果上面几题给的区间开始和截止点都比较小的话,也都可以使用数据代替treeMap进行排序。
|