LeetCode 第 16 场双周赛（402/822，前48.9%）
LeetCode 第 16 场双周赛（402/822，前48.9%）
Michael阿明
发布于 2020-07-13 17:10:33
发布于 2020-07-13 17:10:33
文章被收录于专栏：Michael阿明学习之路
1. 比赛结果
做出了2道题，第二道题耽搁时间有点长，放弃了，第四题在时间到了后一会就做出来了。
在这里插入图片描述
在这里插入图片描述
2. 题目
LeetCode 1299. 将每个元素替换为右侧最大元素 easy
给你一个数组 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
解题： 从后往前遍历，记录当前的最大值。
class Solution {
public:
vector<int> replaceElements(vector<int>& arr) {
int m = arr.back(), origin;
arr.back() = -1;
for(int i = arr.size()-2; i >= 0; --i)
{
origin = arr[i];//记录原始数据
arr[i] = m;//右侧的最大值填入
m = max(m, origin);//更新最大值
}
return arr;
}
};LeetCode 1300. 转变数组后最接近目标值的数组和 medium
LeetCode 1302. 层数最深叶子节点的和 medium
给你一棵二叉树，请你返回层数最深的叶子节点的和。
在这里插入图片描述
输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8] 输出：15 提示： 树中节点数目在 1 到 10^4 之间。 每个节点的值在 1 到 100 之间。
解题：按层遍历即可
class Solution {
public:
int deepestLeavesSum(TreeNode* root) {
queue<TreeNode*> q;
int sum, n;
q.push(root);
while(!q.empty())
{
n = q.size();
sum = 0;
while(n--)
{
sum += q.front()->val;
if(q.front()->left)
q.push(q.front()->left);
if(q.front()->right)
q.push(q.front()->right);
q.pop();
}
}
return sum;
}
};LeetCode 1301. 最大得分的路径数目 hard
给你一个正方形字符数组 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二维数组存储一个pair（得分，方案数）
class Solution {
int n, i, j;
public:
vector<int> pathsWithMaxScore(vector<string>& board) {
n = board.size();
board[0][0] = board[n-1][n-1] = '0';//方便后面处理起点和终点的得分
vector<vector<pair<int,int>>> dp(n,vector<pair<int,int>> (n, make_pair(0,0)));
dp[n-1][n-1].second = 1;//起点的方案数为1
for(i = n-2; i >= 0 && board[i][n-1] != 'X'; --i)
{ //初始化最后1列
dp[i][n-1].first = dp[i+1][n-1].first+board[i][n-1]-'0';//得分累加
dp[i][n-1].second = 1;//方案数只有1种
}
for(i = n-2; i >= 0 && board[n-1][i] != 'X'; --i)
{ //初始化最后1行
dp[n-1][i].first = dp[n-1][i+1].first+board[n-1][i]-'0';
dp[n-1][i].second = 1;
}
for(i = n-2; i >= 0; i--)
{
for(j = n-2; j >= 0; j--)
{ //填写其他dp数组
if(board[i][j] != 'X')//没有障碍
{
if(dp[i+1][j+1].second)//右下角 如果有方案数，则可以过来
{
if(dp[i+1][j+1].first+board[i][j]-'0' > dp[i][j].first)//得分大，更新得分，方案数
{
dp[i][j].first = dp[i+1][j+1].first+board[i][j]-'0';
dp[i][j].second = dp[i+1][j+1].second%1000000007;
}
else if(dp[i+1][j+1].first+board[i][j]-'0' == dp[i][j].first)//得分相等，方案数相加
{
dp[i][j].second += dp[i+1][j+1].second%1000000007;
}
}
if(dp[i][j+1].second)//右边
{
if(dp[i][j+1].first+board[i][j]-'0' > dp[i][j].first)
{
dp[i][j].first = dp[i][j+1].first+board[i][j]-'0';
dp[i][j].second = dp[i][j+1].second%1000000007;
}
else if(dp[i][j+1].first+board[i][j]-'0' == dp[i][j].first)
{
dp[i][j].second += dp[i][j+1].second%1000000007;
}
}
if(dp[i+1][j].second)//下边
{
if(dp[i+1][j].first+board[i][j]-'0' > dp[i][j].first)
{
dp[i][j].first = dp[i+1][j].first+board[i][j]-'0';
dp[i][j].second = dp[i+1][j].second%1000000007;
}
else if(dp[i+1][j].first+board[i][j]-'0' == dp[i][j].first)
{
dp[i][j].second += dp[i+1][j].second%1000000007;
}
}
}
}
}
return {dp[0][0].first, dp[0][0].second%1000000007};//得分，方案数
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/12/29 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
