LeetCode笔记：Weekly Contest 220 比赛记录_实现 distancelimitedpathsexist 类

• LeetCode笔记：Weekly Contest 220
  • 0. 赛后总结
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现

0. 赛后总结

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

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

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

1. 题目一

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

• 5629. 重新格式化电话号码

1. 解题思路

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

2. 代码实现

给出python代码实现如下：

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

提交代码评测得到：耗时36ms，占用内存14.1MB。

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

2. 题目二

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

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

1. 解题思路

这一题的思路其实还是蛮明确的，就是维护一个滑动窗口，确保窗口中不会存在重复的元素。

2. 代码实现

给出python代码实现如下：

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

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

3. 题目三

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

• 5631. 跳跃游戏 VI

1. 解题思路

这一题的思路就是使用动态规划算法。

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

$$f(i)=n_i+max(f(j))(i<j\le i+k)$$

我们尝试了直接暴力地求解，但是这样的时间复杂度是$O(N\times K)$的，就会导致超时，但是这一题事实上可以参考上一周双周赛的最后一题的思路，使用一个有序队列进行处理，就可以将时间复杂度退化到$O(N)$，具体的算法说明可以参考我们上周的比赛记录（LeetCode笔记：Biweekly Contest 41 比赛记录），这里就不对具体的细节进行展开了。

2. 代码实现

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

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]
1
2
3
4
5
6
7
8
9
10
11
12
13

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

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

4. 题目四

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

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

1. 解题思路

这题比赛的时候没做出来真的是太伤了，赛后看了一下awice大神的解答，发现我没做出来真的是太菜了。

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

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

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

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

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

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

2. 代码实现

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

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

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