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

给你一个数组 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\)

Solution

从后往前扫描，并且记录最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        const int n = arr.size();
        int maxa = arr[n-1];
        arr[n-1] = -1;
        
        for (int i = n-2; i >= 0; i--) {
            int temp = arr[i];
            arr[i] = maxa;
            if (maxa < temp) maxa = temp;
        }
        return arr;
    }
};

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

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

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

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

示例 1：

输入：arr = [4,9,3], target = 10

输出：3

解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。

Solution

先排序，然后前缀和预处理 arr 数组，然后从 0 开始遍历答案，因为 arr 已经排序了，所以计算差异的时候使用二分。总的时间复杂度是 \(O(nlogn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
        const int n = arr.size();
        sort(arr.begin(), arr.end());
        
        int psum[n+1], r = -1;
        psum[0] = 0;
        for (int i = 1; i <= n; i++) {
            psum[i] = psum[i-1] + arr[i-1];
            r = max(r, arr[i-1]);
        }
        int diff = 100000000;
        
        for (int i = 0; i <= r+1; i++) {
            int pos = lower_bound(arr.begin(), arr.end(), i) - arr.begin();
            int temp = psum[pos]+(n-pos)*i;
            int last = diff;
            diff = abs(temp-target);
            
            if (diff >= last)
                return i-1;
        }
        return -1;
    }
};

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

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

Solution

BFS 遍历记录每一层椰子节点的和，遍历完成也就是最深的叶子结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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 deepestLeavesSum(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int sum;
        
        while (!q.empty()) {
            int n = q.size();
            sum = 0;
            for (int i = 0; i < n; i++) {
                TreeNode* top = q.front();
                q.pop();
                sum += top->val;
                if (top->left != NULL) q.push(top->left);
                if (top->right != NULL) q.push(top->right);
            }
        }
        return sum;
    }
};

5137. 最大得分的路径数目

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

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

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

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

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

示例 1：

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

Solution

这题用动态规划做还是比较明显的，第一问有点类似动态规划的经典入门题 数字三角形 。熟悉动态规划的话转移方程的话比较容易想到 \[ dp[i][j] = \max \{ dp[i-1][j-1], max \{ dp[i-1][k], dp[i][j-1] \} \} \quad i, j \in (0, n) \] 对于统计方案数，我们需要记录上面方程的转移过程，在转移的时候更新方案数。

注意一下边界的初始化以及走不通的情况判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    vector<int> pathsWithMaxScore(vector<string>& board) {
        const int n = board.size();
        const int mod = 1000000007;
        
        int dp[n+1][n+1];
        int dp1[n+1][n+1];
        memset(dp, 0, sizeof dp);
        memset(dp1, 0, sizeof dp1);
        dp1[0][0] = 1;
        board[n-1][n-1]= '0';
        for (int i = 1; i < n; i++) {
            if (board[0][i] != 'X') {
                dp[0][i] = dp[0][i-1]+board[0][i]-'0';
                dp1[0][i] = 1;
            } else break;
        }
        for (int i = 1; i < n; i++) {
            if (board[i][0] != 'X') {
                dp[i][0] = dp[i-1][0]+board[i][0]-'0';
                dp1[i][0] = 1;
            } else break;
        }
        
        for (int i = 1; i < n; i++)
            for (int j = 1; j < n; j++) {
                if (board[i][j] != 'X') {
                    int a = dp[i-1][j];
                    int b = dp[i-1][j-1];
                    int c = dp[i][j-1];
                    int temp = max(a, max(b, c));
                    dp[i][j] = temp+board[i][j]-'0';

                    if (temp == 0 && dp1[i-1][j] == 0 && dp1[i-1][j-1] == 0 && dp1[i][j-1] == 0) {
                        dp[i][j] = 0;
                        dp1[i][j] = 0;
                        continue;
                    }

                    if (a == temp) dp1[i][j] += dp1[i-1][j]%mod;
                    if (b == temp) dp1[i][j] += dp1[i-1][j-1]%mod;
                    if (c == temp) dp1[i][j] += dp1[i][j-1]%mod;
                }
            }
        // for (int i = 0; i < n; i++) {
        //     for (int j = 0; j < n; j++)
        //         printf("%d ", dp1[i][j]);
        //     printf("\n");
        // }
        //printf("%d\n", dp[n-1][n-1]);
        return {dp[n-1][n-1], dp1[n-1][n-1]%mod};
    }
};