登录
  • #刷题
  • #leetcode

一个模板刷N题-treeMap解区间题

fireflowers
4928
18
第一次刷题经验帖,表达能力比较差,求各位看官请拍。觉得有用的话,顺便求米~~~

第一题:LC1094:car-pooling

leetcode.com

给定一个数据trips,trips[0] , trips[1], trips[2]分表代表上车地点,下车地点和人数,要求返回汽车是否可以一趟运输完所有的乘客。我们可以模拟汽车的行驶过程,记录每一个上车以及下车地点车上的人数,最后判断每个上下车点人数是否超过capacity。由于上下车地点是排序的,可以使用treeMap这种数据结构,代码如下:

[mw_shl_code=java,true]TreeMap<Integer, Integer> map = new TreeMap();

for (int[] trip : trips) {[br]
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;

}

[/mw_shl_code]

第二题:LC253:meeting-room-ii

leetcode.com

给定一个会议区间列表,返回需要的会议室数量。

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]

Output: 2

和上一题其实很类似,上一题是给定区间trip,trip[2]代表权重。这一题meeting只有两个值,其实最有一个值是默认值1。Meeting[0], meeting[1]代表上下车地点,最有一个值表示每个地点上车1人,返回车上最多一共出现过多少人。代码如下:

本帖隐藏的内容需要论坛积分高于188才可浏览
点击前往一亩三分地论坛查看 >>


第三、四、五题:my-calendar i, ii, iii

leetcode.com, 日程不能有冲突

leetcode.com, 日程最多只有一次冲突

leetcode.com, 返回日程最多出现过几次冲突

类似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;

}

[/mw_shl_code]

第六题:LC56. Merge Intervals

leetcode.com

合并区间,一般做法是先排序再合并。如果遇到follow-up,比如intervals是stream形式给出的,排序的解法就处理不了。但是treeMap可以:

代码如下:

[mw_shl_code=java,true]public int[][] merge(int[][] intervals) {

if (intervals.length == 0) return new int[0][0];

List<int[]> list = new ArrayList<>();[br]
TreeMap<Integer, Integer> map = new TreeMap<>();

for(int[] itv : intervals){//添加区间节点的过程[br]
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});[br]
start = Integer.MAX_VALUE;

end = Integer.MIN_VALUE;

}

}

return list.toArray(new int[list.size()][2]);

}

[/mw_shl_code]

第七题:LC1109. Corporate Flight Bookings

leetcode.com

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5

Output: [10,55,45,25,25]

给出起止航班号以及订阅数量,返回每个航班的订阅数量:[mw_shl_code=java,true]public int[] corpFlightBookings(int[][] bookings, int n) {[br]
int[] res = new int[n];

TreeMap<Integer, Integer> map = new TreeMap<>();

for (int[] booking : bookings){[br]
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;

}[/mw_shl_code]

由于给出的航班数是有限值n,可以使用counting sort代替treeMap进行排序,代码如下:

[mw_shl_code=java,true]public int[] corpFlightBookings3(int[][] bookings, int n) {[br]
int[] res = new int[n];

for (int[] booking : bookings){[br]
res[booking[0]-1] += booking[2];

if (booking[1]<n){

res[booking[1]] -= booking[2];

}

}

for (int i=1;i<n;i++){

res += res[i-1];

}

return res;

}[/mw_shl_code]

如果上面几题给的区间开始和截止点都比较小的话,也都可以使用数据代替treeMap进行排序。



18条回复
热度排序

发表回复