Weekly Contest 317

Problem A

Average Value of Even Numbers That Are Divisible by Three

思路

事实上就是求整除6的数的均值

代码

class Solution:
    def averageValue(self, nums: List[int]) -> int:
        d = 0
        s=0
        for item in nums:
            if item%6==0:
                s+=item
                d+=1
        if d == 0:
            return 0
        else:
            return int(s/d)
        

Problem B

Most Popular Video Creator

思路

按照题意求就完事了，唯一的问题是过程比较麻烦，然后cmp要返回$\pm 1$而不是T,F.

代码

class Solution:
    def mostPopularCreator(self, creators: List[str], ids: List[str], views: List[int]) -> List[List[str]]:
        def cmp(x,y):
            # print(x,y)
            if x[0]==y[0]:
                return 1 if x[1]>y[1] else -1
            else:
                return 1 if x[0]<y[0] else -1
        s = {}
        t = {}
        for i in range(len(ids)):
            tmp = creators[i]
            s.setdefault(tmp,0)
            t.setdefault(tmp,[])
            s[tmp]+=views[i]
            t[tmp].append([views[i],ids[i]])
        temp = []
        ans = []
        for k,v in s.items():
            temp.append([v,k])
        temp.sort(reverse=True)
        d = temp[0][0]
        for v,k in temp:
            if v == d:
                L = t[k]
                L.sort(key=functools.cmp_to_key(cmp))
                # print(L)
                ans.append([k,L[0][1]])
        ans.sort()
        return ans
                

Problem C

Minimum Addition to Make Integer Beautiful

思路

构造题，将数字按高到低拆分，然后target从左到右减，当不能减的时候说明需要加数将当前位置及之后的变成0，然后上一位进1，就是处理起来有点麻烦。

代码

class Solution:
    def makeIntegerBeautiful(self, n: int, target: int) -> int:
        def check(x):
            s = 0
            t = []
            while x!=0:
                s+=x%10
                t.append(str(x%10))
                x=x//10
        
            return s,t  
        m = n
        while True:
            s,t = check(m)
            num = int("".join(t[::-1]))
            if s<=target:
                return num-n
            else:
                temp = target
                f =True
                d = 0
                for i in range(len(t)-1,-1,-1):
                    if f is False:
                        t[i] = '0'
                        continue
                    if temp<int(t[i]):
                        f = False
                        d = i+1
                        t[i] = '0'
                    else:
                        temp-=int(t[i])
                if d == len(t):
                    t.append('1')
                    m = int("".join(t[::-1]))
                else:
                    i = d
                    t.append('0')
                    t[d] = str(int(t[d])+1)
                    while(int(t[d])>9):
                    
                        t[d+1] = str(int(t[d+1])+1)
                        t[d]='0'
                        d+=1
                    m = int("".join(t[::-1]))

Problem D

Height of Binary Tree After Subtree Removal Queries

思路

思路很简单，就是两次DFS。一次dfs确定深度，一次得到结果，在第二次DFS时做的是得到除当前路径之外的最大深度，也就是答案。感觉这个思路蛮巧妙的

代码

class Solution:
    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:
        height = defaultdict(int)  # 每棵子树的高度
        def get_height(node: Optional[TreeNode]) -> int:
            if node is None: return 0
            height[node] = 1 + max(get_height(node.left), get_height(node.right))
            return height[node]
        get_height(root)

        res = [0] * (len(height) + 1)  # 每个节点的答案
        def dfs(node: Optional[TreeNode], depth: int, rest_h: int) -> None:
            if node is None: return
            depth += 1
            res[node.val] = rest_h
            dfs(node.left, depth, max(rest_h, depth + height[node.right]))
            dfs(node.right, depth, max(rest_h, depth + height[node.left]))
        dfs(root, -1, 0)

        for i, q in enumerate(queries):
            queries[i] = res[q]
        return queries

总结

出了3题，但是感觉蛮冗余的，最后一题的思路蛮巧妙地，可惜没想出来。