LeetCode笔记：Weekly Contest 218 比赛记录
LeetCode笔记：Weekly Contest 218 比赛记录
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题没啥可说的，不断地进行内容替换就行了。
2. 代码实现
直接给出python代码实现如下：
class Solution:
def interpret(self, command: str) -> str:
command = command.replace("(al)", "al")
command = command.replace("()", "o")
return command提交代码评测得到：耗时28ms，占用内存14.2MB。
当前的最优解法耗时24ms，但是看了一下其代码，本质上和上述实现是完全一致的，因此这里就不再多做展开了。
2. 题目二
给出题目二试题链接如下：
1. 解题思路
这一题的思路同样异常的直白，只要对数组中所有的数进行计数，然后考察其中加起来等于k的二元组的数据数量即可。
唯一需要注意的是边界条件需要注意一下：
- 当
i == k / 2时，需要特殊考察。
2. 代码实现
给出python代码实现：
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
counter = Counter(nums)
ans = 0
for i in counter:
if i < k-i:
ans += min(counter[i], counter[k-i])
elif i == k-i:
ans += counter[i] // 2
else:
continue
return ans提交代码评测得到：耗时632ms，占用内存27.6MB。
当前最优的代码实现耗时608ms，但是本质来说两者的思路是完全相同的。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题的思路其实也蛮简单的，无非就是依据下面的公式而已：
因此，我们只需要每次计算需要移动的位数，然后对前一次的答案做一次变换之后然后求取下一个解即可。
2. 代码实现
我们给出python代码实现如下：
class Solution:
def concatenatedBinary(self, n: int) -> int:
flag = 1
logits = 0
ans = 0
MOD = 10**9 + 7
for i in range(1, n+1):
if i == flag:
flag *= 2
logits += 1
ans = ((ans << logits) + i) % MOD
return ans提交代码评测得到：耗时832ms，占用内存14.2MB。
当前最优的代码实现耗时仅44ms，比我们有一个量级以上的性能提升，因此，我们需要好好考察一下其代码实现思路。
3. 算法优化
当前最优的代码实现，即44ms的那个代码有点繁琐，就没细看，但值得一说的是，另有一个耗时80ms的算法时间简直崩碎了我的三观，本质上来说他们的做法和我们是一模一样的，但是他们用了一个缓存机制，然后模型奇妙的效果提升了一个量级，简直理解不能。
如果有读者明白其中的奥秘所在的话，请务必在评论区指导一下，大谢！
这里，我们只给出其代码实现如下：
memo={1:1}
mod=10**9+7
class Solution:
def concatenatedBinary(self, n: int) -> int:
if n in memo:
return memo[n]
pre=self.concatenatedBinary(n-1)
ans=((pre<<(len(bin(n))-2))+n)%mod
memo[n]=ans
return ans4. 题目四
给出题目四的试题链接如下：
1. 解题思路
如果换用组合数来进行遍历求解的话事实上也就没有什么好多说的，下面直接给出python实现吧。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimumIncompatibility(self, nums: List[int], k: int) -> int:
n= len(nums)
k = n // k
if k == 1:
return 0
counter = Counter(nums)
if any(x > n // k for x in counter.values()):
return -1
@lru_cache(None)
def dp(idxs):
if len(idxs) == k:
num = [nums[i] for i in idxs]
return math.inf if len(set(num)) != k else max(num) - min(num)
ans = math.inf
for tmp in combinations(idxs, k):
num = [nums[i] for i in tmp]
if len(set(num)) == k:
ans = min(ans, max(num) - min(num) + dp(tuple([idx for idx in idxs if idx not in tmp])))
return ans
ans = dp(tuple([i for i in range(n)]))
return ans if ans != math.inf else -1提交代码评测得到：耗时7848ms，占用内存25.8MB。
当前最优的代码实现耗时1252ms，比我们快了5倍以上，但是代码有够长的，后面再看看有没有更好的解题思路吧。