Leetcode第102场双周赛解题报告

继续恢复做双周赛哈，感觉第100周的难度很低
难度系数：0

2639. 查询网格图中每一列的宽度

知识点：模拟
复杂度：$O(n^2)$

from typing import List
from itertools import accumulate


class Solution:
    def findColumnWidth(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        line = len(grid[0])
        return [max(len(str(grid[j][i])) for j in range(n)) for i in range(line)]

2640. 一个数组所有前缀的分数

知识点：模拟
复杂度：$O(n)$

from typing import List
from itertools import accumulate

class Solution:
    def findPrefixScore(self, nums: List[int]) -> List[int]:
        n = len(nums)
        mx = nums[0]
        for i in range(n):
            mx = max(nums[i], mx)
            nums[i] += mx
        return list(accumulate(nums))

2641. 二叉树的堂兄弟节点 II

知识点：深度搜索
复杂度：$O(2*n) = O(n)$
思路：

• 1. 先进行第一次搜索：用mark标记出兄弟节点的size，同时按照深度缓存下所有相同深度节点的权重之和
• 2. 然后进行第二次搜索：使用缓存出的权重之和减去当前节点的权重，同时减去兄弟节点的size，最后得到题目要求的权重

from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        dep_mp = [0] * (10**5)
        root.mark = 0
        def dfs(rt: TreeNode, dep: int):
            dep_mp[dep] += rt.val
            if rt.left:
                rt.left.mark = 0
            if rt.right:
                rt.right.mark = 0
            if rt.left and rt.right:
                rt.left.mark = rt.right.val
                rt.right.mark = rt.left.val
            
            if rt.left:
                dfs(rt.left,dep+1)
            if rt.right:
                dfs(rt.right,dep+1)

        def dfs1(rt: TreeNode, dep: int):
            rt.val = dep_mp[dep] - rt.val - rt.mark
            if rt.left:
                dfs1(rt.left,dep+1)
            if rt.right:
                dfs1(rt.right,dep+1)

        dfs(root,0)

        dfs1(root,0)
        return root

2642. 设计可以求最短路径的图类

知识点：dijkstra
复杂度：$O(q * n^2)$
思路：

• 1. 建图时边表转换矩阵
• 2. 查询时使用dijkstra进行查询

优化：

• 1. 可以使用哈希表缓存数据

这题简单的不像第四题，单纯的dijkstra应用

from typing import List

INF = 100086111111
class Graph:

    def dijkstra(self, start: int):
        n = len(self.matrix)
        dist = [INF] * n
        dist[start] = 0
        visited = [False] * n
        for i in range(n):
            min_dist = INF
            min_index = -1
            for j in range(n):
                if not visited[j] and dist[j] < min_dist:
                    min_dist = dist[j]
                    min_index = j
            if min_index == -1:
                break
            visited[min_index] = True
            for j in range(n):
                if not visited[j] and self.matrix[min_index][j] != INF:
                    dist[j] = min(dist[j], dist[min_index] + self.matrix[min_index][j])
        return dist
    
    def __init__(self, n: int, edges: List[List[int]]):
        self.matrix = [([INF] * n)for i in range(n)]
        for i in range(n):
            self.matrix[i][i] = 0 #anti loop
        for start, end, weight in edges:
            self.matrix[start][end] = weight

        self.now_version = 0


    def addEdge(self, edge: List[int]) -> None:
        self.now_version += 1
        for start, end, weight in [edge]:
            self.matrix[start][end] = weight

    def shortestPath(self, node1: int, node2: int) -> int:
        res = self.dijkstra(node1)[node2]
        if res >= INF:
            return -1
        return res



# Your Graph object will be instantiated and called as such:
# obj = Graph(n, edges)
# obj.addEdge(edge)
# param_2 = obj.shortestPath(node1,node2)