讨论/题目交流/🐱 第 16 场夜喵双周赛/
🐱 第 16 场夜喵双周赛
展开讨论

Q1

倒着遍历, 一直维护一个最大值,添加最大值到结果,最后取反

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        ma = -1
        res = []
        for i in arr[::-1]:
            res.append(ma)
            if i>ma:
                ma = i
        return res[::-1]

Q2

跟之前一次周赛题很像
二分,左界0,右界10^5
每次二分更新结果

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        l, r = 0, 10**5
        
        def cal(m):
            res = 0
            for i in arr:
                if i<m:
                    res+=i
                else:
                    res+=m
            return res
            
        
        res = (0, 0)
        
        while l<=r:
            m = (l+r)//2
            sm = cal(m)
            if sm==target:
                r = m-1
                res = (m, sm)
                if abs(sm-target)<abs(res[1]-target): res = (m, sm)
            elif sm<target:
                l = m+1
                if abs(sm-target)<=abs(res[1]-target): res = (m, sm)
            else:
                r = m-1
                if abs(sm-target)<abs(res[1]-target): res = (m, sm)
                
        return res[0]

Q3

BFS,把每个深度对应节点和记录下来,最后取最深节点

class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        if not root.left and not root.right: return 0
        dic = collections.defaultdict(int)
        
        q = collections.deque()
        q.append([root, 0])
        while q:
            node, deep = q.popleft()
            dic[deep]+=node.val
            if node.right:
                q.append([node.right, deep+1])
            if node.left:
                q.append([node.left, deep+1])
                
        return dic[max(dic)]

Q4

dp, 重终点向起点走结果也是一样的,dp记录每个点的得分 和 有几条路,得分直接看[i-1][j], [i][j-1], [i-1][j-1]最大的分数加上当前点分数,
有几条路看 [i-1][j], [i][j-1], [i-1][j-1] 三个点中所有可以得到max分数路数的和

这题写的比较丑,比赛时候定义了两个重复命名变量,看了半小时才看出来。。。

class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        # for i in board: print(i)
        m, n = len(board), len(board[0])
        dp = [[[0, 1]]*n for _ in range(m)]
        mod = 10**9+7
        # for i in dp: print(i)
        
        for i in range(m):
            for j in range(n):
                score = 0
                if i==0 and j==0: dp[i][i] = [0, 0]
                if board[i][j]!='X' and board[i][j]!='E' and board[i][j]!='S':
                    score = int(board[i][j])
                
                if board[i][j]=="X":
                    dp[i][j] = [-1, 0]
                    continue
                if i==0:
                    if dp[i][j-1][0]==-1:
                        dp[i][j] = [-1, 0]
                    else:
                        dp[i][j] = [dp[i][j-1][0]+score, dp[i][j-1][1]]
                elif j==0:
                    if dp[i-1][j][0]==-1:
                        dp[i][j] = [-1, 0]
                    else:
                        dp[i][j] = [dp[i-1][j][0]+score, dp[i-1][j][1]]
                else:
                    # a, b, c = dp[i-1][j], dp[i][j-1], dp[i-1][j-1]
                    a = dp[i-1][j] if i-1>-1 else [-1, 0]
                    b = dp[i][j-1] if j-1>-1 else [-1, 0]
                    c = dp[i-1][j-1] if j-1>-1 and i-1>-1 else [-1, 0]
                    # print(i, j)
                    rec = [a, b, c]
                    ma = max([a[0], b[0], c[0]])
                    ps = 0
                    for index, v in enumerate([a[0], b[0], c[0]]):
                        if ma==v:
                            ps+=rec[index][1]
                    # print(ps)
                    # if i==1 and j==2: print(a, b, c, ma)
                    dp[i][j] = [ma+score, ps]
        # for i in dp: print(i)
        return [dp[-1][-1][0]%mod, dp[-1][-1][1]%mod] if dp[-1][-1][0]!=-1 else [0, 0]
                    

展开全部 8 讨论