On the shoulders of giants.

biweekly-contest-16

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

给你一个数组 arr ,请你将每个元素用它右边最大的元素替换,如果是最后一个元素,用 -1 替换。

完成所有替换操作后,请你返回这个数组。

示例:

输入:arr = [17,18,5,4,6,1]
输出:[18,6,6,6,1,-1]

提示:

  • 1 <= arr.length <= 10^4
  • 1 <= arr[i] <= 10^5
题解

从后往前维护最大值。

时间复杂度:\(O(n)\)

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

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

给你一个整数数组 arr 和一个目标值 target ,请你返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近  target (最接近表示两者之差的绝对值最小)。

如果有多种使得和最接近 target 的方案,请你返回这些整数中的最小值。

请注意,答案不一定是 arr 中的数字。

示例 1:

输入:arr = [4,9,3], target = 10
输出:3
解释:当选择 value 为 3 时,数组会变成 [3, 3, 3],和为 9 ,这是最接近 target 的方案。

示例 2:

输入:arr = [2,3,5], target = 10
输出:5

示例 3:

输入:arr = [60864,25176,27249,21296,20204], target = 56803
输出:11361

提示:

  • 1 <= arr.length <= 10^4
  • 1 <= arr[i], target <= 10^5
题解

无脑的二分,以 target 值为界,跑两次二分,然后求代价最小。

时间复杂度:\(O(n\log n)\)

class Solution {
public:
    int solve(vector<int>& arr, int key) {
        int sum = 0;
        
        for(auto x : arr) {
            sum += (key < x ? key : x);
        }
        
        return sum;
    }
    
    int findBestValue(vector<int>& arr, int target) {
        const int INF = 1E5 + 5;
        int lef, rig, mid, result, Max = -INF;
        
        for(auto x : arr) {
            Max = max(Max, x);
        }
        
        lef = 0, rig = Max;
        while(lef < rig) {
            mid = lef + rig + 1 >> 1;
            if(solve(arr, mid) <= target) lef = mid;
            else rig = mid - 1;
        }
        result = lef;
        
        lef = 0, rig = Max;
        while(lef < rig) {
            mid = lef + rig >> 1;
            if(target <= solve(arr, mid)) rig = mid;
            else lef = mid + 1;
        }
        
        // cout << result << " , " << rig << endl;
        if(target - solve(arr, result) > solve(arr, rig) - target) {
            result = rig;
        }
        
        return result;
    }
};

层数最深叶子节点的和

给你一棵二叉树,请你返回层数最深的叶子节点的和。

示例:

输入:root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
输出:15

提示:

  • 树中节点数目在 1 到 10^4 之间。
  • 每个节点的值在 1 到 100 之间。
题解

深度遍历,维护最大深度,更新总和。

时间复杂度:\(O(\log n)\)

/**
 * 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 {
public:
    int result, maxDep;
    
    void dfs(TreeNode* root, int dep) {
        if(root == NULL) return;
        if(maxDep < dep) {
            result = root->val;
            maxDep = dep;
        } else if(maxDep == dep) {
            result += root->val;
        }
        dfs(root->left, dep + 1);
        dfs(root->right, dep + 1);
    }
    
    int deepestLeavesSum(TreeNode* root) {
        dfs(root, 1);
            
        return result;
    }
};

最大得分的路径数目

给你一个正方形字符数组 board ,你从数组最右下方的字符 'S' 出发。

你的目标是到达数组最左上角的字符 'E' ,数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X'。在每一步移动中,你可以向上、向左或者左上方移动,可以移动的前提是到达的格子没有障碍。

一条路径的 「得分」 定义为:路径上所有数字的和。

请你返回一个列表,包含两个整数:第一个整数是 「得分」 的最大值,第二个整数是得到最大得分的方案数,请把结果对 10^9 + 7 取余

如果没有任何路径可以到达终点,请返回 [0, 0]

示例 1:

输入:board = ["E23","2X2","12S"]
输出:[7,1]

示例 2:

输入:board = ["E12","1X1","21S"]
输出:[4,2]

示例 3:

输入:board = ["E11","XXX","11S"]
输出:[0,0]

提示:

  • 2 <= board.length == board[i].length <= 100
题解

动态规划:设

\(dp_{i,j}\) 为到达 \((i,j)\) 时的最大值;

\(f_{i,j}\) 为到达 \((i,j)\) 时值是最大值的个数。

习惯上,可以从左上到右下遍历。

在合法的情况下,\(dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1},dp_{i-1,j-1})\) ;

当某一个上一状态与最优状态的最大值一样时,\(f_{i,j}=(f_{i-1,j}+f_{i,j-1}+f_{i-1,j-1})\% mod\)

时间复杂度:\(O(nm)\)

class Solution {
public:
    const int dt[2][3] = {{0, -1, -1}, {-1, 0, -1}};
    const int MOD = 1E9 + 7;
    int n, m;

    bool check(int x, int y) {
        return (x < 0 || n <= x || y < 0 || m <= y);
    }

    vector<int> pathsWithMaxScore(vector<string>& board) {
        n = board.size(), m = board[0].size();
        vector<vector<int>> dp(n, vector<int> (m, -1));
        vector<vector<int>> f(n, vector<int> (m, 0));
        vector<int> result;

        dp[0][0] = 0, f[0][0] = 1;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == 'X') continue;
                for(int k = 0; k < 3; k++) {
                    int dx = i + dt[0][k], dy = j + dt[1][k];
                    if(check(dx, dy) || board[dx][dy] == 'X') continue;
                    dp[i][j] = max(dp[i][j], dp[dx][dy]);
                }
                if(dp[i][j] == -1) continue;
                for(int k = 0; k < 3; k++) {
                    int dx = i + dt[0][k], dy = j + dt[1][k];
                    if(check(dx, dy) || board[dx][dy] == 'X') continue;
                    if(dp[i][j] == dp[dx][dy]) {
                        f[i][j] = (f[i][j] + f[dx][dy]) % MOD;
                    }
                }
                if(i + j == 0 || i + j == n + m - 2) continue;
                dp[i][j] += board[i][j] - '0';
            }
        }

        result.push_back(dp[n - 1][m - 1] == -1 ? 0 : dp[n - 1][m - 1]);
        result.push_back(f[n - 1][m - 1]);
        
        return result;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注