一亩三分地

 找回密码 注册账号

扫描二维码登录本站


北美版丁香园
美国和加拿大
疫情地图实时动态追踪

热门职场讲座
Career in Tech
职场晋升之路

Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 2677|回复: 13
收起左侧

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

  [复制链接] |试试Instant~ |leetcode, 刷题
我的人缘0

分享帖子到朋友圈
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   100% (23)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

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

游客,本帖隐藏的内容需要积分高于 20 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

第三、四、五题: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进行排序。



评分

参与人数 19大米 +122 收起 理由
jxlxt + 2 给你点个赞!
pxu + 3 给你点个赞!
-_- + 2 给你点个赞!
ran5515 + 1 欢迎分享你知道的情况,会给更多积分奖励!
wolf452 + 2 很有用的信息!
14417335 + 20
417601858 + 2 给你点个赞!
夏虫何以语冰X + 2 很有用的信息!
whdawn + 10
racoona + 2 很有用的信息!

查看全部评分


上一篇:刷多少hard/多快做完hard才算准备充分?
下一篇:【路过加米】纯小白打算开始刷leetcode,请教是先去看什么书/课程么?求指路
我的人缘0
heronalps 2020-1-24 03:04:28 | 显示全部楼层
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   99% (115)
 
 
0% (1)    👎
这个模版的本质,还是start和end两个位置的频率统计,然后遍历结果以求得capacity / merge / verify。如果需要遍历的元素数量上限确定的话,可以用数组来代替treemap。

比如Car Pooling

[Java] 纯文本查看 复制代码
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会处于劣势。

很棒,感谢分享!
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   85% (6)
 
 
14% (1)    👎
为什么不用HashMap用TreeMap呢?

评分

参与人数 1大米 +2 收起 理由
dennyzhang007 + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
diamondsky 2020-1-22 13:15:28 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (54)
 
 
0% (0)    👎
本帖最后由 diamondsky 于 2020-1-22 13:18 编辑

非常棒!

> 56 merge intervals 如果遇到follow-up,比如intervals是stream形式给出的,排序的解法就处理不了。但是treeMap可以
排序也可以解,也非常清晰,就是57. Insert Interval, 代码如下:
[Java] 纯文本查看 复制代码
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][]);
    }
}

评分

参与人数 1大米 +16 收起 理由
Warald + 16

查看全部评分

回复

使用道具 举报

我的人缘0
diamondsky 2020-1-22 14:56:24 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (54)
 
 
0% (0)    👎
仔细看了这个帖子的话,interval相关的所有问题都能解了! 非常感谢楼主!
回复

使用道具 举报

我的人缘0
jliu 2020-1-23 00:17:52 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (106)
 
 
4% (5)    👎
一直有疑问,如果刷题用python, 然后发现题目要用到tree map 怎么办
回复

使用道具 举报

我的人缘0
Wu_kong 2020-1-23 13:32:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (526)
 
 
4% (25)    👎
话说java 有tree map, 但是python 需要先自己实现一下
回复

使用道具 举报

我的人缘0
gwy 2020-1-24 02:31:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
scope 发表于 2020-1-21 23:53
为什么不用HashMap用TreeMap呢?

TreeMap 有排序
回复

使用道具 举报

我的人缘0
heronalps 2020-1-24 02:54:12 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (115)
 
 
0% (1)    👎
diamondsky 发表于 2020-1-22 00:15
非常棒!

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

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

感谢分享!
回复

使用道具 举报

我的人缘0
dreamy 2020-1-24 16:20:47 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (54)
 
 
1% (1)    👎
本帖最后由 dreamy 于 2020-1-24 16:27 编辑

这个帖子总结的很好,和leetcode上的这个discussion异曲同工。https://leetcode.com/problems/me ... -Scheduling-Problem
759. Employee Free Time 也可以用这个模板,和merge interval思路相同。merge interval求的是时间戳上所有被占据的区间,而759求得是时间戳上没有被占据的间隙。
[Java] 纯文本查看 复制代码
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;
    }
}


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-2-19 23:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表