- LeetCode筆記：Biweekly Contest 46
- 0. 賽后總結
- 1. 題目一
- 1. 解題思路
- 2. 代碼實作
- 2. 題目二
- 1. 解題思路
- 2. 代碼實作
- 3. 題目三
- 1. 解題思路
- 2. 代碼實作
- 4. 題目四
- 1. 解題思路
- 2. 代碼實作
0. 賽后總結
這場比賽打的挺糟心的，之前在和朋友聊天，最后臨時決定還是參加了這場比賽，然后從第一題開始就做的很不順暢……
第一題最后舍棄了時間復雜度，選擇了一個暴力方法進行求解，第二題是干脆看錯了題目，把一個關鍵條件弄反了，結果硬生生把一道easy的題目做成了地獄難度，最后3分鐘才猛然醒悟，但是已經沒有時間做了，最后超時兩分鐘提交通過，真是要多不甘心有多不甘心，
然后最后一題也是，遇到了超時問題，始終沒想到什么好的解決思路……
感覺就是諸事不順，大概是因為前段時間和朋友聊天吹牛逼立下了flag的關系吧……
1. 題目一
給出題目一的試題鏈接如下：
- 5668. 最長的美好子字串
1. 解題思路
這題有一說一，做的不順的最主要原因事實上還是看錯題目的關系，題目的要求包括：
- 首先必須是美好字串
- 給出最長的美好字串
- 只有存在多個最長的美好字串時，給出第一個
我最初的想法是先統計各個字符出現的次數，然后進行統計考察，但是遇到了困難，最后還是直接給出了最暴力的列舉法進行解答的，后續看看有沒有更好的解題思路吧……
2. 代碼實作
給出暴力求解的代碼實作如下：
class Solution:
def longestNiceSubstring(self, s: str) -> str:
def is_nice(sub):
for c in sub:
if not c.lower() in sub or not c.upper() in sub:
return False
return True
n = len(s)
res = []
for i in range(n):
for j in range(n, i, -1):
if is_nice(s[i:j]):
res.append((s[i:j], i))
res = sorted(res, key=lambda x: (-len(x[0]), x[1]))
return "" if res == [] else res[0][0]
提交代碼評測得到：耗時88ms，占用記憶體14.5MB，
看了一下當前的代碼實作思路，貌似都是暴利求解的……
2. 題目二
給出題目二的試題鏈接如下：
- 5669. 通過連接另一個陣列的子陣列得到一個陣列
1. 解題思路
這道題其實只要注意匹配順序必須與給定的groups順序一致，因此，我們只要采用貪婪匹配的方式進行子陣列的注意匹配即可，
2. 代碼實作
給出python代碼實作如下：
class Solution:
def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
n = len(groups)
flag = 0
i = 0
m = len(nums)
while i < m and flag < n:
if nums[i] != groups[flag][0]:
i += 1
continue
status = True
for j in range(len(groups[flag])):
if i+j >= m or nums[i+j] != groups[flag][j]:
status = False
break
if status:
i += len(groups[flag])
flag += 1
else:
i += 1
return flag == n
提交代碼評測得到：耗時144ms，占用記憶體14.4MB，
當前最優的代碼實作耗時72ms，但是看了一下，其核心演算法思路是相同的，因此就不多做展開了，
3. 題目三
給出題目三的試題鏈接如下：
- 5671. 地圖中的最高點
1. 解題思路
這一題我的解題思路就是bfs，我們首先將最低點加入到佇列當中，然后不斷更新其鄰接點上的高度，然后將鄰接點順序加入到佇列當中，直到地圖上所有的點全部都被賦予了高度，
2. 代碼實作
我們給出python代碼實作如下：
class Solution:
def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
n, m = len(isWater), len(isWater[0])
q = []
res = [[-1 for _ in range(m)] for _ in range(n)]
for i in range(n):
for j in range(m):
if isWater[i][j] == 1:
res[i][j] = 0
q.append((i, j))
while q:
i, j = q.pop(0)
if i-1 >= 0 and res[i-1][j] == -1:
res[i-1][j] = res[i][j] + 1
q.append((i-1, j))
if i+1 < n and res[i+1][j] == -1:
res[i+1][j] = res[i][j] + 1
q.append((i+1, j))
if j-1 >= 0 and res[i][j-1] == -1:
res[i][j-1] = res[i][j] + 1
q.append((i, j-1))
if j+1 < m and res[i][j+1] == -1:
res[i][j+1] = res[i][j] + 1
q.append((i, j+1))
return res
提交代碼評測得到：耗時5944ms，占用記憶體79.5MB，
當前的最優演算法實作耗時4348ms，看了一下他們的演算法實作，思路和我們是一致的，都是采用了bfs的思路，因此就不過多展開了，有興趣的讀者可以自行去看一下，
4. 題目四
給出題目四的試題鏈接如下：
- 5670. 互質樹
1. 解題思路
這一題比賽的時候遇到了超時問題，到最后也沒有解決，賽后看了一下其他大佬們的解法，發現整體的思路在于使用了深度優先遍歷，這個倒是沒啥新奇的，不過最核心的優化點在于：
- 他們不是記錄每個點的祖先，而是在每一層記錄每一個值向上最近的祖先的值，
這樣，就不需要記錄整個樹，而是只要維護1-50這些數向上的最近互質祖先位置即可，
但是他們的解法思路整體上來說確實看的半懂不懂的，就放在下面供讀者參考了，
2. 代碼實作
給出比賽中那些大佬們的解法如下：
class Solution:
def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
n = len(nums)
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
primes = [[j for j in range(1, 51) if gcd(i, j) == 1] for i in range(1, 51)]
current = [-1 for _ in range(51)]
ans = [-1 for _ in range(n)]
def dfs(x, parent):
nonlocal current
ans[x] = current[nums[x]]
current2 = current[:]
for j in primes[nums[x] - 1]:
current[j] = x
for v in graph[x]:
if v != parent:
dfs(v, x)
current[:] = current2
dfs(0, -1)
return ans
提交代碼評測得到：耗時2412ms，占用記憶體135.8MB，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/266375.html
標籤：python
上一篇：烤面筋的第四場