- LeetCode筆記：Weekly Contest 221
- 0. 賽后總結
- 1. 題目一
- 1. 解題思路
- 2. 代碼實作
- 2. 題目二
- 1. 解題思路
- 2. 代碼實作
- 3. 題目三
- 1. 解題思路
- 2. 代碼實作
- 4. 題目四
- 1. 解題思路
- 2. 代碼實作
0. 賽后總結
昨天才遭遇滑鐵盧，本以為成績已經夠差了，結果轉頭今天就被打臉，成績比昨天還差，國內468/3397，全球1274/8838，真的是，不想說什么了，
不過這次真心是我自找的，第三題明明是一道簡單的題目，硬生生被我當成了之前一道hard的dsu題目來做，寫的極其復雜，結果還是錯的，真的是，好歹最后是改回來了，不過代價就是最后一題算是徹底沒時間做了，雖然大致看了一下，確實也沒啥思路就是了，，，
唉，時運不濟，命途多舛啊，只能后面加油了，，，
1. 題目一
給出題目一的試題鏈接如下：
- 5637. 判斷字串的兩半是否相似
1. 解題思路
這一題沒啥好說的，就是把字串分成前后兩部分，然后統計一下其中元音字符的個數，然后比較一下就行了，
2. 代碼實作
給出python代碼實作如下：
class Solution:
def halvesAreAlike(self, s: str) -> bool:
n = len(s)
cnt = sum([1 for c in s[:n//2] if c in "aeiouAEIOU"]) - sum([1 for c in s[n//2:] if c in "aeiouAEIOU"])
return cnt == 0
該演算法的演算法復雜度為 O ( N ) O(N) O(N)，
提交代碼評測得到：耗時32ms，占用記憶體14.2MB，屬于當前最優的代碼實作，
2. 題目二
給出題目二的試題鏈接如下：
- 5638. 吃蘋果的最大數目
1. 解題思路
這一題事實上也并不復雜，只要按照蘋果的腐爛時間維護一個有序陣列就行了，對每一天，彈出所有的腐爛蘋果，并放入新收入的蘋果，然后如果陣列不為空，當天就能吃到一個蘋果，
2. 代碼實作
給出python代碼實作如下：
class Solution:
def eatenApples(self, apples: List[int], days: List[int]) -> int:
ans = 0
q = []
n = len(apples)
i = 0
while i < n or q != []:
if i<n and apples[i] != 0:
if q != [] and i+days[i] == q[0][0]:
q[0][1] += apples[i]
else:
heapq.heappush(q, [i+days[i], apples[i]])
while q != [] and q[0][0] <= i:
heapq.heappop(q)
if q != []:
ans += 1
q[0][1] -= 1
if q[0][1] == 0:
heapq.heappop(q)
i += 1
return ans
提交代碼評測得到：耗時700ms，占用記憶體18.8MB，
當前最優的演算法實作耗時688ms，但是看了一下整體的思路實作共同的，因此這里就不過多展開了，
3. 題目三
給出題目三的試題鏈接如下：
- 5210. 球會落何處
1. 解題思路
第三題是我這次最大的敗筆，顯然這一題與leetcode的959題是非常相似的，后者是一道給我留下了非常深刻印象的dsu典型例題，
因此，我拿到這一題之后直接就上手開始用dsu進行求解，結果就呵呵了，不但演算法寫的很煩，而且事實上演算法邏輯上是有問題的，因為上述959題當中事實上問的是連通關系，但是這里是一個掉落問題，與連通關系不同，掉落關系是有序的，只能由上而下，而不能回傳到另一個連通點上，
因此，我們遇到了錯誤，這個問題我debug了近一個小時，后面才發現，然后就呵呵了，簡直不能更慘，唉，，，
下面，我們來考慮真實的解題思路，由于只能小球只能沿著通道向下，因此，事實上我們需要討論的情況是很少的，允許的情況只有以下兩種：
- 某個節點的格柵為1，他的右側節點同樣為1，那么球就會從這個節點滾落到他的右下面節點；
- 某個節點的格柵為-1，他的左側節點同樣為-1，那么球就會經過該節點滾落到他的左下方節點；
- 對于其他任何情況，小球都會在該節點位置終止掉落，
那么，我們只要上述內容用代碼語言表達出來即可，
2. 代碼實作
給出python代碼實作如下：
class Solution:
def findBall(self, grid: List[List[int]]) -> List[int]:
m = len(grid)
n = len(grid[0])
res = [-1 for _ in range(n)]
for b in range(n):
i = 0
j = b
while 0 <= i < m and 0 <= j < n:
if grid[i][j] == 1 and j+1<n and grid[i][j+1] == 1:
j += 1
i += 1
elif grid[i][j] == -1 and j-1 >= 0 and grid[i][j-1] == -1:
j -= 1
i += 1
else:
break
if i == m:
res[b] = j
return res
該演算法的演算法復雜度為 O ( N 2 ) O(N^2) O(N2)，
提交代碼評測得到：耗時196ms，占用記憶體14.7MB，
當前leetcode還沒有足夠的提交代碼，因此暫不清楚是否存在更有效率的演算法實作，后續如果有更好的演算法實習思路，歡迎讀者在下方評論欄中進行補充，
4. 題目四
給出題目四的試題鏈接如下：
- 5640. 與陣列中元素的最大異或值
1. 解題思路
這一題比賽的時候就是完全沒有思路，唯一的想法就是直接暴力求解，然后果然遇到了超時問題，
賽后也算是想了挺久的，不過一直沒有好的思路，直到看了答案才恍然大悟，這就是一道典型的trie樹的問題！！！
是了，對于大量資料的查詢問題最直接的想法不就應該是Trie樹嗎？
有了這個主體思想之后，后面也就是針對查找結果不能夠大于m進行一個變體而已，這部分內容相對就好實作了，我是用了堆疊的思想實作了一個深度優先遍歷演算法進行實作的，不過應該也有其他的實作方法就是了，
有關trie樹的相關內容可以詳見我之前的博客Python筆記：Trie樹結構簡介，可憐我明明已經專門整理過trie樹的相關內容，居然還是沒有想到，真的是慚愧啊，，，
2. 代碼實作
我們直接給出python代碼實作如下：
class Trie:
def __init__(self):
self.trie = {}
def num2digits(self, n):
digits = [0 for _ in range(30)]
idx = 29
while n != 0:
digits[idx] = n % 2
n = n // 2
idx -= 1
return digits
def add(self, n):
digits = self.num2digits(n)
trie = self.trie
for d in digits:
trie = trie.setdefault(d, {})
trie["eos"] = n
return
def find(self, x, m):
digits = self.num2digits(x)
stack = [(self.trie, 0, 0)]
while stack:
trie, val, depth = stack.pop()
if depth == 30:
return x ^ trie["eos"]
new_val = val + 2**(29-depth)
if digits[depth] == 0:
if 0 in trie:
stack.append((trie[0], val, depth+1))
if 1 in trie and new_val <= m:
stack.append((trie[1], new_val, depth+1))
else:
if 1 in trie and new_val <= m:
stack.append((trie[1], new_val, depth+1))
if 0 in trie:
stack.append((trie[0], val, depth+1))
return -1
class Solution:
def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
trie = Trie()
for n in nums:
trie.add(n)
# print(trie.trie)
res = [trie.find(x, m) for x, m in queries]
return res
提交代碼評測得到：耗時6672ms，占用記憶體256.1MB，
當前最優的演算法實作耗時4460ms，倒是好像沒有使用trie樹，事實上也確實沒有看懂他的演算法，因為實在是有點看不動了😭，有興趣的讀者可以自行研讀一下，這里就請允許我偷個懶，不過多展開了，還請各位讀者諒解，
另外，關于這題如果有更好的思路的話，也請務必在評論區里面留言一下，萬分感激！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/241924.html
標籤：其他
上一篇：簡易貪吃蛇的實作
下一篇：C語言游戲——“2048”