Range Module
2024-08-28 22:13:51
2019-09-21 18:54:16
- 715. Range Module
问题描述：
问题求解：
用线段树解决了。
class RangeModule {
Node root;
class Node {
int l;
int r;
int m;
Node left;
Node right;
boolean tracked;
public Node(int l, int r, int m, boolean tracked) {
this.l = l;
this.r = r;
this.m = m;
this.left = null;
this.right = null;
this.tracked = tracked;
}
}
public RangeModule() {
root = new Node(0, (int)1e9, -1, false);
}
public void addRange(int left, int right) {
root = addRange(left, right, root);
}
private Node addRange(int l, int r, Node root) {
if (root.m == -1) {
if (root.tracked) return root;
if (root.l == l && root.r == r) root.tracked = true;
else if (root.l == l) {
root.m = r;
root.left = new Node(l, r, -1, root.tracked);
root.right = new Node(r, root.r, -1, root.tracked);
root.left = addRange(l, r, root.left);
}
else {
root.m = l;
root.left = new Node(root.l, l, -1, root.tracked);
root.right = new Node(l, root.r, -1, root.tracked);
root.right = addRange(l, r, root.right);
}
}
else {
if (r <= root.m) {
root.left = addRange(l, r, root.left);
}
else if (l >= root.m) {
root.right = addRange(l, r, root.right);
}
else {
root.left = addRange(l, root.m, root.left);
root.right = addRange(root.m, r, root.right);
}
}
return root;
}
public boolean queryRange(int left, int right) {
return queryRange(left, right, root);
}
private boolean queryRange(int l, int r, Node root) {
if (root.m == -1) {
return root.tracked;
}
else {
if (r <= root.m) return queryRange(l, r, root.left);
else if (l >= root.m) return queryRange(l, r, root.right);
else return queryRange(l, root.m, root.left) && queryRange(root.m, r, root.right);
}
}
public void removeRange(int left, int right) {
root = removeRange(left, right, root);
}
private Node removeRange(int l, int r, Node root) {
if (root.m == -1) {
if (!root.tracked) return root;
if (root.l == l && root.r == r) {
root.tracked = false;
}
else if (root.l == l) {
root.m = r;
root.left = new Node(l, root.m, -1, root.tracked);
root.right = new Node(root.m, root.r, -1, root.tracked);
root.left =removeRange(l, r, root.left);
}
else {
root.m = l;
root.left = new Node(root.l, root.m, -1, root.tracked);
root.right = new Node(root.m, root.r, -1, root.tracked);
root.right = removeRange(l, r, root.right);
}
}
else {
if (r <= root.m) root.left = removeRange(l, r, root.left);
else if (l >= root.m) root.right = removeRange(l, r, root.right);
else {
root.left = removeRange(l, root.m, root.left);
root.right = removeRange(root.m, r, root.right);
}
}
return root;
}
}
/**
* Your RangeModule object will be instantiated and called as such:
* RangeModule obj = new RangeModule();
* obj.addRange(left,right);
* boolean param_2 = obj.queryRange(left,right);
* obj.removeRange(left,right);
*/
最新文章
- 微软“.Net社区虚拟大会”dotnetConf2015 第二天 无处不在的Xamarin
- Java（Helloworld.java）
- DBlink与同义词
- hiho #1361 Playfair密码表
- zju(5)LED控制实验
- ThreadPool原理介绍
- Netsharp快速入门(之7) 基础档案(工作区1 向导创建工作区)
- SQL语言简介
- 设计模式之适配器模式(Decorator)
- kafka监控项目大全
- important的妙用解决firefox和ie的css兼容问题
- 网络安装Centos x64 6.10
- PHP7 网络编程（二）daemon守护进程
- java集合之List。
- yum安装命令：遇到的问题报错如下： File "/usr/bin/yum", line 30 except KeyboardInterrupt, e: 通过看报错可以了解到是使用了python2的语法，所以了解到当前yum使用的Python2，因为我单独安装了python3，且python3设置为默认版本了，所以导致语法问题 解决方法： 使用python2.6 yum install
- Batch Normalization--介绍
- Lessons Learned from Developing a Data Product
- [转]Javascript原型继承
- iOS-----使用CoreLocation定位
- forbidden