- 1694. 重新格式化电话号码
- 1695. 删除子数组的最大得分
- 1696. 跳跃游戏 VI
- 1697. 检查边长度限制的路径是否存在
赛题传送门
1694. 重新格式化电话号码赛题
简要概况题目如下:
给定一个电话号码字符串
number
,由数字0-9
,空格' '
和破折号'-'
组成。要求输出 格式化 的电话号码。格式化要求:1. 删除所有非数字字符。2. 从左至右每 3 个一组,最后如果剩 4 个数字则变成每 2 个一组,否则最后少于等于 3 个数字独立为一组。3. 每组间用破折号'-'
连接。
简单题有简单题的做法,就是模拟,那就按照要求一个个来呗。首先我们筛选所有数字字符出来。
string nums;
for (const char& ch : number)
if ('0' <= ch && ch <= '9')
nums += ch;
然后每 3 个分为一组,并在后加上 '-'
。
int n = nums.size(), index = 0;
string ans;
while (index < n - 4) {
ans += nums.substr(index, 3) + "-";
index += 3;
};
注意最后 4 个字符特殊处理。
if (n - index == 4)
ans += nums.substr(index, 2) + "-" + nums.substr(index + 2, 2);
else if (index < n) ans += nums.substr(index);
else ans.pop_back(); // 抹掉最后一个字符 `-`
完整代码见 GitHub。
1695. 删除子数组的最大得分赛题
给你一个正整数数组
nums
,请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和。
返回 只删除一个 子数组可获得的 最大得分。
如果数组b
是数组a
的一个连续子序列,即如果它等于a[l], a[l + 1], ..., a[r]
,那么它就是a
的一个子数组。
提示
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4
翻译题目意思,就是找到一个元素和最大且不含有相同元素的连续子数组。由于 nums[i]
都是正整数,理论上来说,如果不要求不含相同元素的话,答案就是整个数组。
所以,我们不停地向后遍历并将当前元素加入子数组中,一旦碰到了重复元素,那么我们就得重复元素的上一个数组下标,并从那里开始继续计算。
具体地,我们用两个指针 last
和 next
来记录当前子数组的左右边界,并用哈希表 counts
记录子数组中元素出现的次数。
unordered_map counts;
int last = 0, next = 0, ans = 0, tmp = 0, n = nums.size();
然后将 next
指针往后遍历,并在 counts
中增加对应元素的出现次数,同时更新结果值 ans
。
while (next < n && !counts[nums[next]]) {
tmp += nums[next];
counts[nums[next]]++;
next++;
};
一旦碰上重复元素 nums[next]
,则需要移动 last
位置,直到 last
到 next
中 nums[next]
元素仅在 next
位置上出现。
while (last < n && counts[nums[next]]) {
tmp -= nums[last];
counts[nums[last]]--;
last++;
};
完整代码见 GitHub。
1696. 跳跃游戏 VI赛题
给你一个下标从 0 开始的整数数组
nums
和一个整数k
。
一开始你在下标0
处。每一步,你最多可以往前跳k
步,但你不能跳出数组的边界。也就是说,你可以从下标i
跳出[i + 1, min(n - 1, i + k)]
包含 两个端点的任意位置。
你的目标是到达数组最后一个位置(下标为n - 1
),你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分。
提示:
1 <= nums.length, k <= 10^5
-10^4 <= nums[i] <= 10^4
很容易想到使用 动态规划 来解决这个问题,dp[i]
代表以第 i
个元素为结尾元素的最大得分,则可以通过前 k 个元素跳过来,因此可以通过遍历 dp[i - 1]
至 dp[i - k]
的最大值并加上第 i
个元素值 nums[i]
来获得。
d p [ i ] = { n u m s [ 0 ] i = 0 n u m s [ i ] + max ( d p [ i − 1 ] , … , d p [ i − k ] ) i > 0 dp[i] = \begin{cases} nums[0] & i = 0 \\ nums[i] + \max(dp[i - 1], \dots, dp[i - k]) & i > 0 \\ \end{cases} dp[i]={nums[0]nums[i]+max(dp[i−1],…,dp[i−k])i=0i>0
但是这样的做法复杂度高达 O(nk)
,因此试图寻找可优化的空间,发现这个
k
k
k 次的遍历其实很多是重复的,所以我们完全可以用 优先级队列 来存储前
k
k
k 个的值,当然每次向后遍历的时候都要判断队首值是否符合下标条件,不符合就要d出队列。
同时,因为我们相当于用优先级队列去存储了每次遍历需要的值,因此可以抛弃 dp
这个数组,这样虽然空间复杂度也从 O(N)
降低到了 O(k)
。
具体地,我们定义结构体 node
来同时保存下标 index
和分数 score
。
struct node {
int index;
int score;
node() {};
node(int index, int score) : index(index), score(score) {};
bool operator>(const node& other) const {
return score < other.score;
};
};
我们用优先级队列 pque
来模拟,注意边界值(第一个值)的处理。这里我之前犯了一个小错误,就是我假设有个下标为 -1
分数为 0
的 node
然后正常遍历整个数组来更新 pque
,这样在某些条件下是不符合题意的,因为题目要求从下标 0 开始,而我这么做相当于可以从下标 0 至下标 (k - 1) 的任意位置开始。
priority_queue, greater > pque;
pque.push(node(0, nums[0]));
然后我们向后遍历更新来模拟上述过程。
for (int i = 1; i < n; i++) {
while (!pque.empty()) {
node top = pque.top();
if (i - top.index > k) pque.pop();
else {
node new_node = node(i, top.score + nums[i]);
pque.push(new_node);
break;
};
};
};
由于最后要停在下标为 n - 1 的位置,所以需要寻找 pque
中对应下标的 node
。
while (!pque.empty() && pque.top().index < n - 1) pque.pop();
return pque.top().score;
完整代码见 GitHub。
1697. 检查边长度限制的路径是否存在赛题
给你一个
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
。
这道题挺难的,我想过排序 queries
查询,但总觉得啊,图上的更新乱七八糟的,如果要求出每两个节点的路径中的最大值,那时间复杂度根本控制不住啊。
苦思冥想半天,于是找出了题解(因为这场竞赛我是事后做的虚拟竞赛),发现很巧妙。
首先将 edgeList
按照边值从小到大排序,再将 queries
按照 limit
从小到大排序,这样对于每个 query
都可以加入小于等于 limit
的边,然后去判断这个 query
对应的两个顶点是否连通,因此还需要用到 并查集。
核心代码逻辑就是:
for (int query: qid) {
// 将小于等于 `limit` 边的 `edge` 加入现在的图中
while (i < edgeList.size() && edgeList[i][2] < queries[query][2]) {
uf.unite(edgeList[i][0], edgeList[i][1]);
++i;
};
// 判断两个顶点的连通性作为结果
ans[query] = uf.connected(queries[query][0], queries[query][1]);
完整代码见 GitHub。
这周双周赛是我在 2022-4-19
号上午打的虚拟竞赛,虽然最后一题是看了题解写出来的,但我觉得,面对一道题,思考过五到十分钟但好没有好的思路时,可以去看题解并自己再做一遍啦,这样效率很高!我最近也在集中攻破 k8s
的虚拟 ip
和服务间通信,虽然忙但还是要坚持刷题!
好滴,以上就是力扣第 220 场周赛的全部思路啦。最后,欢迎关注我的 GitHub 账号。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)