讨论/题目交流/🐱 第 16 场夜喵双周赛/
🐱 第 16 场夜喵双周赛
展开讨论
力扣 (LeetCode)发起于 2019-12-28
最近编辑于 2019-12-28

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
展开全部 8 讨论