0. 赛后总结
昨天才遭遇滑铁卢，本以为成绩已经够差了，结果转头今天就被打脸，成绩比昨天还差，国内468/3397，全球1274/8838，真的是，不想说什么了。
不过这次真心是我自找的，第三题明明是一道简单的题目，硬生生被我当成了之前一道hard的dsu题目来做，写的极其复杂，结果还是错的，真的是，好歹最后是改回来了，不过代价就是最后一题算是彻底没时间做了，虽然大致看了一下，确实也没啥思路就是了。。。
唉，时运不济，命途多舛啊，只能后面加油了。。。
1. 题目一
给出题目一的试题链接如下：
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. 题目二
给出题目二的试题链接如下：
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. 题目三
给出题目三的试题链接如下：
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. 题目四
给出题目四的试题链接如下：
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树，事实上也确实没有看懂他的算法，因为实在是有点看不动了