推广网站弄哪家好,优秀网站设计作品分析,百度seo搜索引擎优化厂家,wordpress表格不显示目录 2276. 统计区间中的整数数目
题目描述#xff1a;
实现代码与解析#xff1a;
TreeMap
原理思路#xff1a; 2276. 统计区间中的整数数目
题目描述#xff1a;
给你区间的 空 集#xff0c;请你设计并实现满足要求的数据结构#xff1a;
新增#xff1a;添加…目录 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 {TreeMapInteger, Integer map new TreeMap(); // 按左端点排序int cnt 0;public CountIntervals() {}public void add(int left, int right) {Map.EntryInteger, 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刷题还有点不习惯好多方法也不太知道。
