LeetCode:2276. 统计区间中的整数数目(TreeMap Java)

2023-12-16 22:35:44

目录

2276. 统计区间中的整数数目

题目描述:

实现代码与解析:

TreeMap

原理思路:


2276. 统计区间中的整数数目

题目描述:

给你区间的??集,请你设计并实现满足要求的数据结构:

  • 新增:添加一个区间到这个区间集合中。
  • 统计:计算出现在?至少一个?区间中的整数个数。

实现?CountIntervals?类:

  • CountIntervals()?使用区间的空集初始化对象
  • void add(int left, int right)?添加区间?[left, right]?到区间集合之中。
  • int count()?返回出现在?至少一个?区间中的整数个数。

注意:区间?[left, right]?表示满足?left <= x <= right?的所有整数?x?。

示例 1:

输入
["CountIntervals", "add", "add", "count", "add", "count"]
[[], [2, 3], [7, 10], [], [5, 8], []]
输出
[null, null, null, 6, null, 8]

解释
CountIntervals countIntervals = new CountIntervals(); // 用一个区间空集初始化对象
countIntervals.add(2, 3);  // 将 [2, 3] 添加到区间集合中
countIntervals.add(7, 10); // 将 [7, 10] 添加到区间集合中
countIntervals.count();    // 返回 6
                           // 整数 2 和 3 出现在区间 [2, 3] 中
                           // 整数 7、8、9、10 出现在区间 [7, 10] 中
countIntervals.add(5, 8);  // 将 [5, 8] 添加到区间集合中
countIntervals.count();    // 返回 8
                           // 整数 2 和 3 出现在区间 [2, 3] 中
                           // 整数 5 和 6 出现在区间 [5, 8] 中
                           // 整数 7 和 8 出现在区间 [5, 8] 和区间 [7, 10] 中
                           // 整数 9 和 10 出现在区间 [7, 10] 中

提示:

  • 1 <= left <= right <= 109
  • 最多调用??add?和?count?方法?总计?105?次
  • 调用?count?方法至少一次

实现代码与解析:

TreeMap

class CountIntervals {

    TreeMap<Integer, Integer> map = new TreeMap<>(); // 按左端点排序
    int cnt = 0;

    public CountIntervals() {

    }
    
    public void add(int left, int right) {
        Map.Entry<Integer, Integer> it = map.floorEntry(right); // 小于等于right的最大键值对
        while (it != null && it.getValue() >= left) { // 有重合,合并区间
            int l = it.getKey(), r= it.getValue();
            left = Math.min(left, l); 
            right = Math.max(right, r);
            cnt -= r - l + 1; // 这区间的点暂时都去掉
            map.remove(l);
            it = map.floorEntry(right); // 再看是否重合,合并
        }
        // 跳出循环,说明没重合的了
        cnt += right - left + 1; // 把合并好的区间的整数再加回来  
        map.put(left, right); // 把最终合并好的放入map中

    }
    
    public int count() {
        return cnt;
    }
}

原理思路:

? ? ? ? map中存放区间,用左端点排序,没加入一个区间,就看是否有重复,循环合并区间,再计算区间中的数即可。

? ? ? ? 主要是学习TreeMap中的这些方法。

最近刚从C++改成用java刷题,还有点不习惯,好多方法也不太知道。?

文章来源:https://blog.csdn.net/Cosmoshhhyyy/article/details/135038181
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。