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

今天的题目好简单,WA 一次会严重影响成绩啊!难受的一晚,睡觉😴


5134. 将每个元素替换为右侧最大元素

反向记录当前状态的最大值就行了。遍历一次即可

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        res = arr[-1]
        dp = [0] * len(arr)
        dp[-1] = -1
        for i in range(len(arr) - 2, -1, -1):
            dp[i] = max(res, arr[i + 1])
            res = max(res, arr[i])
        return dp     

5135. 转变数组后最接近目标值的数组和

典型的最小化最大值的二分问题。先确定二分的上下界,下界肯定是 0,由于是大于 value 则下降成 value,所以上界是数组最大值。根据题意发现情况和是和 value 单调递增的,符合二分规律。按题意写个二分即可。

发现 n 的范围是 10^4,其实 10^7 感觉都能过。如果不懂这个 Min-Max 的二分类型题,可以看我公众号的文章:《二分搜索不仅仅是查找值(下)》。

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        def sol(val):
            res = 0
            for i in arr:
                if i > val:
                    res += val
                else:
                    res += i    
            return res        
            
        l, r = 0, max(arr)
        while l <= r:
            mid = l + (r - l) // 2
            tt = sol(mid)
            if tt == target:
                return mid
            elif tt > target:
                r = mid - 1
            else:
                l = mid + 1    
        a, b = sol(l), sol(r)        
        return l if abs(a - target) < abs(b - target) else r

5153. 层数最深叶子节点的和

很水的一题,DFS 一遍搜出每一层所有的节点,然后最深层求和就行了。这题不应该是 Easy 吗🤦‍♂️ ️

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.dp = {}
        
    def dfs(self, rt, cnt):
        cur = self.dp.get(cnt, [])
        cur.append(rt.val)
        self.dp[cnt] = cur
        if rt.left is not None:
            self.dfs(rt.left, cnt + 1) 
        if rt.right is not None:
            self.dfs(rt.right, cnt + 1)    
        
    def deepestLeavesSum(self, root: TreeNode) -> int:
        if root is None:
            return 0
        self.dp = {}
        self.dfs(root, 0)
        md = max(self.dp.keys())
        return sum(self.dp[md])

5137. 最大得分的路径数目

又是一道很简单的 dp,正着走反着走都可以,为了好写代码就从左上到右下走就好。次数和最大值用两个数组装着就好了。两个很简单的状态转移:

dp(i,j)=max(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+board(i,j)dp(i, j) = max(dp(i - 1, j), dp(i - 1, j - 1), dp(i, j - 1)) + board(i, j)

个数记录是通过每次遍历之后,如果 dp[i][j] 与上一状态 + 当前位置值的结果相同的时候,次数就加上上一状态的次数即可。

cc(i,j)=cc(i−1,j)+cc(i,j−1)+cc(i−1,j−1)cc(i, j) = cc(i - 1, j) + cc(i, j - 1) + cc(i - 1, j - 1)

class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        dp = [[0] * len(board[0]) for _ in range(0, len(board))]
        cc = copy.deepcopy(dp)
        cc[0][0] = 1
        MOD = 10 ** 9 + 7
        for j in range(1, len(board[0])):
            if board[0][j] != 'X' and dp[0][j - 1] >= 0:
                dp[0][j] = dp[0][j - 1] + int(board[0][j])
                cc[0][j] = 1
            else:
                dp[0][j] = -1 
        for i in range(1, len(board)):
            if board[i][0] != 'X' and dp[i - 1][0] >= 0:
                dp[i][0] = dp[i - 1][0] + int(board[i][0])
                cc[i][0] = 1
            else:
                dp[i][0] = -1    
        for i in range(1, len(board)):
            for j in range(1, len(board[0])):
                if board[i][j] == 'X':
                    dp[i][j] = -1
                    continue
                cur = int(board[i][j]) if board[i][j] != 'S' else 0 
                dp[i][j] = cur + max(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1])    
                if dp[i][j] == cur + dp[i - 1][j]:
                    cc[i][j] += cc[i - 1][j]
                if dp[i][j] == cur + dp[i - 1][j - 1]:
                    cc[i][j] += cc[i - 1][j - 1]
                if dp[i][j] == cur + dp[i][j - 1]:
                    cc[i][j] += cc[i][j - 1]    
        #print(dp)
        if dp[-1][-1] < 0:
            return [0, 0]            
                    
        return [dp[-1][-1] % MOD, max(cc[-1][-1] % MOD, 0)]
7
展开全部 8 讨论