ranges

type Node ¶

type Node struct {
	// contains filtered or unexported fields
}

type RangeModule ¶

type RangeModule struct {
	// contains filtered or unexported fields
}

RangeModule 715. Range 模块 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 仍然会被跟踪）

提示： 1 <= left < right <= 109 在单个测试用例中，对 addRange 、 queryRange 和 removeRange 的调用总数不超过 104 次

func Constructor2() RangeModule

func (this *RangeModule) AddRange(left int, right int)

func (this *RangeModule) QueryRange(left int, right int) bool

func (this *RangeModule) RemoveRange(left int, right int)

type RangeNode ¶

type RangeNode struct {
	// contains filtered or unexported fields
}

type SummaryRanges ¶

type SummaryRanges struct {
	// 红黑树的每个结点的key为每个区间的左端点，value为每个区间的右端点
	*redblacktree.Tree
	// contains filtered or unexported fields
}

SummaryRanges

352. 将数据流变为多个不相交区间 给你一个由非负整数 a1, a2, ..., an 组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。

实现 SummaryRanges 类： SummaryRanges() 使用一个空数据流初始化对象。 void addNum(int val) 向数据流中加入整数 val 。 int[][] getIntervals() 以不相交区间 [starti, endi] 的列表形式返回对数据流中整数的总结。

示例： 输入： ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"] [[], [1], [], [3], [], [7], [], [2], [], [6], []] 输出： [null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]] 解释： SummaryRanges summaryRanges = new SummaryRanges(); summaryRanges.addNum(1); // arr = [1] summaryRanges.getIntervals(); // 返回 [[1, 1]] summaryRanges.addNum(3); // arr = [1, 3] summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]] summaryRanges.addNum(7); // arr = [1, 3, 7] summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]] summaryRanges.addNum(2); // arr = [1, 2, 3, 7] summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]] summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7] summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]

提示： 0 <= val <= 104 最多调用 addNum 和 getIntervals 方法 3 * 104 次

进阶：如果存在大量合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办?

func Constructor() SummaryRanges

func (this *SummaryRanges) AddNum(val int)

func (this *SummaryRanges) GetIntervals() [][]int