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

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

题目描述非常清楚,按照题意模拟即可。
需要注意的是,如果从右往左进行替换,那么查找右侧最大的的操作可以顺带着做,于是复杂度就变成 O(n)O(n)。

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int n = arr.size(), mx = -1;
        
        for(int i = n - 1; i >= 0; i--){
            int temp = arr[i];
            arr[i] = mx;
            mx = max(mx, temp);
        }
        
        return arr;
    }
};

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

观察可以发现,数组中数字的值域范围并不大,为 [1,105][1, 10^5]。同时,当 value 大于等于数组中的最大值,那么不会有任何替换发生,数组和不变,所以 value 大于 10510^5 是没有意义的。
那么,我们就可以枚举 value∈[0,105]value \in [0, 10^5],同时快速计算此时替换发生后的数组和。
快速计算的方法也很简单,我们只需要直到两个东西:大于 value 的数字数量,小于等于 value 的数字之和。那么,我们先将数组排序之后,从小到大枚举 value,就可以维护一个指针指向小于等于 value 和大于 value 的分界点,顺带计算需要的两个东西。
求得数组和之后,比较找一个最小合理的 value 即可。

class Solution {
public:
    long long Abs(long long x){
        if (x < 0) return -x;
        return x;
    }
    
    int findBestValue(vector<int>& arr, int target) {
        int n = arr.size();
        
        long long sum = 0;
        int ans = 0;
        long long delta = 2e9;
        sort(arr.begin(), arr.end());
        
        for (int i = 0, j = 0; i <= 100000; i++){
            while(j < n && arr[j] <= i) sum += arr[j++];
            long long cur = sum + 1LL * i * (n - j);
            if (Abs(cur - target) < delta){
                ans = i; delta = Abs(cur - target);
            }
        }
        
        return ans;
    }
};

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

考你怎么遍历一颗二叉树……不能多说了

class Solution {
public:
    
    int mx_dep, ans;
    
    void dfs(TreeNode* root, int dep, bool sum){
        if (root == NULL) return;
        mx_dep = max(dep, mx_dep);
        if (sum && mx_dep == dep) ans += root->val;
        dfs(root->left, dep+1, sum);
        dfs(root->right, dep+1, sum);
    }
    
    int deepestLeavesSum(TreeNode* root) {
        ans = mx_dep = 0;
        dfs(root, 1, false);
        dfs(root, 1, true);
        return ans;
    }
};

5137. 最大得分的路径数目

经典的动态规划题目,其实也可以看作是可以递推的计数题。递推方式和状态表示,其实在题目中已经写明。
dp[i][j]dp[i][j] 表示到了 (i,j)(i, j) 位置的最高得分, cnt[i][j]cnt[i][j] 表示 (i,j)(i, j) 在最高得分下的方案数量。
对于一个位置 (i,j)(i, j),可以向三个状态转移 (i−1,j)(i-1, j), (i,j−1)(i, j-1), (i−1,j−1)(i-1, j-1)(如果位置存在且不是障碍)。
转移的时候,从 A→BA \rightarrow B,首先尝试更新目标位置的 dp(B)dp(B) 值,如果新的值比原本的更大,那么更新值 dp(B)dp(B) 且之前的方案数 cnt(B)cnt(B) 清零(因为那是原来较小的路径和所对应的方案数)。接下来,如果值等于 dp(B)dp(B) 值,那么 cnt(B)+=cnt(A)cnt(B) += cnt(A),因为到 A 之后再走到 B 的所有路径均可以达到当前的最大值,所以计入目标位置的方案数。详情请看代码。

const int MOD = 1e9 + 7;
class Solution {
public:
    int dp[150][150], cnt[150][150];
    
    vector<int> pathsWithMaxScore(vector<string>& board) {
        int n = board.size(), m = board[0].length();
        memset(dp, 0, sizeof(dp));
        memset(cnt, 0, sizeof(cnt));
        
        cnt[n - 1][m - 1] = 1;
        board[0][0] = '0';
        for (int i = n - 1; i >= 0; i--){
            for (int j = m - 1; j >= 0; j--){
                if (cnt[i][j] == 0) continue;
                if (i > 0 && board[i - 1][j] != 'X'){
                    int v = dp[i][j] + (board[i - 1][j] - '0');
                    if (v > dp[i - 1][j]) dp[i - 1][j] = v, cnt[i - 1][j] = 0;
                    if (v == dp[i - 1][j]) cnt[i - 1][j] = (cnt[i - 1][j] + cnt[i][j]) % MOD;
                }
                if (j > 0 && board[i][j - 1] != 'X'){
                    int v = dp[i][j] + (board[i][j - 1] - '0');
                    if (v > dp[i][j - 1]) dp[i][j - 1] = v, cnt[i][j - 1] = 0;
                    if (v == dp[i][j - 1]) cnt[i][j - 1] = (cnt[i][j - 1] + cnt[i][j]) % MOD;
                }
                if (i > 0 && j > 0 && board[i - 1][j - 1] != 'X'){
                    int v = dp[i][j] + (board[i - 1][j - 1] - '0');
                    if (v > dp[i - 1][j - 1]) dp[i - 1][j - 1] = v, cnt[i - 1][j - 1] = 0;
                    if (v == dp[i - 1][j - 1]) cnt[i - 1][j - 1] = (cnt[i - 1][j - 1] + cnt[i][j]) % MOD;
                }
            }
        }
        
        return {dp[0][0], cnt[0][0]};
    }
};
2

题解

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

倒着扫一遍维护后缀最大值即可。这个属于基本功,时间复杂度 O(arr.size())O\left(arr.size()\right),不用多说。

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int n=arr.size();
        int cur=-1;
        for (int i=n-1;i>=0;--i){
            int tmp=max(cur,arr[i]);
            arr[i]=cur;
            cur=tmp;
        }
        return arr;
    }
};

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

二分+遍历。
需要观察到两个结论:

  • arr数组中数的出现顺序不影响答案
  • v的取值范围一定在 [0,105][0,10^5] 之间(想一想,为什么?)

因此,我们可以遍历每一个可能的 vv ,并统计出最好的 vv 是什么。然而我们需要用一种快速的方式算出数组和。

我们先做两件事情:

  • 将原数组从小到大排序
  • 设 n=arr.size()n=arr.size() , O(n)O\left(n\right) 维护出排序后数组的前缀和

这样,对于任意给定的 vv ,会存在一个下标 xx ,在 xx 之前的数都是原数,而在 xx 之后的数都是vv 。严格来说,xx 就是最后一个小于 vv 的数的下标。
因此,我们就可以使用二分法(或者lower_bound等)在对数时间复杂度内定位到 xx。则数组和恰为数组前 xx 项的前缀和以及剩下数的个数乘以v的和。

由此, O(n)O(n) 遍历每个可能的 vv ,O(log⁡(n))O(\log(n)) 判断出它是不是当前最优。总体时间复杂度为 O(n⋅log⁡(n))O(n \cdot \log(n)) 。

class Solution {
public:
    int findBestValue(vector<int>& a, int target) {
        sort(a.begin(),a.end());
        int n=a.size();
        int arr[n+10];
        int sum[n+10];
        sum[0]=a[0];
        arr[0]=a[0];
        for (int i=1;i<n;++i){
            sum[i]=sum[i-1]+a[i];
            arr[i]=a[i];
        }
        int bv=-1,bans=0x3f3f3f3f;
        for (int v=0;v<=100000;++v){
            int x=upper_bound(arr,arr+n,v)-arr;
            int cur=(x==0?0:sum[x-1])+(n-x)*v;
            if (abs(cur-target)<bans){
                bans=abs(cur-target);
                bv=v;
            }
        }
        return bv;
    }
};

层数最深叶子节点的和

简单题,使用任意深度优先遍历方法统计出最深的节点,以及它们的和即可。
在深度优先遍历的同时,维护两个值:当前最大深度以及当前最大深度对应的节点和。

  • 如果当前深度高于最大深度,则更新最大深度为当前深度,且当前和为当前节点值
  • 如果当前深度等于最大深度,则将当前和加上当前节点的值
  • 如果当前深度小于最大深度,则不更新。

在遍历完整棵树后,当前和就是你需要的答案。时间复杂度 O(节点个数))O(节点个数))

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int bd,cur;
    void dfs(TreeNode* rt,int p){
        if (rt->left) dfs(rt->left,p+1);
        if (rt->right) dfs(rt->right,p+1);
        if (p>bd){
            bd=p;
            cur=rt->val;
        }
        else if (p==bd){
            cur+=rt->val;
        }
    }
public:
    int deepestLeavesSum(TreeNode* root) {
        bd=-1,cur=0;
        if (!root) return 0;
        dfs(root,0);
        return cur;
    }
};

最大得分的路径数目

动态规划问题。

很容易发现每一个位置的最大和和路径数只与横纵坐标都不比它小的那些位置有关。
设

  • dp[u][v].xdp[u][v].x 表示从起点走到坐标 [u,v][u,v] 处最大的和;
  • dp[u][v].cntdp[u][v].cnt 表示从起点走到坐标 [u,v][u,v] 处能走到最大的和的方案数;

那么有

  • dp[n−1][m−1].x=0dp[n-1][m-1].x=0
  • dp[n−1][m−1].cnt=1dp[n-1][m-1].cnt=1

并且有

dp[u][v].x=max⁡(∑i=ui<n∑j=vj<mdp[i][j].x)+board[u][v]dp[u][v].x=\max{\left( \sum_{i=u}^{i<n} \sum_{j=v}^{j<m} dp[i][j].x \right)} + board[u][v]

dp[u][v].cnt=(∑i=ui<n∑j=vj<m{dp[i][j].cnt ,dp[u][v].x=dp[i][j].x+board[u][v]0, dp[u][v].x≠dp[i][j].x+board[u][v])dp[u][v].cnt=\left( \sum_{i=u}^{i<n} \sum_{j=v}^{j<m} \left\{\begin{matrix}dp[i][j].cnt\text{ },dp[u][v].x=dp[i][j].x+board[u][v] \\ 0,\text{ }dp[u][v].x\neq dp[i][j].x+board[u][v] \end{matrix}\right. \right)

因此,以 O(n4)O(n^4) 的复杂度从 [n−1,m−1][n-1,m-1] 位置处逐步更新到 [0,0][0,0] 即可。

typedef long long ll;
#define x first
#define cnt second
const ll inf=10000000;
const int mod=1e9+7;

class Solution {
    int n,m;
    int maze[110][110];
    pair<ll,ll> dp[110][110];

public:
    vector<int> pathsWithMaxScore(vector<string>& board) {
        n=board.size();
        m=board[0].size();
        for (int i=0;i<n;++i){
            for (int j=0;j<m;++j){
                if (board[i][j]>='0'&&board[i][j]<='9'){
                    maze[i][j]=board[i][j]-'0';
                }
                else if (board[i][j]=='S'||board[i][j]=='E'){
                    maze[i][j]=0;
                }
                else{
                    maze[i][j]=-inf;
                }
            }
        }
        for (int i=0;i<=n;++i){
            for (int j=0;j<=m;++j){
                dp[i][j]={-inf,0};
            }
        }
        dp[n-1][m-1]={0,1};
        for (int i=n-1;i>=0;--i){
            for (int j=m-1;j>=0;--j){
                if (i==n-1&&j==m-1) continue;
                dp[i][j].x=max({dp[i+1][j].x,dp[i][j+1].x,dp[i+1][j+1].x});
                dp[i][j].cnt=0;
                if (dp[i+1][j].x==dp[i][j].x){
                    dp[i][j].cnt+=dp[i+1][j].cnt;
                    dp[i][j].cnt%=mod;
                }
                if (dp[i][j+1].x==dp[i][j].x){
                    dp[i][j].cnt+=dp[i][j+1].cnt;
                    dp[i][j].cnt%=mod;
                }
                if (dp[i+1][j+1].x==dp[i][j].x){
                    dp[i][j].cnt+=dp[i+1][j+1].cnt;
                    dp[i][j].cnt%=mod;
                }
                dp[i][j].x+=maze[i][j];
                dp[i][j].x=max(-inf,dp[i][j].x);
            }
        }
        if (dp[0][0].x<0||dp[0][0].cnt==0){
            return {0,0};
        }
        return {dp[0][0].x,dp[0][0].cnt};
    }
};

Comment: 第四题成功看错题(+3) ,第二题lower_bound用炸公式推错,欢声笑语打出GG

1

感jio第二题比第三题难呀

今天出奇地简单,明天可能会被虐了。

感觉又刷新难度下限了...40分钟做完差点没进50...
一句话题解:

  1. 倒序遍历记录最大值即可
  2. 正常来讲这题是二分,但注意到target是所有元素的和并且不含负数,所以直接遍历0 ~ (target/size) 所有可能的值也一定不会超时。
  3. 先序遍历,开个数组记录每个节点的层数即可。
  4. dp。dp[i][j] = board[i][j] + max(dp[i+1][j],dp[i][j+1],dp[i+1][j+1]), 需要注意可以从右下向左上走(没看清,然后就wa了)

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]
                    

第二题坑了我蛮久的,但又不想用穷举,直到结束前才答出来。拿出来做个参考:

更新:这个解法发现是有错误的,正在考虑优化: 输入 [1,1,1,6,9], 18 时返回的是 7,正确应该是 9。


class Solution {
    public int findBestValue(int[] arr, int target) {
        int len = arr.length;
        int aimVal = getClosetVal(target, len);
        
        // 所有小于等于目标值的一定保留
        int sum = 0, size = 0;
        for(int val : arr) {
            if (val <= aimVal) {
                sum += val;
                size++;
            }
        }
        
        // 所有值都保留时(目标值大于等于整个数组和),取数组最大值
        if (len == size) {
            Arrays.sort(arr);
            return arr[arr.length - 1];
        }
        // 剩下的值重新计算最接近的取值即可
        return getClosetVal(target - sum, len - size);
    }
    
    // 计算 num 个值求和最接近 target 值时的取值
    private int getClosetVal(int target, int num) {
        return (target%num) > (num/2) ? target/num + 1 : target/num;
    }
}

今天的题目好简单,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