BakerHub

# A. Average Value of Even Numbers That Are Divisible by Three (opens new window)

Find elements not divisible by 6.

DETAILS 
def averageValue(self, nums: List[int]) -> int:
        ans = [x for x in nums if not x % 6]
        return 0 if not ans else sum(ans) // len(ans)

Sort creators by their accumulated views.

DETAILS 
def mostPopularCreator(self, C: List[str], D: List[str], V: List[int]) -> List[List[str]]:
        count = collections.defaultdict(int)
        videos = collections.defaultdict(list)
        
        for c, d, v in zip(C, D, V):
            count[c] += v
            videos[c].append([-v, d])

        ma, ans = max(count.values()), []
        for k, v in count.items():
            if v == ma:
                ans.append([k, sorted(videos[k])[0][1]])
        
        return ans

# C. Minimum Addition to Make Integer Beautiful (opens new window)

When the integer is initially not beautiful, after it becomes beautiful, its last digits must be 0.

Thus we keep making its lasting digits to 0, until the modified integer is beautiful.

DETAILS 
def makeIntegerBeautiful(self, n: int, target: int) -> int:
        L = [0] + [int(k) for k in str(n)]
        i = len(L) - 1
        
        while sum(L) > target or L[i] > 9:
            L[i] = 0
            L[i - 1] += 1
            i -= 1
            
        return int("".join(map(str, L))) - n

# D. Height of Binary Tree After Subtree Removal Queries (opens new window)

Please refer to This LC Discussion (opens new window) for my solution in English.

我们把节点按照深度来分类，如果被移除的点深度为d，那么从树根出发到这个点的路径长度不会超过d。但我们可以看看这个节点有没有其他的兄弟节点，如果有，那么从树根到这些兄弟节点上一定存在更长（最长）的路径。

DETAILS 
def treeQueries(self, R: Optional[TreeNode], Q: List[int]) -> List[int]:
        Depth, Height = collections.defaultdict(int), collections.defaultdict(int)

        def dfs(node, depth):
            if not node:
                return -1
            Depth[node.val] = depth
            cur = max(dfs(node.left, depth + 1), dfs(node.right, depth + 1)) + 1
            Height[node.val] = cur
            return cur
        dfs(R, 0)

        cousins = collections.defaultdict(list) # Group nodes according to their depth. Keep the top 2 heights.
        for val, depth in Depth.items():
            cousins[depth].append((-Height[val], val))
            cousins[depth].sort()
            if len(cousins[depth]) > 2:
                cousins[depth].pop()

        ans = []
        for q in Q:
            depth = Depth[q]
            if len(cousins[depth]) == 1:  # No cousin, path length equals depth - 1.
                ans.append(depth - 1)
            elif cousins[depth][0][1] == q:  # The removed node has the largest height, look for the node with 2nd largest height.
                ans.append(-cousins[depth][1][0] + depth)
			else:   # Look for the node with the largest height.
                ans.append(-cousins[depth][0][0] + depth)
        return ans

← Weekly Contest 316 →