Leetcode第344场周赛解题报告

又是手速场，不过今天来晚了，没掉分就是了

6416. 找出不同元素数目差数组

知识点：模拟
复杂度：$O(n)$
按照题意模拟出前缀后缀

from typing import List


class Solution:
    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:
        dif = []
        dif_pre = []
        s1 = set()
        for i in nums:
            s1.add(i)
            dif.append(len(s1))
        nums.reverse()
        s1 = set()
        for i in nums:
            s1.add(i)
            dif_pre.append(len(s1))
        dif_pre.reverse()
        dif_pre.append(0)
        return [dif[i]-dif_pre[i+1] for i in range(len(nums))]

6417. 频率跟踪器

知识点：模拟
复杂度：$O(n)$
根据题意模拟哈希表

from typing import List


class FrequencyTracker:

    def __init__(self):
        self.mp = [0]*(int(pow(10,5))+10)
        self.app = [0]*(int(pow(10,5))+10)

    def add(self, number: int) -> None:
        self.mp[number] += 1
        rst = self.mp[number]
        self.app[rst] += 1
        if rst > 1:
            self.app[rst-1] -= 1


    def deleteOne(self, number: int) -> None:
        if self.mp[number] > 0:
            self.app[self.mp[number]] -= 1
            self.mp[number] -= 1
            self.app[self.mp[number]] += 1


    def hasFrequency(self, frequency: int) -> bool:
        return True if self.app[frequency] > 0 else False



# Your FrequencyTracker object will be instantiated and called as such:
# obj = FrequencyTracker()
# obj.add(number)
# obj.deleteOne(number)
# param_3 = obj.hasFrequency(frequency)

6418. 有相同颜色的相邻元素数目

知识点：归纳
复杂度：$O(n)$
根据题意归纳出三种情况，修改后：

• A.不影响答案
• B.拆散了连续（答案-1/-2）
• C.构成新的连续(答案+1/+2)

import random
from typing import List


class Solution:
    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
        m = [0] * n
        ans = []
        now = 0
        for s,e in queries:
            if s < n-1 and m[s] == m[s+1] and m[s] != 0:
                now -= 1
            if s > 0 and m[s] == m[s-1] and m[s] != 0:
                now -= 1
            m[s] = e
            if s < n-1 and m[s] == m[s+1] and m[s] != 0:
                now += 1
            if s > 0 and m[s] == m[s-1] and m[s] != 0:
                now += 1
            ans.append(now)
        return ans

6419. 使二叉树所有路径值相等的最小代价

知识点：搜索
复杂度：$O(3*n)$
明确：

1. 只能增加，也就是说最后所有路径和需要=最大的那个路径和
2. 求最小增加次数，也就是说尽量在根节点就增加完成，能够减少叶节点的增加数量

所以思路：

1. 第一次dfs求每条路径的代价，保存最大代价
2. 第二次dfs求每个节点最大能够减少的代价
3. 第三次dfs按照第二次dfs求的代价进行计算，得到答案

import random
from typing import List


class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        cost.insert(0, 0)
        global mxas
        mxas = 0
        mark = [0] * (n + 1)

        def dfs(now, sm=0, mx=-1, dep=1):
            l = now * 2
            r = now * 2 + 1
            dep = 1
            cst = cost[now]
            mx = max(mx, cst)
            sm = sm + cst
            if l < n:
                dfs(l, sm, mx, dep + 1)
                dfs(r, sm, mx, dep + 1)
            else:
                global mxas
                mxas = max(mxas, sm)

        def dfs1(now, sm=0, mx=-1, dep=1):
            l = now * 2
            r = now * 2 + 1
            dep = 1
            cst = cost[now]
            mx = max(mx, cst)
            sm = sm + cst
            if l < n:
                a = dfs1(l, sm, mx, dep + 1)
                b = dfs1(r, sm, mx, dep + 1)
                mark[now] = min(a, b)
                return min(a, b)
            else:
                mark[now] = mxas - sm
                return mxas - sm

        global ans
        ans = 0

        def dfs2(now, add=0):
            l = now * 2
            r = now * 2 + 1
            if mark[now] > 0:
                global ans
                ans += mark[now] - add
                add = mark[now]
            if l < n:
                dfs2(l, add)
                dfs2(r, add)

        dfs(1)
        dfs1(1)
        dfs2(1)
        return ans