- 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)
提交代碼評測得到：耗時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
提交代碼評測得到：耗時1380ms，占用記憶體28.4MB，
當前的最優演算法耗時792ms，但是看了一下，他們的演算法思路和我們是相同的，因此這里就不過多展開了，
3. 題目三
給出題目三的試題鏈接如下：
- 5631. 跳躍游戲 VI
1. 解題思路
這一題的思路就是使用動態規劃演算法，
他的遞推關系還是非常明確的，可以給出遞推關系如下：
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<j≤i+k)
我們嘗試了直接暴力地求解，但是這樣的時間復雜度是 O ( N × K ) O(N \times K) O(N×K)的，就會導致超時，但是這一題事實上可以參考上一周雙周賽的最后一題的思路，使用一個有序佇列進行處理，就可以將時間復雜度退化到 O ( N ) O(N) 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]
提交代碼評測得到：耗時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代碼實作如下：
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方式進行的實作，因此這里就不過多進行展開了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/237981.html
標籤：其他
上一篇：[“菜鳥杯”華中師范大學程式設計新生賽]Coda的題解集
下一篇：推箱子