1. 除法求值

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

虽然写的时间长了点，但是一遍过！

主要这题的标签有“图“，不然正常不太好想到用图去解决，很可能会去折腾怎么模拟了。

把变量抽象成一个个顶点，把除法关系抽象成两个变量间的有向带权边，且两个点间的反向边权值互为倒数。那么求任意两个点的商，实际上就是求一条路径上的权值之积。如果变量不在顶点集内，那么返回 -1 。

我们将字符串映射为 0 起始的数字，这样可以用一个邻接矩阵来表示整个图。然后用 DFS 找两点间路径，并给出累积权值。

为了方便起见，实际上是用回溯法，先在 ans 末尾附加上一个 -1 ，即默认不存在这样的路径。然后在回溯中找到路径时将 ans 末尾元素弹出，将累积权值添加到 ans 尾部即可。

代码

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        map = defaultdict()
        n = 0
        for s1, s2 in equations:
            if s1 not in map:
                map[s1] = n
                n += 1
            if s2 not in map:
                map[s2] = n
                n += 1
        graph = [[-1.0 for _ in range(n)] for _ in range(n)]
        m = len(equations)
        for i in range(m):
            graph[map[equations[i][0]]][map[equations[i][1]]] = values[i]
            graph[map[equations[i][1]]][map[equations[i][0]]] = 1 / values[i]
        ans = []
        def dfs(cur: int, end: int, visited: List[int], path: float) -> None:
            if cur == end:
                ans.pop()
                ans.append(path)
                return
            for next in range(n):
                if graph[cur][next] != -1.0 and not visited[next]:
                    visited[next] = 1
                    path *= graph[cur][next]
                    dfs(next, end, visited, path)
                    path /= graph[cur][next]
                    visited[next] = 0
        for s1, s2 in queries:
            visited = [0 for _ in range(n)]
            if s1 not in map or s2 not in map:
                ans.append(-1.0)
            else:
                visited[map[s1]] = 1
                ans.append(-1.0)
                dfs(map[s1], map[s2], visited, 1.0)
        return ans

2. 冗余连接

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

本以为用集合来判断最后出现的边会比较低效，结果时间几乎超过 100% ，比较占空间就是。

这道题作图模拟一下，不难发现，可以先找到图中的环，然后从环中随便去掉一条边即可，只不过这条边要是最后出现的边。

类比拓扑排序找有向图中的环的思想，我们用一个数组 du 记录每个顶点的度，显然度为 1 的点不会在环里面，那么我们逐个去除度为 1 的点，并将其邻接点的度减一。最终剩下的度大于 1 的点（实际上都是 2 ），就是环上的所有点。我们将这些点放进集合里，然后从后向前遍历边集，第一个两端点都在集合内的边，就是要返回的答案。

代码

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        graph = [[] for _ in range(n)]
        du = [0 for _ in range(n)]
        for v1, v2 in edges:
            du[v1 - 1] += 1
            du[v2 - 1] += 1
            graph[v1 - 1].append(v2 - 1)
            graph[v2 - 1].append(v1 - 1)
        queue = []
        for v in range(n):
            if du[v] == 1:
                queue.append(v)
        while queue:
            cur = queue.pop(0)
            for v in graph[cur]:
                du[v] -= 1
                if du[v] == 1:
                    queue.append(v)
        nodeSet = set()
        for v in range(n - 1, -1, -1):
            if du[v] > 1:
                nodeSet.add(v + 1)
        for idx in range(n - 1, -1, -1):
            if edges[idx][0] in nodeSet and edges[idx][1] in nodeSet:
                return edges[idx]
        return []

3. 单词的压缩编码

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

虽然打着图的 tag ，但确实没想到怎么用图做，一点思路是并查集。

手动模拟了一下，想到一个很方便的方法。本质上，这个编码过程，就是一个合并后缀的过程。比如字符串 time 和 me ，后者是前者的后缀，那么把后者删除，然后记录下起始到 # 的位置。最终字符串的长度，只要加上 time 的长度即可（附带一个 # ）。而我们最终返回的只是字符串长度，而不用关心助记字符串的具体样子和 indice 数组 。所以说到底，我们只关心哪些字符串可以被合并到另一个 字符串中去。而最终，我们返回不可合并的字符串的总长度 + 总数（即 # 的数量）。

那么，可以这样做：

1. 将 words 中的字符串全部反转，将判断后缀转换为判断前缀，这样可以用字符串的 find() 成员函数直接实现。
2. 将 words 排序，即按字典序排序，这样字符串一定是按前缀字符串连续，且长度短的在前的顺序排列。
3. 逐个判断当前字符串是否是后一个字符串的前缀，是的话，即可以合并，就 continue 略过。如果不能合并，则要把当前字符串加到助记字符串中去，还要附带一个 # 。当然，最后一个字符串也要一样加入进去。

代码

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        ans = 0
        n = len(words)
        for idx in range(n):
            words[idx] = words[idx][::-1]
        words.sort()
        for idx in range(n):
            if idx < n - 1 and words[idx + 1].find(words[idx]) == 0:
                continue
            else: ans += len(words[idx]) + 1
        return ans

4. 从二叉搜索树到更大和树

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

看到二叉搜索树，第一反应转换成线性结构（被某次周赛搞得印象深刻）。

因为节点数有限，方便起见直接定义一个 101 容量的数组 tree 存储节点，另外一个 101 容量的数组 nums 存储值，对于不存在的节点，对应 tree 的元素是 None ，对应 nums 元素是 0 ，线性遍历每一个节点，如果节点存在，将其值改写为对右侧元素（包括自己）求和。时间超过 100% ，空间超过 55% 。

代码

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        tree = [None for _ in range(101)]
        nums = [0 for _ in range(101)]
        def convert(cur: TreeNode):
            if not cur: return
            tree[cur.val] = cur
            nums[cur.val] = cur.val
            convert(cur.left)
            convert(cur.right)
        convert(root)
        for idx in range(101):
            if tree[idx]:
                tree[idx].val = sum(nums[idx:])
        return root

5. 多边形三角剖分的最低得分

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

原本想用数组的方法枚举所有情况，但失败了。

题解基本使用记忆化搜索，没见与图相关解法。关于记忆化搜索还有待学习。

代码