当前位置:网站首页>729. 我的日程安排表 I :「模拟」&「线段树(动态开点)」&「分块 + 位运算(分桶)」
729. 我的日程安排表 I :「模拟」&「线段树(动态开点)」&「分块 + 位运算(分桶)」
2022-07-05 14:31:00 【宫水三叶的刷题日记】
题目描述
这是 LeetCode 上的 729. 我的日程安排表 I ,难度为 中等。
Tag : 「模拟」、「红黑树」、「线段树(动态开点)」、「线段树」、「分块」、「位运算」、「哈希表」
实现一个 MyCalendar
类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ,则可以存储这个新的日程安排。
当两个日程安排有一些时间上的交叉时(例如两个日程安排都在同一时间内),就会产生 重复预订 。
日程可以用一对整数 start
和 end
表示,这里的时间是半开区间,即 , 实数 的范围为, 。
实现 MyCalendar 类:
MyCalendar()
初始化日历对象。boolean book(int start, int end)
如果可以将日程安排成功添加到日历中而不会导致重复预订,返回true
。否则,返回false
并且不要将该日程安排添加到日历中。
示例:
输入:
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
输出:
[null, true, false, true]
解释:
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False ,这个日程安排不能添加到日历中,因为时间 15 已经被另一个日程安排预订了。
myCalendar.book(20, 30); // return True ,这个日程安排可以添加到日历中,因为第一个日程安排预订的每个时间都小于 20 ,且不包含时间 20 。
提示:
每个测试用例,调用 book
方法的次数最多不超过 次。
模拟
利用 book
操作最多调用 次,我们可以使用一个数组存储所有已被预定的日期 ,对于每次 book
操作,检查当前传入的 是否会与已有的日期冲突,冲突返回 False
,否则将 插入数组并返回 True
。
代码:
class MyCalendar {
List<int[]> list = new ArrayList<>();
public boolean book(int start, int end) {
end--;
for (int[] info : list) {
int l = info[0], r = info[1];
if (start > r || end < l) continue;
return false;
}
list.add(new int[]{start, end});
return true;
}
}
时间复杂度:令 为 book
的最大调用次数,复杂度为空间复杂度:
线段树(动态开点)
线段树维护的节点信息包括:
ls/rs
: 分别代表当前节点的左右子节点在线段树数组tr
中的下标;add
: 懒标记;val
: 为当前区间的所包含的点的数量。
对于常规的线段树实现来说,都是一开始就调用 build
操作创建空树,而线段树一般以「满二叉树」的形式用数组存储,因此需要 的空间,并且这些空间在起始 build
空树的时候已经锁死。
如果一道题仅仅是「值域很大」的离线题(提前知晓所有的询问),我们还能通过「离散化」来进行处理,将值域映射到一个小空间去,从而解决 MLE
问题。
但对于本题而言,由于「强制在线」的原因,我们无法进行「离散化」,同时值域大小达到 级别,因此如果我们想要使用「线段树」进行求解,只能采取「动态开点」的方式进行。
动态开点的优势在于,不需要事前构造空树,而是在插入操作 add
和查询操作 query
时根据访问需要进行「开点」操作。由于我们不保证查询和插入都是连续的,因此对于父节点 而言,我们不能通过 u << 1
和 u << 1 | 1
的固定方式进行访问,而要将节点 的左右节点所在 tr
数组的下标进行存储,分别记为 ls
和 rs
属性。对于 和 则是代表子节点尚未被创建,当需要访问到它们,而又尚未创建的时候,则将其进行创建。
由于存在「懒标记」,线段树的插入和查询都是 的,因此我们在单次操作的时候,最多会创建数量级为 的点,因此空间复杂度为 ,而不是 ,而开点数的预估需不能仅仅根据 来进行,还要对常熟进行分析,才能得到准确的点数上界。
动态开点相比于原始的线段树实现,本质仍是使用「满二叉树」的形式进行存储,只不过是按需创建区间,如果我们是按照连续段进行查询或插入,最坏情况下仍然会占到 的空间,因此盲猜 的常数在 左右,保守一点可以直接估算到 ,因此我们可以估算点数为 ,其中 和 分别代表值域大小和查询次数。
当然一个比较实用的估点方式可以「尽可能的多开点数」,利用题目给定的空间上界和我们创建的自定义类(结构体)的大小,尽可能的多开( Java
的 可以开到 以上)。
代码:
class MyCalendar {
class Node {
// ls 和 rs 分别代表当前节点的左右子节点在 tr 的下标
// val 代表当前节点有多少数
// add 为懒标记
int ls, rs, add, val;
}
int N = (int)1e9, M = 120010, cnt = 1;
Node[] tr = new Node[M];
void update(int u, int lc, int rc, int l, int r, int v) {
if (l <= lc && rc <= r) {
tr[u].val += (rc - lc + 1) * v;
tr[u].add += v;
return ;
}
lazyCreate(u);
pushdown(u, rc - lc + 1);
int mid = lc + rc >> 1;
if (l <= mid) update(tr[u].ls, lc, mid, l, r, v);
if (r > mid) update(tr[u].rs, mid + 1, rc, l, r, v);
pushup(u);
}
int query(int u, int lc, int rc, int l, int r) {
if (l <= lc && rc <= r) return tr[u].val;
lazyCreate(u);
pushdown(u, rc - lc + 1);
int mid = lc + rc >> 1, ans = 0;
if (l <= mid) ans = query(tr[u].ls, lc, mid, l, r);
if (r > mid) ans += query(tr[u].rs, mid + 1, rc, l, r);
return ans;
}
void lazyCreate(int u) {
if (tr[u] == null) tr[u] = new Node();
if (tr[u].ls == 0) {
tr[u].ls = ++cnt;
tr[tr[u].ls] = new Node();
}
if (tr[u].rs == 0) {
tr[u].rs = ++cnt;
tr[tr[u].rs] = new Node();
}
}
void pushdown(int u, int len) {
tr[tr[u].ls].add += tr[u].add; tr[tr[u].rs].add += tr[u].add;
tr[tr[u].ls].val += (len - len / 2) * tr[u].add; tr[tr[u].rs].val += len / 2 * tr[u].add;
tr[u].add = 0;
}
void pushup(int u) {
tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val;
}
public boolean book(int start, int end) {
if (query(1, 1, N + 1, start + 1, end) > 0) return false;
update(1, 1, N + 1, start + 1, end, 1);
return true;
}
}
时间复杂度:令 为值域大小,本题固定为 ,线段树的查询和增加复杂度均为 空间复杂度:令询问数量为 ,复杂度为
分块 + 位运算(分桶)
另一个留有遗憾的算法是「分块」,朴素的分块做法是使用一个布尔数组 region
代表某个块是否有被占用,使用哈希表记录具体某个位置是否被占用,但可惜被奇怪的测评机制卡了。
TLE
代码:
class MyCalendar {
static Boolean T = Boolean.TRUE, F = Boolean.FALSE;
static int n = (int)1e9, len = (int) Math.sqrt(n) + 30;
static boolean[] region = new boolean[len];
static Map<Integer, Boolean> map = new HashMap<>();
int getIdx(int x) {
return x / len;
}
void add(int l, int r) {
if (getIdx(l) == getIdx(r)) {
for (int k = l; k <= r; k++) map.put(k, T);
} else {
int j = l, i = r;
while (getIdx(j) == getIdx(l)) map.put(j++, T);
while (getIdx(i) == getIdx(r)) map.put(i--, T);
for (int k = getIdx(j); k <= getIdx(i); k++) region[k] = true;
}
}
boolean query(int l, int r) {
if (getIdx(l) == getIdx(r)) {
boolean cur = region[getIdx(l)];
for (int k = l; k <= r; k++) {
if (map.getOrDefault(k, F) || cur) return false;
}
return true;
} else {
int j = l, i = r;
while (getIdx(j) == getIdx(l)) {
if (map.getOrDefault(j, F) || region[getIdx(j)]) return false;
j++;
}
while (getIdx(i) == getIdx(r)) {
if (map.getOrDefault(i, F) || region[getIdx(i)]) return false;
i--;
}
for (int k = getIdx(j); k <= getIdx(i); k++) {
if (region[k]) return false;
}
return true;
}
}
public MyCalendar() {
Arrays.fill(region, false);
map.clear();
}
public boolean book(int start, int end) {
if (query(start, end - 1)) {
add(start, end - 1);
return true;
}
return false;
}
}
但我们知道分块算法的复杂度并不糟糕,而哈希表可能是被卡常数的关键,因此我们可以使用 int
数组来充当哈希表,由于只需要记录「是否被占用」,因此我们可以使用 int
的每一位充当格子,通过这种「分桶 + 位运算」,有效降低常数。
AC
代码(2022-07-05
可过):
class MyCalendar {
static int n = (int)1e9, len = (int) Math.sqrt(n) + 50, cnt = 32;
static boolean[] region = new boolean[len];
static int[] map = new int[n / cnt];
int getIdx(int x) {
return x / len;
}
boolean get(int x) {
return ((map[x / cnt] >> (x % cnt)) & 1) == 1;
}
void set(int x) {
map[x / cnt] |= (1 << (x % cnt));
}
void add(int l, int r) {
if (getIdx(l) == getIdx(r)) {
for (int k = l; k <= r; k++) set(k);
} else {
int j = l, i = r;
while (getIdx(j) == getIdx(l)) set(j++);
while (getIdx(i) == getIdx(r)) set(i--);
for (int k = getIdx(j); k <= getIdx(i); k++) region[k] = true;
}
}
boolean query(int l, int r) {
if (getIdx(l) == getIdx(r)) {
boolean cur = region[getIdx(l)];
for (int k = l; k <= r; k++) {
if (get(k) || cur) return false;
}
return true;
} else {
int j = l, i = r;
while (getIdx(j) == getIdx(l)) {
if (get(j) || region[getIdx(j)]) return false;
j++;
}
while (getIdx(i) == getIdx(r)) {
if (get(i) || region[getIdx(i)]) return false;
i--;
}
for (int k = getIdx(j); k <= getIdx(i); k++) {
if (region[k]) return false;
}
return true;
}
}
public MyCalendar() {
Arrays.fill(region, false);
Arrays.fill(map, 0);
}
public boolean book(int start, int end) {
if (query(start, end - 1)) {
add(start, end - 1);
return true;
}
return false;
}
}
时间复杂度: 空间复杂度: ,其中 为值域大小, 为单个数字的能够存储的格子数
最后
这是我们「刷穿 LeetCode」系列文章的第 No.729
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
边栏推荐
- be careful! Software supply chain security challenges continue to escalate
- The speed monitoring chip based on Bernoulli principle can be used for natural gas pipeline leakage detection
- dynamic programming
- Which Internet companies are worth going to in Shenzhen for software testers [Special Edition for software testers]
- R语言ggplot2可视化条形图:通过双色渐变配色颜色主题可视化条形图、为每个条形添加标签文本(geom_text函数)
- Section - left closed right open
- R language uses the polR function of mass package to build an ordered multi classification logistic regression model, and uses the coef function to obtain the log odds ratio corresponding to each vari
- Webrtc learning (II)
- Thymeleaf 使用后台自定义工具类处理文本
- How to protect user privacy without password authentication?
猜你喜欢
直播预告|如何借助自动化工具落地DevOps(文末福利)
How does redis implement multiple zones?
Pointer operation - C language
leetcode:881. lifeboat
How to choose the appropriate certificate brand when applying for code signing certificate?
SaaS multi tenant solution for FMCG industry to build digital marketing competitiveness of the whole industry chain
选择排序和冒泡排序
Redis如何实现多可用区?
Niuke: intercepting missiles
Thymeleaf th:classappend attribute append th:styleappend style append th:data- custom attribute
随机推荐
CYCA少儿形体礼仪 宁波市培训成果考核圆满落幕
Explain Vue's plan to clean up keepalive cache in time
How does redis implement multiple zones?
启牛学堂班主任给的证券账户安全吗?能开户吗?
[summary of leetcode weekly competition] the 81st fortnight competition of leetcode (6.25)
R语言ggplot2可视化:gganimate包基于transition_time函数创建动态散点图动画(gif)、使用shadow_mark函数为动画添加静态散点图作为动画背景
3W principle [easy to understand]
be careful! Software supply chain security challenges continue to escalate
There is a powerful and good-looking language bird editor, which is better than typora and developed by Alibaba
Enjoy what you want. Zhichuang future
总量分析 核算方法和势方法 - 分摊分析
一网打尽异步神器CompletableFuture
SaaS multi tenant solution for FMCG industry to build digital marketing competitiveness of the whole industry chain
Disjoint Set
微帧科技荣获全球云计算大会“云鼎奖”!
快消品行业SaaS多租户解决方案,构建全产业链数字化营销竞争力
webRTC SDP mslabel lable
R语言使用nnet包的multinom函数构建无序多分类logistic回归模型、使用coef函数获取模型中每个变量(自变量改变一个单位)对应的对数优势比(log odds ratio)
【leetcode周赛总结】LeetCode第 81 场双周赛(6.25)
Qingda KeYue rushes to the science and Innovation Board: the annual revenue is 200million, and it is proposed to raise 750million