LeetCode笔记：Weekly Contest 234 比赛记录（补发）
LeetCode笔记：Weekly Contest 234 比赛记录（补发）
- LeetCode笔记：Weekly Contest 234
- 0. 赛后总结
- 1. 题目一
- 1. 解题思路
- 2. 代码实现
- 2. 题目二
- 1. 解题思路
- 2. 代码实现
- 3. 题目三
- 1. 解题思路
- 2. 代码实现
- 4. 题目四
- 1. 解题思路
- 2. 代码实现
0. 赛后总结
这一次说是赛后总结其实挺不合适的，因为事实上也没有参加这次比赛，离职之后的第一周，收拾了一下东西，准备北上了，就借机在家偷了个懒……
不过偷懒归偷懒，题目终究还是要做的，毕竟一个程序员，经常性地写写代码保持手热的状态感觉还是挺必要的……
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题其实没啥好说的，其实就是把原先string里面所有非数字类型的字符转换为空字符，然后将所有的数字提取出来之后转换为int型然后计数即可。
唯一需要需要注意的是，数字开头的0需要先全部删除，然后记得对重复的数字去个重。
2. 代码实现
给出一个简单的python代码实现如下：
class Solution:
def numDifferentIntegers(self, word: str) -> int:
for ch in string.ascii_lowercase:
word = word.replace(ch, " ")
res = [x.lstrip("0") for x in word.strip().split()]
return len(set(res))提交代码评测得到：耗时24ms，占用内存14.3MB。
当前最优的解法耗时12ms，不过解法相对复杂一点，它是直接在一次遍历之中找到所有的数字然后记录，时间复杂度更低，但是代码相对复杂一点，有兴趣的读者可以自行看一下，这里就不多做展开了。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这题有点坑爹，之前想了好几天，但是一直找不到规律，今天终于放弃了，然后看了一下答案之后直接崩溃了，他的解法就是直接暴力尝试直到恢复到原先的状态……
坑爹啊！！！
2. 代码实现
给出python代码实现如下：
class Solution:
def reinitializePermutation(self, n: int) -> int:
arr = [i for i in range(n)]
res = 0
while True:
arr = [arr[i//2] if i % 2 == 0 else arr[n//2 + (i-1)//2] for i in range(n)]
res += 1
if all(i == arr[i] for i in range(n)):
break
return res提交代码评测得到：耗时532ms，占用内存14.2MB。
当前最优的算法耗时仅16ms，他的解法更加暴力一点，但是没想明白为啥一定靠谱，他们的解法是考察第一个元素的变化，当第一个元素恢复到原先位置时，就直接返回操作数。
但是这部分的逻辑没有完全理解，如果有读者想明白了的话请务必在评论区解说一二，大谢！
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题其实思路非常的简单，无非就是一个正则替换就完事了。
不过如果直接使用正则方法进行替换的话就会遇到超时的问题，毕竟其复杂度为O(K×N)。其中，K为pattern的种类。
不过，事先先把pattern记录下来之后，后面可以直接使用O(N)的时间复杂度完成，即一次遍历即可完成所有的pattern的替换。
2. 代码实现
给出python代码实现如下：
class Solution:
def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
knowledge = {k:v for k, v in knowledge}
bra = -1
res = []
for idx, ch in enumerate(s):
if ch == ')':
if s[bra+1:idx] in knowledge:
res.append(knowledge[s[bra+1:idx]])
else:
res.append("?")
bra = -1
elif ch == "(":
bra = idx
else:
if bra == -1:
res.append(ch)
return "".join(res)提交代码评测得到：耗时924ms，占用内存54.9MB。
算法效率在前10%，当前最优的算法实现耗时852ms，但是看了一下时间复杂度同样是O(N)，因此这里就不再多做展开了。
4. 题目四
给出题目四的试题链接如下：
2. 代码实现
综上，我们就可以快速地给出我们的python代码如下：
class Solution:
def maxNiceDivisors(self, primeFactors: int) -> int:
MOD = 10**9+7
def fn(n):
if n <= 4:
return n
elif n % 3 == 0:
return pow(3, n//3, MOD) % MOD
elif n % 3 == 1:
return 4 * pow(3, (n-4)//3, MOD) % MOD
else:
return 2 * pow(3, (n-2)//3, MOD) % MOD
return fn(primeFactors)提交代码评测得到：耗时32ms，占用内存14.2MB。
