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

题解

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

倒着扫一遍维护后缀最大值即可。这个属于基本功,时间复杂度 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
展开全部 8 讨论