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

fireflowers

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

第一次刷题经验帖，表达能力比较差，求各位看官请拍。觉得有用的话，顺便求米~~~
第一题：LC1094:car-pooling
https://leetcode.com/problems/car-pooling/
给定一个数据trips，trips[0] , trips[1], trips[2]分表代表上车地点，下车地点和人数，要求返回汽车是否可以一趟运输完所有的乘客。我们可以模拟汽车的行驶过程，记录每一个上车以及下车地点车上的人数，最后判断每个上下车点人数是否超过capacity。由于上下车地点是排序的，可以使用treeMap这种数据结构，代码如下：

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人，返回车上最多一共出现过多少人。代码如下：

[hide=20]

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代码如下
[code]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可以：
代码如下：

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]);
}

复制代码

第七题：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]
给出起止航班号以及订阅数量，返回每个航班的订阅数量：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;

}
复制代码

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

public int[] corpFlightBookings3(int[][] bookings, int n) {

      int[] res = new int[n];

      for (int[] booking : bookings){

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

         if (booking[1]<n){

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

         }

      }

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

         res[i] += res[i-1];

      }

      return res;

}
复制代码

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

[/i]

heronalps

这个模版的本质，还是start和end两个位置的频率统计，然后遍历结果以求得capacity / merge / verify。如果需要遍历的元素数量上限确定的话，可以用数组来代替treemap。

比如Car Pooling

public boolean carPooling(int[][] trips, int capacity) {
int stops[] = new int[1001];
for (int[] t : trips) {
stops[t[1]] += t[0];
stops[t[2]] -= t[0];
}
for (int i = 0; i < stops.length; i++) {
capacity -= stops[i];
if (capacity < 0) return false;
}
return true;
}

复制代码

TreeMap的优势在于Flexible Length, 以及floorKey等接口，可以避免如1109题中的Corner case. 缺点在于每一个操作都是O(Log(n)), 很多情况下与数组相比TC会处于劣势。

很棒，感谢分享！

vivflynn

zea7ot 发表于 2020-08-24 18:10:35
我不太清楚你这里说的"这个"具体是指什么。

如果是使用楼主本帖描述的扫描线(Sweep Line)算法，那TreeMap几乎是是必须的。如果不是必须的，我个人也是强烈推荐的。

嗯嗯我觉得你对扫描线算法的理解是对的但是就对这两题而言我们扫描过程不是由这个map决定的而是由那个for 循环你看代码只有读值和插入对吧其实这题的本质就是start 和 end 的频率统计所以其实不需要treemap

diamondsky

本帖最后由 diamondsky 于 2020-1-22 13:18 编辑

非常棒！

> 56 merge intervals 如果遇到follow-up,比如intervals是stream形式给出的，排序的解法就处理不了。但是treeMap可以
排序也可以解，也非常清晰，就是57. Insert Interval，代码如下：

class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> list = new ArrayList<>();
// corner case
if ((intervals == null || intervals.length == 0)
&& (newInterval == null || newInterval.length == 0)) return new int[][]{};
int i = 0;
int n = intervals.length;
int start = newInterval[0];
int end = newInterval[1];
// case 1: no overlap
// intervals : |_____|
// [start, end] : |______|
//
while (i < n && intervals[1] < start) {
list.add(intervals);
i++;
}
// case 2: overlap
// intervals : |_____| |___|
// [start, end] : |______|
//
while (i < n && intervals[0] <= end) {
start = Math.min(start, intervals[0]);
end = Math.max(end, intervals[1]);
i++;
}
list.add(new int[]{start, end});
// case 3: no overlap
// intervals : |_____|
// [start, end] : |______|
//
while (i < n) {
list.add(intervals);
i++;
}
return list.toArray(new int[0][]);
}
}

复制代码

scope

为什么不用HashMap用TreeMap呢？

diamondsky

仔细看了这个帖子的话，interval相关的所有问题都能解了! 非常感谢楼主！

jliu

一直有疑问，如果刷题用python，然后发现题目要用到tree map 怎么办

Wu_kong

话说java 有tree map, 但是python 需要先自己实现一下

gwy

scope 发表于 2020-1-21 23:53
为什么不用HashMap用TreeMap呢？

TreeMap 有排序

heronalps

diamondsky 发表于 2020-1-22 00:15
非常棒！

> 56 merge intervals 如果遇到follow-up,比如intervals是stream形式给出的，排序的解法就处理 ...

57的默认条件是Interval 数组已经排好序，而56并没有这个条件。但interval以数据流形式出现，每一步interval insert之后，整体数组保持有序。

感谢分享！

dreamy

本帖最后由 dreamy 于 2020-1-24 16:27 编辑

这个帖子总结的很好，和leetcode上的这个discussion异曲同工。https://leetcode.com/problems/me ... -Scheduling-Problem
759. Employee Free Time 也可以用这个模板，和merge interval思路相同。merge interval求的是时间戳上所有被占据的区间，而759求得是时间戳上没有被占据的间隙。

class Solution {
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
List<Interval> res = new ArrayList<>();
if (schedule == null || schedule.size() == 0) return res;
TreeMap<Integer, Integer> calendar = new TreeMap<>();
for (List<Interval> list : schedule) {
if (list == null || list.size() == 0) continue;
for (Interval i : list) {
calendar.put(i.start, calendar.getOrDefault(i.start, 0) + 1);
calendar.put(i.end, calendar.getOrDefault(i.end, 0) - 1);
}
}
int count = 0;
int start = -1;
for (Map.Entry<Integer, Integer> entry : calendar.entrySet()) {
count += entry.getValue();
if (count == 0) start = entry.getKey();
if (count > 0 && start != -1) {
res.add(new Interval(start, entry.getKey()));
start = -1;
}
}
return res;
}
}

复制代码

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

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

评分

评分

浏览过的版块