@TOC
日报
- 明天两题之前都做过，从新提交一遍。
- 这两题我测试线段树和珂朵莉都能够过，珂朵莉快一点。
- [[python刷题模板] 珂朵莉树 ODT](https://blog.csdn.net/liulian...)
- [[python刷题模板] 线段树](https://blog.csdn.net/liulian...)
- [[LeetCode解题报告] 699. 掉落的方块](https://blog.csdn.net/liulian...)
题目
一、731. 我的日程安排表 II
731. 我的日程安排表 II
1. 题目形容
- 我的日程安排表 II
难度：中等
实现一个 MyCalendar 类来寄存你的日程安排。如果要增加的工夫内不会导致三重预订时，则能够存储这个新的日程安排。
MyCalendar 有一个 book(int start, int end)办法。它意味着在 start 到 end 工夫内减少一个日程安排，留神，这里的工夫是半开区间，即 [start, end), 实数 x 的范畴为， start <= x < end。
当三个日程安排有一些工夫上的穿插时（例如三个日程安排都在同一时间内），就会产生三重预订。
每次调用 MyCalendar.book办法时，如果能够将日程安排胜利增加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排增加到日历中。
请依照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
示例：
MyCalendar();MyCalendar.book(10, 20); // returns trueMyCalendar.book(50, 60); // returns trueMyCalendar.book(10, 40); // returns trueMyCalendar.book(5, 15); // returns falseMyCalendar.book(5, 10); // returns trueMyCalendar.book(25, 55); // returns true解释： 前两个日程安排能够增加至日历中。 第三个日程安排会导致双重预订，但能够增加至日历中。第四个日程安排流动（5,15）不能增加至日历中，因为它会导致三重预订。第五个日程安排（5,10）能够增加至日历中，因为它未应用曾经双重预订的工夫10。第六个日程安排（25,55）能够增加至日历中，因为工夫 [25,40] 将和第三个日程安排双重预订；工夫 [40,50] 将独自预订，工夫 [50,55）将和第二个日程安排双重预订。提醒：
- 每个测试用例，调用
MyCalendar.book函数最多不超过1000次。 - 调用函数
MyCalendar.book(start, end)时，start和end的取值范畴为[0, 10^9]。
2. 思路剖析
- 保护区间[l,r]工夫区间上的预约数。
- 发现以后区间最大值为2了，则这个区间再插入就是3.
- 显然是线段树IUIQ的板子，区间更新就是要思考Lazytag。
- 发现数据范畴10^9,那么思考离线做离散化，发现强行禁止离线，只能在线做。
- 那么找到动静开点线段树的板子，CV胜利！
- 这里说一下废话：为什么要用线段树或者珂朵莉而不能用数组模仿：因为数组模仿是 O(nm) 的，n是每次线段均匀长度，这里最大是 10^9 。必定过不了。
- 而线段树能够把这个过程变成 O(mlgn)。
3. 代码实现
class IntervalTree: def __init__(self): self.interval_tree = collections.defaultdict(int) self.lazys = collections.defaultdict(int) def give_lay_to_son(self,p,l,r): interval_tree = self.interval_tree lazys = self.lazys if lazys[p] == 0: return mid = (l+r)//2 interval_tree[p*2] += lazys[p] interval_tree[p*2+1] += lazys[p] lazys[p*2] += lazys[p] lazys[p*2+1] += lazys[p] lazys[p] = 0 def add(self,p,l,r,x,y,val): """ 把[x,y]区域全+val """ if r < x or y < l: # 这里不加就会TLE return interval_tree = self.interval_tree lazys = self.lazys if x <= l and r<=y: interval_tree[p] += val lazys[p] += val return self.give_lay_to_son(p,l,r) mid = (l+r)//2 if x <= mid: self.add(p*2,l,mid,x,y,val) if mid < y: self.add(p*2+1,mid+1,r,x,y,val) interval_tree[p] = max(interval_tree[p*2], interval_tree[p*2+1]) def query(self,p,l,r,x,y): """ 查找x,y区间的最大值 """ if y < l or r < x: return 0 if x<=l and r<=y: return self.interval_tree[p] self.give_lay_to_son(p,l,r) mid = (l+r)//2 s = 0 if x <= mid: s = max(s,self.query(p*2,l,mid,x,y)) if mid < y: s = max(s,self.query(p*2+1,mid+1,r,x,y)) return sclass MyCalendarTwo: def __init__(self): self.tree = IntervalTree() def book(self, start: int, end: int) -> bool: m = self.tree.query(1,1,10**9+1,start+1,end) if m >= 2: return False self.tree.add(1,1,10**9+1,start+1,end,1) return True二、 699. 掉落的方块
链接: 699. 掉落的方块
1. 题目形容
- 掉落的方块
难度：艰难
在二维立体上的 x 轴上，搁置着一些方块。
给你一个二维整数数组 positions ，其中 positions[i] = [lefti, sideLengthi] 示意：第 i 个方块边长为 sideLengthi ，其左侧边与 x 轴上坐标点 lefti 对齐。
每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向着落，直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无奈挪动。
在每个方块掉落后，你必须记录目前所有曾经落稳的 方块重叠的最高高度 。
返回一个整数数组 ans ，其中 ans[i] 示意在第 i 块方块掉落后重叠的最高高度。
示例 1：
<img style="width: 100%; height: 100%;" src="https://assets.leetcode.com/uploads/2021/04/28/fallingsq1-plane.jpg" alt="">
输出：positions = [[1,2],[2,3],[6,1]]输入：[2,5,5]解释：第 1 个方块掉落后，最高的重叠由方块 1 组成，重叠的最高高度为 2 。第 2 个方块掉落后，最高的重叠由方块 1 和 2 组成，重叠的最高高度为 5 。第 3 个方块掉落后，最高的重叠依然由方块 1 和 2 组成，重叠的最高高度为 5 。因而，返回 [2, 5, 5] 作为答案。示例 2：
输出：positions = [[100,100],[200,100]]输入：[100,100]解释：第 1 个方块掉落后，最高的重叠由方块 1 组成，重叠的最高高度为 100 。第 2 个方块掉落后，最高的重叠能够由方块 1 组成也能够由方块 2 组成，重叠的最高高度为 100 。因而，返回 [100, 100] 作为答案。留神，方块 2 擦过方块 1 的右侧边，但不会算作在方块 1 上着陆。提醒：
1 <= positions.length <= 10001 <= lefti <= 1081 <= sideLengthi <= 106
2. 思路剖析
- 方块掉落时，显然高度取决于这个方块底边管辖内，以后最高的方块，本方块会落在上边。
- 那咱们须要的是一个疾速查问区间极值，疾速区间赋值的数据结构，显然线段树能够。
- 这题范畴较大，然而能够离线，那就离散化吧。
- 这题有大量区间推平操作，能够珂朵莉。
- 这里还是贴一个线段树，须要珂朵莉能够去我上边贴的地址看。
3. 代码实现
class IntervalTree: def __init__(self, size): self.size = size self.interval_tree = [0 for _ in range(size*4)] self.lazys = [0 for _ in range(size*4)] def give_lay_to_son(self,p,l,r): interval_tree = self.interval_tree lazys = self.lazys if lazys[p] == 0: return mid = (l+r)//2 interval_tree[p*2] = lazys[p] interval_tree[p*2+1] = lazys[p] lazys[p*2] = lazys[p] lazys[p*2+1] = lazys[p] lazys[p] = 0 def update(self,p,l,r,x,y,val): """ 把[x,y]区域全变成val """ if y < l or r < x: return interval_tree = self.interval_tree lazys = self.lazys if x <= l and r<=y: interval_tree[p] = val lazys[p] = val return self.give_lay_to_son(p,l,r) mid = (l+r)//2 if x <= mid: self.update(p*2,l,mid,x,y,val) if mid < y: self.update(p*2+1,mid+1,r,x,y,val) interval_tree[p] = max(interval_tree[p*2], interval_tree[p*2+1]) def query(self,p,l,r,x,y): """ 查找x,y区间的最大值 """ if y < l or r < x: return 0 if x<=l and r<=y: return self.interval_tree[p] self.give_lay_to_son(p,l,r) mid = (l+r)//2 s = 0 if x <= mid: s = max(s,self.query(p*2,l,mid,x,y)) if mid < y: s = max(s,self.query(p*2+1,mid+1,r,x,y)) return sclass Solution: def fallingSquares(self, positions: List[List[int]]) -> List[int]: n = len(positions) hashes = [left for left,_ in positions] + [left+side for left,side in positions] hashes = sorted(list(set(hashes))) # 用线段树保护x轴区间最大值，记录每个点的高度：比方[1,2]这个方块，会使线段[1,2]闭区间这个线段上的每个高度都变成2 # 落下一个新方块时，查问它的底边所在线段[x,y]的最大高度h，这个方块会落在这个高度h，把新高度h+side插入线段树[x,y]的局部 # 每次插入完结，树根存的高度就是以后最大高度 # 因为数据范畴大1 <= lefti <= 108，须要散列化 # 散列化的值有left和right(线段短点) # print(hashes) tree_size = len(hashes) tree = IntervalTree(tree_size) heights = [] for left,d in positions: right = left + d l = bisect_left(hashes,left) r = bisect_left(hashes,right) h = tree.query(1,1,tree_size,l+1,r) tree.update(1,1,tree_size,l+1,r,h+d) heights.append(tree.interval_tree[1]) return heights人生苦短，我用Python！