-
LeetCode笔记：Biweekly Contest 107
-
1. 题目一
- 1. 解题思路
- 2. 代码实现
-
2. 题目二
- 1. 解题思路
- 2. 代码实现
- 3. 算法优化
-
3. 题目三
- 1. 解题思路
- 2. 代码实现
-
4. 题目四
- 1. 解题思路
- 2. 代码实现
-
1. 题目一
- 比赛链接：https://leetcode.com/contest/biweekly-contest-107/
1. 题目一
给出题目一的试题链接如下：
- 2744. Find Maximum Number of String Pairs
1. 解题思路
这一题由于每一个字符串都是unique的，因此事实上问题就被大幅简化了，我们只需要找到所有的反字符串同样出现过的，且其反不为自身的字符串的个数除以2即可。
2. 代码实现
给出python代码实现如下：文章来源：https://www.toymoban.com/news/detail-515806.html
class Solution:
def maximumNumberOfStringPairs(self, words: List[str]) -> int:
s = set(words)
res = 0
for w in words:
if w != w[::-1] and w[::-1] in s:
res += 1
return res // 2
提交代码评测得到：耗时62ms，占用内存16.4MB。
2. 题目二
给出题目二的试题链接如下：
- 2745. Construct the Longest New String
1. 解题思路
这一题感觉应该是可以直接写出答案的，不过可惜的是我没有想到很好的思路，不过考虑到题目限制了string的个数，因此我暴力地采用动态规划的方式强行枚举求出了答案……
2. 代码实现
给出python代码实现如下：
class Solution:
def longestString(self, x: int, y: int, z: int) -> int:
@lru_cache(None)
def dfs(x, y, z, pre):
res = 0
if pre == "AA":
if y > 0:
res = max(res, 2 + dfs(x, y-1, z, "BB"))
elif pre == "BB" or pre == "AB":
if x > 0:
res = max(res, 2 + dfs(x-1, y, z, "AA"))
if z > 0:
res = max(res, 2 + dfs(x, y, z-1, "AB"))
else:
if x > 0:
res = max(res, 2 + dfs(x-1, y, z, "AA"))
if y > 0:
res = max(res, 2 + dfs(x, y-1, z, "BB"))
if z > 0:
res = max(res, 2 + dfs(x, y, z-1, "AB"))
return res
return dfs(x, y, z, "")
提交代码评测得到：耗时3134ms，占用内存166.6MB。
3. 算法优化
不过如前所述，这道题应该是有直接的解法的，想清楚了应该可以直接手写答案，事实上看其他大佬们的解答看起来就是，当前执行效率最高的代码耗时仅56ms，其算法便是如此：
class Solution:
def longestBeautifulString(self, x: int, y: int, z: int) -> int:
return (z + min(x, y+1) + min(x+1, y)) * 2
不过可惜的是，暂时我还没有想明白其中的解释，因此只是先在此摘录一下，后续还需要细想一下。
3. 题目三
给出题目三的试题链接如下：
- 2746. Decremental String Concatenation
1. 解题思路
这一题我的思路同样是使用动态规划，这里就不赘述了，直接给出代码如下。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimizeConcatenatedLength(self, words: List[str]) -> int:
n = len(words)
s = sum(len(w) for w in words)
@lru_cache(None)
def dp(idx, st, ed):
if idx >= n:
return 0
if st == words[idx][-1]:
s1 = 1 + dp(idx+1, words[idx][0], ed)
else:
s1 = dp(idx+1, words[idx][0], ed)
if ed == words[idx][0]:
s2 = 1 + dp(idx+1, st, words[idx][-1])
else:
s2 = dp(idx+1, st, words[idx][-1])
return max(s1, s2)
return s - dp(1, words[0][0], words[0][-1])
提交代码评测得到：耗时453ms，占用内存48MB。
4. 题目四
给出题目四的试题链接如下：
- 2747. Count Zero Request Servers
1. 解题思路
这一题我最开始的思路是使用segment tree，毕竟范围内求值这个范式太接近于segment tree了，这个思路是可行的，但是不幸遇上了超时。
后来仔细一想，发现自己想复杂了，维护一个时间窗口，然后通过滑动时间窗口的方式直接对范围内有请求的server进行记录和维护即可……
难怪只是一道medium的题目，不过居然只有这么少的人提交了也是有点奇怪……
2. 代码实现
给出python代码实现如下：
class Solution:
def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:
logs = sorted(logs, key=lambda x: x[1])
m = len(logs)
queries = [(idx, t) for idx, t in enumerate(queries)]
queries = sorted(queries, key=lambda x: x[1])
res = [0 for _ in queries]
i, j = 0, 0
cnt = {}
for idx, t in queries:
while j < m and logs[j][1] <= t:
server = logs[j][0]
if server in cnt:
cnt[server] += 1
else:
cnt[server] = 1
j += 1
while i < m and logs[i][1] < t-x:
server = logs[i][0]
cnt[server] -= 1
if cnt[server] == 0:
cnt.pop(server)
i += 1
res[idx] = n - len(cnt)
return res
提交代码评测得到：耗时1635ms，占用内存79MB。文章来源地址https://www.toymoban.com/news/detail-515806.html
到了这里，关于LeetCode笔记：Biweekly Contest 107的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
