715. Range 模块

作者: 刘翊扬 | 来源:发表于2022-06-20 23:23 被阅读0次

    Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。

    半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。

    实现 RangeModule 类:

    RangeModule() 初始化数据结构的对象。
    void addRange(int left, int right) 添加 半开区间 [left, right),跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时,应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
    boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时,才返回 true ,否则返回 false 。
    void removeRange(int left, int right) 停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。

    示例 1:

    输入
    ["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
    [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
    输出
    [null, null, null, true, false, true]
    
    解释
    RangeModule rangeModule = new RangeModule();
    rangeModule.addRange(10, 20);
    rangeModule.removeRange(14, 16);
    rangeModule.queryRange(10, 14); 返回 true (区间 [10, 14) 中的每个数都正在被跟踪)
    rangeModule.queryRange(13, 15); 返回 false(未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字)
    rangeModule.queryRange(16, 17); 返回 true (尽管执行了删除操作,区间 [16, 17) 中的数字 16 仍然会被跟踪)
    

    准备,需要了解的知识

    /**
       * 了解下treeMap的用法
         * @param args
         */
     public static void main(String[] args) {
            // creating object of TreeMap<Integer, String>
            TreeMap<Integer, String>
                    treemap = new TreeMap<Integer, String>();
    
            // populating tree map
            treemap.put(1, "One");
            treemap.put(2, "Two");
            treemap.put(3, "Three");
            treemap.put(4, "Four");
            treemap.put(5, "Five");
    
            Map.Entry<Integer, String> higherEntry = treemap.higherEntry(3);
            System.out.println("higherEntry => " + higherEntry); // higherEntry => 4=Four
    
            Map.Entry<Integer, String> lowerEntry = treemap.lowerEntry(3);
            System.out.println("lowerEntry => " + lowerEntry); // lowerEntry => 2=Two
    
            Map.Entry<Integer, String> lastEntry = treemap.lastEntry();
            System.out.println("lastEntry => " + lastEntry); // lastEntry => 5=Five
        }
    

    方法一:有序集合 / 有序映射

    class RangeModule {
        TreeMap<Integer, Integer> intervals;
    
        public RangeModule() {
            intervals = new TreeMap<Integer, Integer>();
        }
    
        public void addRange(int left, int right) {
            Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
            if (entry != intervals.firstEntry()) {
                Map.Entry<Integer, Integer> start = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
                if (start != null && start.getValue() >= right) {
                    return;
                }
                if (start != null && start.getValue() >= left) {
                    left = start.getKey();
                    intervals.remove(start.getKey());
                }
            }
            while (entry != null && entry.getKey() <= right) {
                right = Math.max(right, entry.getValue());
                intervals.remove(entry.getKey());
                entry = intervals.higherEntry(entry.getKey());
            }
            intervals.put(left, right);
        }
    
        public boolean queryRange(int left, int right) {
            Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
            if (entry == intervals.firstEntry()) {
                return false;
            }
            entry = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
            return entry != null && right <= entry.getValue();
        }
    
        public void removeRange(int left, int right) {
            Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
            if (entry != intervals.firstEntry()) {
                Map.Entry<Integer, Integer> start = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
                if (start != null && start.getValue() >= right) {
                    int ri = start.getValue();
                    if (start.getKey() == left) {
                        intervals.remove(start.getKey());
                    } else {
                        intervals.put(start.getKey(), left);
                    }
                    if (right != ri) {
                        intervals.put(right, ri);
                    }
                    return;
                } else if (start != null && start.getValue() > left) {
                    intervals.put(start.getKey(), left);
                }
            }
            while (entry != null && entry.getKey() < right) {
                if (entry.getValue() <= right) {
                    intervals.remove(entry.getKey());
                    entry = intervals.higherEntry(entry.getKey());
                } else {
                    intervals.put(right, entry.getValue());
                    intervals.remove(entry.getKey());
                    break;
                }
            }
        }
    }
    
    

    作者:LeetCode-Solution
    链接:https://leetcode.cn/problems/range-module/solution/range-mo-kuai-by-leetcode-solution-4utf/
    来源:力扣(LeetCode)
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    相关文章

      网友评论

        本文标题:715. Range 模块

        本文链接:https://www.haomeiwen.com/subject/drlrmrtx.html