跟着leedcode刷算法 -- 树2

发表于

这是我参与11月更文挑战的第24天，活动详情查看：2021最后一次更文挑战

image.png

题3

二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
示例 4：

输入：root = [1,2]
输出：[1,2]

提示：

  • 树中结点数在范围 [0, 104] 内
  • -1000 <= Node.val <= 1000
  • 相关标签*
  • 树
  • 深度优先搜索
  • 广度优先搜索
  • 设计
  • 字符串
  • 二叉树

解题思路：
深度优先 DFS 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
python复制代码# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        def dfs(node):
            if node:
                res.append(str(node.val))
                dfs(node.left)
                dfs(node.right)
            else:
                res.append("#")

        res = []
        dfs(root)
        return ",".join(res)


    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        def dfs():
            v = next(res)
            if v == "#":
                return None
            node = TreeNode(int(v))
            node.left = dfs()
            node.right = dfs()
            return node
        res = iter(data.split(","))
        return dfs()

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

执行结果:

image.png

题4

天际线问题

城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回由这些建筑物形成的 天际线 。

每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：

  • lefti 是第 i 座建筑物左边缘的 x 坐标。
  • righti 是第 i 座建筑物右边缘的 x 坐标。
  • heighti 是第 i 座建筑物的高度。
  • 天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],…] ，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
  • 注意：输出天际线中不得有连续的相同高度的水平线。例如 […[2 3], [4 5], [7 5], [11 5], [12 7]…] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[…[2 3], [4 5], [12 7], …]

示例 1：

image.png

  • 输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
  • 输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
  • 解释：
  • 图 A 显示输入的所有建筑物的位置和高度，
  • 图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。
    示例 2：
  • 输入：buildings = [[0,2,3],[2,5,3]]
  • 输出：[[0,3],[5,0]]

提示：

  • 1 <= buildings.length <= 104
  • 0 <= lefti < righti <= 231 - 1
  • 1 <= heighti <= 231 - 1
  • buildings 按 lefti 非递减排序
  • 相关标签*
  • 树状数组
  • 线段树
  • 数组
  • 分治
  • 有序集合
  • 扫描线
  • 堆（优先队列）

这里借助一下SortedList 方法来维持高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ini复制代码from sortedcontainers import SortedList

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        res = []
        ans = []
        for l, r, h in buildings:
            ans.append((l, -h))
            ans.append((r, h))
        ans.sort()
        level = SortedList([0])
        response = 0
        for i, j in ans:
            if j < 0:
                level.add(j)
            else:
                level.remove(-j)
            curr_max = -level[0]
            if curr_max != response:
                res.append([i, curr_max])
            response = curr_max
        return res

执行结果：

image.png

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%