​

0. 赛后总结这次的比赛结果略惨，只做出3题，然后国内才只有229/3690，世界则是667/9606，都是只有前7%的水平。

但是这次的题目应该算是比较简单的，看了一下，第一名的大佬只花了不到10分钟就搞定了，而我没有做出来的最后一题，事实上就是一个DSU的问题，之前我也专门写博客聊过这个算法（Python笔记：并查集（DSU）结构简介），然而在比赛中还是没有搞出来。

倒不是完全没有想到过使用DSU，但是终究还是想岔了，没能想到正确的使用方法，导致最后一题没有做出来，不过这个后面再谈吧，唉。。。

1. 题目一给出题目一的试题链接如下：

5629. 重新格式化电话号码1. 解题思路这一题挺直接的，解题思路上就是先去掉空格和-字符，然后按照3个数字为一组进行分割，知道最后几位进行特殊处理即可。

2. 代码实现给出python代码实现如下：

代码语言：javascript复制class Solution:

def reformatNumber(self, number: str) -> str:

number = number.replace("-", "").replace(" ", "")

n = len(number)

res = []

idx = 0

while idx < n-4:

res.append(number[idx:idx+3])

idx += 3

if n - idx == 4:

res.extend([number[idx:idx+2], number[idx+2:idx+4]])

else:

res.append(number[idx:])

return "-".join(res)提交代码评测得到：耗时36ms，占用内存14.1MB。

当前的最优算法耗时28ms，但看了一下思路是一致的，因此这里就不过多展开了。

2. 题目二给出题目二的试题链接如下：

5630. 删除子数组的最大得分1. 解题思路这一题的思路其实还是蛮明确的，就是维护一个滑动窗口，确保窗口中不会存在重复的元素。

2. 代码实现给出python代码实现如下：

代码语言：javascript复制class Solution:

def maximumUniqueSubarray(self, nums: List[int]) -> int:

i, j, n = 0, 0, len(nums)

counter = defaultdict(int)

ans = 0

score = 0

while j < n:

while i < j and counter[nums[j]] == 1:

score -= nums[i]

counter[nums[i]] -= 1

i += 1

while j < n and counter[nums[j]] == 0:

score += nums[j]

counter[nums[j]] += 1

j += 1

ans = max(ans, score)

return ans提交代码评测得到：耗时1380ms，占用内存28.4MB。

当前的最优算法耗时792ms，但是看了一下，他们的算法思路和我们是相同的，因此这里就不过多展开了。

3. 题目三给出题目三的试题链接如下：

5631. 跳跃游戏 VI1. 解题思路这一题的思路就是使用动态规划算法。

他的递推关系还是非常明确的，可以给出递推关系如下：

代码语言：txt复制 f ( i ) = n i + m a x ( f ( j ) ) ( i < j ≤ i + k ) f(i) = n\_i + max(f(j)) \ (i< j \leq i+k) f(i)=ni​+max(f(j)) (i

2. 代码实现我们直接给出python代码实现如下：

代码语言：javascript复制class Solution:

def maxResult(self, nums: List[int], k: int) -> int:

n = len(nums)

dp = [k for k in nums]

q = [(nums[-1], n-1)]

for i in range(n-2, -1, -1):

while q != [] and q[-1][1] > i + k:

q.pop()

dp[i] += q[-1][0]

while q != [] and q[0][0] < dp[i]:

q.pop(0)

q.insert(0, (dp[i], i))

return dp[0]提交代码评测得到：耗时828ms，占用内存27.8MB。

当前最优的代码实现耗时704ms，但是看了一下他们的思路和我们是完全一致的，因此这里就不多做展开了。

4. 题目四给出题目四的试题链接如下：

5632. 检查边长度限制的路径是否存在1. 解题思路这题比赛的时候没做出来真的是太伤了，赛后看了一下awice大神的解答，发现我没做出来真的是太菜了。

这题的思路其实挺直白的，显然由于n最大可以取到 1 0 5 10^5 105，因此要求的算法复杂度肯定不能超过 O ( N 2 ) O(N^2) O(N2)，最好只有 O ( N ) O(N) O(N)，那么一个直接的思路就是使用DSU（这部分内容的说明可以参考我们之前的博客：Python笔记：并查集（DSU）结构简介）。

到这里事实上比赛的时候我们也想到了，但是具体的实现上却犯了难，因为他事实上只允许使用有限的边，是要返回两个点的所有连通方案中的最小实现方案中的最大边长，而DSU只能够反应聚合关系以及整个聚类的一些特征，而无法反应其中更小的集合的关系，因此比赛的时候就没有想出来，当然，这个后续可以通过其他方式绕开，我们等会再说。

然后另外一种思路就是使用动态规划，将历史计算结果全部保存在缓存当中，从而优化执行效果，这个是我比赛的时候的思路，但是遇到的问题就是怎么存储状态，然后你懂的，不到南墙不回头，死的不能更惨，唉。。。

我们回过头来重新说说正确的使用dsu的方法吧。

问题如果简化到对于某一个具体的query，事实上我们只要使用边长小于limit的边进行dsu的构建即可。因此，我们就可以很简单的使用dsu进行解答，但是，问题在于对于每一个query，我们都要针对limit进行一次dsu的构建，这个就会非常复杂，必然会带来超时问题。

但是，如果我们实现对query针对limit进行排序的话，那么，我们事实上就不需要每次都进行dsu的构建了，只要全局的构建一个dsu结构就能够解决这个问题了。

2. 代码实现我们给出具体的python代码实现如下：

代码语言：javascript复制class DSU:

def __init__(self, n):

self.dsu = [i for i in range(n)]

def find(self, x):

if self.dsu[x] != x:

self.dsu[x] = self.find(self.dsu[x])

return self.dsu[x]

def union(self, x, y):

x = self.find(x)

y = self.find(y)

if x != y:

self.dsu[y] = x

return

class Solution:

def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:

edges = sorted(edgeList, key=lambda x: x[2])

queries = sorted([(idx, u, v, limit) for idx, (u, v, limit) in enumerate(queries)], key=lambda x: x[-1])

m = len(edges)

res = [False for _ in queries]

i = 0

dsu = DSU(n)

for idx, u, v, limit in queries:

while i < m and edges[i][2] < limit:

p, q, _ = edges[i]

dsu.union(p, q)

i += 1

res[idx] = (dsu.find(u) == dsu.find(v))

return res提交代码评测得到：耗时2028ms，占用内存61.2MB。

当前最优的代码实现耗时1812ms，但是看了一下同样是采用dsu方式进行的实现，因此这里就不过多进行展开了。