LeetCode 第 220 场周赛 题解及思路

LeetCode 第 220 场周赛 题解及思路

• • 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 账号。