- LeetCode筆記：Biweekly Contest 39
- 0. 賽后總結
- 1. 題目一
- 1. 解題思路
- 2. 代碼實作
- 2. 題目二
- 1. 解題思路
- 2. 代碼實作
- 3. 題目三
- 1. 解題思路
- 2. 代碼實作
- 3. 演算法優化
- 4. 題目四
- 1. 解題思路
- 2. 代碼實作
- 3. 演算法優化
0. 賽后總結
這一次的比賽從成績上來看是挺滿意的，國內84，世界214，挺讓人滿意的一個結果了，不過可惜的是依然沒能把四題全部做出來，卡死在了第三題上，簡直了，
看看別人的做法學習一下吧，再接再厲，再接再厲！
1. 題目一
給出題目一的試題鏈接如下：
- 5550. 拆炸彈
1. 解題思路
第一題整體還是蠻trival的一道題目，就是按照題目意思進行處理就行了，唯一復雜一點的地方就在于回圈的處理，
但這個其實也不難，當k大于零時，我們在序列最后補上頭上的k個數，反之當k小于0時，我們在序列頭上補上末尾的k個數即可，
2. 代碼實作
給出最終的python代碼實作如下：
class Solution:
def decrypt(self, code: List[int], k: int) -> List[int]:
n = len(code)
if k == 0:
return [0 for _ in range(n)]
if k > 0:
code = code + code[:k]
return [sum(code[i+1:i+k+1]) for i in range(n)]
else:
k = -k
code = code[-k:] + code
return [sum(code[i-k:i]) for i in range(k, k+n)]
提交代碼評測得到：耗時28ms，占用記憶體14.1MB，為當前最優的代碼實作，
2. 題目二
給出題目二的試題鏈接如下：
- 5551. 使字串平衡的最少洗掉次數
1. 解題思路
這一題總感覺之前在哪里做過，，，不過本質來說，這題的思路還是非常直白的，它最終要得到的狀態就是達到前面都是a，后面都是b的一個字串，那么，我們要做的就是統計每一個字符位置前方的b的字符的個數以及后方的a的字符的個數，然后求其中的最小值即可，
2. 代碼實作
我們直接給出python代碼實作如下：
class Solution:
def minimumDeletions(self, s: str) -> int:
n = len(s)
a = [0 for _ in range(n)]
b = [0 for _ in range(n)]
for i in range(n-1):
if s[i] == 'b':
b[i+1] = b[i]+1
else:
b[i+1] = b[i]
for i in range(n-1, 0, -1):
if s[i] == 'a':
a[i-1] = a[i] + 1
else:
a[i-1] = a[i]
return min(a[i] + b[i] for i in range(n))
提交代碼評測得到：耗時1296ms，占用記憶體19.8MB，
當前的最優解法耗時僅500ms，看了一下他們的代碼，發現思路上應該是一樣的，不過實作細節上有所差異，有興趣的讀者可以自行去看一下，這里就不多做展開了，
3. 題目三
給出題目三的試題鏈接如下：
- 5552. 到家的最少跳躍次數
1. 解題思路
隔了一天重新看了一下這題，結果昨天的解法和最終答案事實上就差了兩行代碼，簡直了，，，
本質上來說，這個還是一個遞回演算法，有點像是八皇后問題，解題思路如下：
- 如果當前位置小于目標x，且可以向右走，則優先向右走，并將其記錄到歷史路徑當中；
- 如果當前位置大于目標x，且可以向左走，則優先向左走，并將其記錄到歷史路徑當中；
- 如果某一個位置已經出現在歷史路徑當中過了，那么這條路徑必然不會是最優路徑；
- 如果一條路徑走到了盡頭無法再走或者遇到了3中的情況，那么就回退直至上一個可以走下一步的路徑遍歷下一個可行的路徑，
2. 代碼實作
給出python代碼實作如下：
class Solution:
def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
forbidden = set(forbidden)
seen = {0}
@lru_cache(None)
def dfs(loc, can_back):
if loc == x:
return 0
if loc < x:
if loc + a not in forbidden and loc + a not in seen:
seen.add(loc + a)
tmp = dfs(loc+a, True)
if tmp != -1:
return tmp + 1
seen.remove(loc+a)
if can_back and loc - b >= 0 and loc - b not in seen and loc-b not in forbidden:
seen.add(loc-b)
tmp = dfs(loc-b, False)
if tmp != -1:
return tmp + 1
seen.remove(loc-b)
return -1
else:
if b-a <= 0 and loc > x+b:
return -1
if can_back and loc - b >= 0 and loc - b not in seen and loc-b not in forbidden:
seen.add(loc-b)
tmp = dfs(loc-b, False)
if tmp != -1:
return tmp + 1
seen.remove(loc-b)
if loc >= 4000:
return -1
if loc + a not in forbidden and loc + a not in seen:
seen.add(loc + a)
tmp = dfs(loc+a, True)
if tmp != -1:
return tmp + 1
seen.remove(loc+a)
return -1
return dfs(0, True)
提交代碼評測得到：耗時96ms，占用記憶體21.4MB，
當前最優代碼實作耗時68ms，看了一下，他的代碼實作確實比我們的優雅，唉，，，
3. 演算法優化
本質而言，當前最優演算法和我們的思路是一樣的，但是，他直接使用了一個佇列來保存第k步時所有可能的路徑，另外在第k步時走過的所有歷史線路都直接加入到了forbidden當中，而不像我們哪個另外搞了一個seen集合來另外存盤，
另一方面，他對于最大距離的處理也更加好，我們暴力地采用了兩倍最大距離，即4000的方式，而他則對這個值進行了優化，
給出他的代碼實作如下：
class Solution:
def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
from collections import deque
queue = deque([(0,1)])
jumps = 0
forbidden = set(forbidden)
forbidden.add(0)
MAX_DIST = max(x, max(forbidden)) + a + b
while queue:
tmp = deque()
for elem in queue:
(pos, direction) = elem
if pos == x:
return jumps
forward = pos + a
if forward not in forbidden and forward <= MAX_DIST:
tmp.append((forward, 1))
forbidden.add(forward)
for elem in queue:
(pos, direction) = elem
if pos == x:
return jumps
backward = pos - b
if direction != -1 and backward >= 0 and backward not in forbidden:
tmp.append((backward, -1))
forbidden.add(backward)
queue = tmp
jumps += 1
return -1
4. 題目四
給出題目四的試題鏈接如下：
- 5553. 分配重復整數
1. 解題思路
這一題比較直接的一個思路就是仿照八皇后問題那樣使用遞回的一種演算法，將能夠分配的先進行分配，直至分配完成或者無法繼續匹配為止，
如果匹配完成，則直接回傳True即可，否則退回上一次分配，使用下一個可行的分配方案進行分配，直至有一個成功或者所有的候選方案全部匹配失敗為止，然后重復這個步驟，
2. 代碼實作
給出python代碼實作如下：
class Solution:
def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
counter = list(Counter(nums).values())
quantity = sorted(quantity, reverse=True)
n = len(quantity)
def dfs(idx):
if idx >= n:
return True
for i, c in enumerate(counter):
if c < quantity[idx]:
continue
counter[i] -= quantity[idx]
if dfs(idx+1):
return True
counter[i] += quantity[idx]
return False
return dfs(0)
提交代碼評測得到：耗時4628ms，占用記憶體25.6MB，
當前最優的解法耗時僅512ms，較之我們的解法有近一個量級的性能提升，因此，我們有必要好好研究一下他們的解法，
3. 演算法優化
這個演算法的優化我基本放棄了，原則上來說上述dfs代碼中最浪費時間的在于每一次都遍歷了全部的資料，但是如果我們能夠通過某種方式維護住這個有序序列的話，那么就可以減少很多的冗余操作，
但是，這里我們并沒有想到什么比較好的方法來消除這個冗余操作，看了一下他們的代碼，感覺應該也是在這部分進行了優化，不過實在是不想看他們的代碼了，有點累，就直接摘錄他們的代碼如下了，有興趣的讀者可以自行研究一下，
import heapq
class Solution:
def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
cnt=collections.Counter(nums)
vs=sorted(cnt.values())
qt=tuple(sorted(quantity))
cusum=[vs[0]]*len(vs)
for i in range(1,len(vs)):
cusum[i]=cusum[i-1]+vs[i]
def helper(qt,v):
cands=set()
seen={qt}
stack=[[qt,v]]
while stack:
cqt,cv=stack.pop()
if cqt[0]>cv:
cands.add((sum(cqt),cqt))
else:
for i in range(len(cqt)):
if cqt[i]<=cv:
nv=cv-cqt[i]
nqt=cqt[:i]+cqt[i+1:]
if nqt not in seen:
seen.add(nqt)
stack.append([nqt,nv])
return cands
state=[[sum(qt),qt,len(vs)-1]]
while state:
csum,cqt,j=heappop(state)
rem=cusum[j]
if j==0:
return rem>=csum
rem-=cusum[j-1]
if rem>=csum:
return True
if cusum[j]>=csum and cqt[-1]<=vs[j]:
cands=helper(cqt,vs[j])
for nsum,nqt in cands:
if nsum<=cusum[j-1] and nqt[-1]<=vs[j-1]:
heapq.heappush(state,[nsum,nqt,j-1])
return False
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/225353.html
標籤：python
上一篇：Idea自定義模板，家里5年級的外甥看了我的操作驚呆了，立馬打開Idea，再也不貪玩了，產生了濃厚的興趣。
下一篇：pytest介面測驗輕松入門