【英雄哥六月集训】第 22天: 有序集合

系列文章

文章目录

系列文章
有序集合
一、我的日程安排表 III
二、最大频率栈
三、将数据流变为多个不相交区间
总结

有序集合

首先，集合的有序无序是指在插入的时候，保持插入的顺序性，先插入的放在集合前面，后插入的放在集合后面。
而排序是指插入元素后，集合中的元素是否自动进行排序(例如升序降序)。
实现List接口的，例如ArrayList，LinkedList都是有序的
实现Set接口的，例如HashSet,TreeSet,LinkHashSet等都是无序的，但是TreeSet是基于树排序的。
实现Map接口的，例如HashMap,HashTable,
LinkedHashMap，TreeMap也都是无序的，但是TreeMap是基于树排序的。

一、我的日程安排表 III

732. 我的日程安排表 III

class MyCalendarThree {
    private TreeMap<Integer, Integer> cnt;

    public MyCalendarThree() {
        cnt = new TreeMap<Integer, Integer>();
    }
    
    public int book(int start, int end) {
        int ans = 0;
        int maxBook = 0;
        cnt.put(start, cnt.getOrDefault(start, 0) + 1);
        cnt.put(end, cnt.getOrDefault(end, 0) - 1);
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            maxBook += freq;
            ans = Math.max(maxBook, ans);
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

二、最大频率栈

895. 最大频率栈

class FreqStack {
    Map<Integer, Stack<Integer>> freqStkMap;
    Map<Integer, Integer> numFreqMap;
    int maxFreq;

    public FreqStack() {
        freqStkMap = new HashMap<>();
        numFreqMap = new HashMap<>();
        maxFreq = 0;
    }
    
    public void push(int val) {
        int currFreq = numFreqMap.getOrDefault(val,0)+1;
        numFreqMap.put(val,currFreq);
        if(currFreq>maxFreq){
            maxFreq=currFreq;
        }
        freqStkMap.putIfAbsent(currFreq, new Stack<>());
        freqStkMap.get(currFreq).push(val);

    }
    
    public int pop() {
        int maxFreqNum = freqStkMap.get(maxFreq).pop();
        numFreqMap.put(maxFreqNum, numFreqMap.get(maxFreqNum) - 1);
        if(freqStkMap.get(maxFreq).size() == 0){
            maxFreq--;
        }
        return maxFreqNum;

    }
}

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack obj = new FreqStack();
 * obj.push(val);
 * int param_2 = obj.pop();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

三、将数据流变为多个不相交区间

352. 将数据流变为多个不相交区间

class SummaryRanges {
    TreeMap<Integer,Integer> treeMap;

    public SummaryRanges() {
        treeMap = new TreeMap<>();

    }
    
    public void addNum(int val) {
        Integer l =treeMap.floorKey(val);
        if(l!= null && l<=val && treeMap.get(l)>=val){
            return;
        }
        Integer r =treeMap.ceilingKey(val);
        if(r!=null && r==val+1){
            treeMap.put(val, treeMap.get(r));
            treeMap.remove(r);
        } else {
            treeMap.put(val,val);
        }
        if(l!=null && treeMap.get(l) == val-1){
            treeMap.put(l,treeMap.get(val));
            treeMap.remove(val);
        }

    }
    
    public int[][] getIntervals() {
        int[][] ans = new int[treeMap.size()][2];
        int idx=0;
        for(Map.Entry<Integer,Integer> entry: treeMap.entrySet()){
            ans[idx][0] = entry.getKey();
            ans[idx++][1] = entry.getValue();
        }
        return ans;

    }
}

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(val);
 * int[][] param_2 = obj.getIntervals();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

总结

getOrDefault(Object key, V defaultValue)
意思就是当Map集合中有这个key时，就使用这个key对应的value值，如果没有就使用默认值defaultValue

相关阅读:
【服务器数据恢复】IBM服务器raid5两块硬盘离线数据恢复案例
 LeetCode LCP 50. 宝石补给【模拟】简单
 【iOS】—— 响应者链和事件传递链
 阿里云的99元服务器和腾讯云的88元云服务器选择哪个？怎么选？
java包的介绍
 mybatis详解(全)
经典排序算法
 详细介绍mysql表格id清零的方法
 stm32之30.DMA
【温故而知新】构建高可用Linux服务器（二）
原文地址：https://blog.csdn.net/weixin_39348931/article/details/125461841