LeetCode周赛 220

本文主要是介绍LeetCode周赛 220，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

5629. 重新格式化电话号码

给你一个字符串形式的电话号码 number 。number 由数字、空格 ’ '、和破折号 ‘-’ 组成。

请你按下述方式重新格式化电话号码。

首先，删除所有的空格和破折号。
其次，将数组从左到右每 3 个一组分块，直到剩下 4 个或更少数字。剩下的数字将按下述规定再分块：
2 个数字：单个含 2 个数字的块。
3 个数字：单个含 3 个数字的块。
4 个数字：两个分别含 2 个数字的块。
最后用破折号将这些块连接起来。注意，重新格式化过程中不应该生成仅含 1 个数字的块，并且最多生成两个含 2 个数字的块。

返回格式化后的电话号码。

示例 1：

输入：number = “1-23-45 6”
输出：“123-456”
解释：数字是 “123456”
步骤 1：共有超过 4 个数字，所以先取 3 个数字分为一组。第 1 个块是 “123” 。
步骤 2：剩下 3 个数字，将它们放入单个含 3 个数字的块。第 2 个块是 “456” 。
连接这些块后得到 “123-456” 。
示例 2：

输入：number = “123 4-567”
输出：“123-45-67”
解释：数字是 “1234567”.
步骤 1：共有超过 4 个数字，所以先取 3 个数字分为一组。第 1 个块是 “123” 。
步骤 2：剩下 4 个数字，所以将它们分成两个含 2 个数字的块。这 2 块分别是 “45” 和 “67” 。
连接这些块后得到 “123-45-67” 。
示例 3：

输入：number = “123 4-5678”
输出：“123-456-78”
解释：数字是 “12345678” 。
步骤 1：第 1 个块 “123” 。
步骤 2：第 2 个块 “456” 。
步骤 3：剩下 2 个数字，将它们放入单个含 2 个数字的块。第 3 个块是 “78” 。
连接这些块后得到 “123-456-78” 。
示例 4：

输入：number = “12”
输出：“12”
示例 5：

输入：number = "–17-5 229 35-39475 "
输出：“175-229-353-94-75”

提示：

2 <= number.length <= 100
number 由数字和字符 ‘-’ 及 ’ ’ 组成。
number 中至少含 2 个数字。

思路：
按照 $\mod 3=0,1,2$ 的情况分类讨论就好了。

class Solution {
public:string reformatNumber(string number) {string ans;for(int i = 0;i < number.length();i++) {if(number[i] == ' ' || number[i] == '-') {continue;}ans = ans + number[i];}string res;int cnt = 0;if(ans.length() % 3 == 0) {for(int i = 0;i < ans.length();i++) {cnt++;res = res + ans[i];if(cnt % 3 == 0 && i != ans.length() - 1) {res = res + "-";}}} else if(ans.length() % 3 == 1) {for(int i = 0;i < ans.length() - 4;i++) {cnt++;res = res + ans[i];if(cnt % 3 == 0) {res = res + "-";}}res = res + ans.substr(ans.length() - 4,2) + "-" + ans.substr(ans.length() - 2,2);} else {for(int i = 0;i < ans.length() - 2;i++) {cnt++;res = res + ans[i];if(cnt % 3 == 0) {res = res + "-";}}res = res + ans.substr(ans.length() - 2,2);}return res;}
};

5630. 删除子数组的最大得分

给你一个正整数数组 nums ，请你从中删除一个含有若干不同元素的子数组。删除子数组的得分就是子数组各元素之和。

返回只删除一个子数组可获得的最大得分。

如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],…,a[r] ，那么它就是 a 的一个子数组。

示例 1：

输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 [2,4,5,6]
示例 2：

输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 104

思路：
就用 $m a p$ 维护每个数上一次出现的位置就好了

int sum[100005];
class Solution {
public:map<int,int>mp;int maximumUniqueSubarray(vector<int>& nums) {int n = nums.size();int pre = 0;int ans = 0;for(int i = 1;i <= n;i++) {sum[i] = sum[i - 1] + nums[i - 1];pre = max(pre,mp[nums[i - 1]]);mp[nums[i - 1]] = i;ans = max(ans,sum[i] - sum[pre]);}return ans;}
};

5631. 跳跃游戏 VI

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含两个端点的任意位置。

你的目标是到达数组最后一个位置（下标为 n - 1 ），你的得分为经过的所有数字之和。

请你返回你能得到的最大得分。

示例 1：

输入：nums = [1,-1,-2,4,-7,3], k = 2
输出：7
解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。
示例 2：

输入：nums = [10,-5,-2,4,0,3], k = 3
输出：17
解释：你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。
示例 3：

输入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
输出：0

思路：
转移方程特别明显 $f [i] = m a x (f [j]) + n u m s [i] ， i - k \leq j \leq i - 1$
直接打了个线段树来维护这个方程

const int maxn = 1e5 + 7;
const int INF = 0x3f3f3f3f;
struct Node {int l,r;int mx;
}t[maxn << 2];
int f[maxn];
void pushup(int i) {t[i].mx = max(t[i * 2].mx,t[i * 2 + 1].mx);
}
void build(int i,int l,int r) {t[i].l = l;t[i].r = r;t[i].mx = -INF;if(l == r) {return;}int m = (l + r) >> 1;build(i * 2,l,m);build(i * 2 + 1,m + 1,r);
}
int query(int i,int l,int r) {if(l <= t[i].l && t[i].r <= r) {return t[i].mx;}int m = (t[i].l + t[i].r) >> 1;int mx = -INF;if(l <= m) mx = max(mx,query(i * 2,l,r));if(r > m) mx = max(mx,query(i * 2 + 1,l,r));return mx;
}
void update(int i,int x,int v) {if(t[i].l == t[i].r) {t[i].mx = v;return;}int m = (t[i].l + t[i].r) >> 1;if(x <= m) update(i * 2,x,v);if(x > m) update(i * 2 + 1,x,v);pushup(i);
}
class Solution {
public:int maxResult(vector<int>& nums, int k) {f[1] = nums[0];build(1,1,nums.size());update(1,1,f[1]);for(int i = 2;i <= nums.size();i++) {int l = max(1,i - k);f[i] = query(1,l,i - 1) + nums[i - 1];update(1,i,f[i]);}return f[nums.size()];}
};

5632. 检查边长度限制的路径是否存在

给你一个 n 个点组成的无向图边集 edgeList ，其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边。请注意，两个点之间可能有超过一条边。

给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj] ，你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径，且这条路径上的每一条边都严格小于 limitj 。

请你返回一个布尔数组 answer ，其中 answer.length == queries.length ，当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false 。

示例 1：

输入：n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
输出：[false,true]
解释：上图为给定的输入数据。注意到 0 和 1 之间有两条重边，分别为 2 和 16 。
对于第一个查询，0 和 1 之间没有小于 2 的边，所以我们返回 false 。
对于第二个查询，有一条路径（0 -> 1 -> 2）两条边都小于 5 ，所以这个查询我们返回 true 。
示例 2：

输入：n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
输出：[true,false]
解释：上图为给定数据。

提示：

2 <= n <= 105
1 <= edgeList.length, queries.length <= 105
edgeList[i].length == 3
queries[j].length == 3
0 <= ui, vi, pj, qj <= n - 1
ui != vi
pj != qj
1 <= disi, limitj <= 109
两个点之间可能有多条边。

思路：
最小生成树中两点路径就对应边权值最大最小的路径，只要判断这个路径上最大边是否大于等于 $l i m i t$ 就好了。
判断的过程使用 $l c a$ 倍增来判断。

ps:中间把函数遍历开在外面，一直报栈错误，吐了。。。记住，一定要把函数写在class里面！class里面的数组有时候也需要初始化（有的这种类型的oj需要初始化）。

const int maxn = 1e5 + 4;struct Edge {int x,y,z;
}a[maxn];
int cmp(Edge a,Edge b) {return a.z < b.z;
}
class Solution {
public:int fa[maxn];int findset(int x) {if(fa[x] == x) return fa[x];return fa[x] = findset(fa[x]);}void Union(int x,int y) {int rx = findset(x),ry = findset(y);if(rx != ry) {fa[rx] = ry;}}int f[maxn][20],d[maxn],mx[maxn][20];vector<pair<int,int>>G[maxn];void dfs(int x,int fa) {for(int i = 0;i < G[x].size();i++) {int v = G[x][i].first,w = G[x][i].second;if(v == fa) continue;d[v] = d[x] + 1;f[v][0] = x;mx[v][0] = w;dfs(v,x);}}int lca(int x,int y) {if(d[x] < d[y]) swap(x,y);int res = 0;for(int i = 19;i >= 0;i--) {if(d[f[x][i]] >= d[y]) {res = max(res,mx[x][i]);x = f[x][i];}}if(x == y) return res;for(int i = 19;i >= 0;i--) {if(f[x][i] != f[y][i]) {res = max(res,mx[x][i]);res = max(res,mx[y][i]);x = f[x][i];y = f[y][i];}}res = max(res,max(mx[x][0],mx[y][0]));return res;}vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {for(int i = 0;i < edgeList.size();i++) {int x = edgeList[i][0],y = edgeList[i][1],z = edgeList[i][2];x++,y++;a[i + 1] = {x,y,z};}for(int i = 1;i <= n;i++) fa[i] = i;sort(a + 1,a + 1 + edgeList.size(),cmp);int cnt = 0;for(int i = 1;i <= edgeList.size();i++) {int x = a[i].x,y = a[i].y,z = a[i].z;int rx = findset(x), ry = findset(y);if(rx != ry) {Union(rx,ry);cnt++;G[x].push_back({y,z});G[y].push_back({x,z});}if(cnt >= n - 1) break;}for(int i = 1;i <= n;i++) {if(i == findset(i)) {dfs(i,-1);}}for(int i = 1;i <= 19;i++) {for(int j = 1;j <= n;j++) {f[j][i] = f[f[j][i - 1]][i - 1];mx[j][i] = max(mx[j][i - 1],mx[f[j][i - 1]][i - 1]);}}vector<bool>ans;for(int i = 0;i < queries.size();i++) {int x = queries[i][0],y = queries[i][1],limit = queries[i][2];x++;y++;if(findset(x) != findset(y)) {ans.push_back(false);continue;}int mx = lca(x,y);// printf("DEBUG %d %d %d %d\n",x,y,mx,limit);if(mx < limit) {ans.push_back(true);} else {ans.push_back(false);}}return ans;}
};