乐趣区

关于python:英雄星球六月集训LeetCode解题日报-第24日-线段树

@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. 题目形容

  1. 我的日程安排表 II

难度:中等

实现一个 MyCalendar 类来寄存你的日程安排。如果要增加的工夫内不会导致三重预订时,则能够存储这个新的日程安排。

MyCalendar 有一个 book(int start, int end)办法。它意味着在 startend 工夫内减少一个日程安排,留神,这里的工夫是半开区间,即 [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 true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.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)时,startend 的取值范畴为 [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 s

class 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. 题目形容

  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 <= 1000
  • 1 <= lefti <= 108
  • 1 <= 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 s

class 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!

退出移动版