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

这题用动态规划做还是比较明显的,第一问有点类似动态规划的经典入门题 数字三角形 。熟悉动态规划的话转移方程的话比较容易想到

对于统计方案数,我们需要记录上面方程的转移过程,在转移的时候更新方案数。

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

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};
}
};