LeetCode笔记：Weekly Contest 221 比赛记录

• 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
1
2
3
4
5

该算法的算法复杂度为$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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

提交代码评测得到：耗时700ms，占用内存18.8MB。

当前最优的算法实现耗时688ms，但是看了一下整体的思路实现共同的，因此这里就不过多展开了。

3. 题目三

给出题目三的试题链接如下：

• 5210. 球会落何处

1. 解题思路

第三题是我这次最大的败笔，显然这一题与leetcode的959题是非常相似的，后者是一道给我留下了非常深刻印象的dsu典型例题。

因此，我拿到这一题之后直接就上手开始用dsu进行求解，结果就呵呵了，不但算法写的很烦，而且事实上算法逻辑上是有问题的，因为上述959题当中事实上问的是连通关系，但是这里是一个掉落问题，与连通关系不同，掉落关系是有序的，只能由上而下，而不能返回到另一个连通点上。

因此，我们遇到了错误，这个问题我debug了近一个小时，后面才发现，然后就呵呵了，简直不能更惨，唉。。。

下面，我们来考虑真实的解题思路，由于只能小球只能沿着通道向下，因此，事实上我们需要讨论的情况是很少的，允许的情况只有以下两种：

1. 某个节点的格栅为1，他的右侧节点同样为1，那么球就会从这个节点滚落到他的右下面节点；
2. 某个节点的格栅为-1，他的左侧节点同样为-1，那么球就会经过该节点滚落到他的左下方节点；
3. 对于其他任何情况，小球都会在该节点位置终止掉落。

那么，我们只要上述内容用代码语言表达出来即可。

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

该算法的算法复杂度为$O(N^2)$。

提交代码评测得到：耗时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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

提交代码评测得到：耗时6672ms，占用内存256.1MB。

当前最优的算法实现耗时4460ms，倒是好像没有使用trie树，事实上也确实没有看懂他的算法，因为实在是有点看不动了