LeetCode笔记：Weekly Contest 234 比赛记录（补发）

• LeetCode笔记：Weekly Contest 234
  • 0. 赛后总结
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现

0. 赛后总结

这一次说是赛后总结其实挺不合适的，因为事实上也没有参加这次比赛，离职之后的第一周，收拾了一下东西，准备北上了，就借机在家偷了个懒……

不过偷懒归偷懒，题目终究还是要做的，毕竟一个程序员，经常性地写写代码保持手热的状态感觉还是挺必要的……

1. 题目一

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

• 1805. Number of Different Integers in a String

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. 题目二

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

• 1806. Minimum Number of Operations to Reinitialize a Permutation

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. 题目三

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

• 1807. Evaluate the Bracket Pairs of a String

1. 解题思路

这一题其实思路非常的简单，无非就是一个正则替换就完事了。

不过如果直接使用正则方法进行替换的话就会遇到超时的问题，毕竟其复杂度为$O(K\times 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. 题目四

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

• 1808. Maximize Number of Nice Divisors

1. 解题思路

这一题事实上就是一道数学题目。

事实上就是要解如下数学问题：

• 已知：$\sum n_i=n$，求解：$max{\prod }_i{n}_i$

由不等式关系：$\sqrt[n]{{\prod }_i^m{n}_i}\le \frac{{\sum }_i{n}_i}{m}=\frac{n}{m}$

我们可以快速地看出，显然当所有的因子尽可能相同时能够得到最大的解。

剩下的问题就是看要怎么拆分总数n。

我们给出一般的计算公式如下：

$f(m)=m^{\frac{n}{m}}$

对其求对数不会影响其单调关系，即有：$f(m)=\frac{n}{m}?ln(m)$。

对其求导即有：
KaTeX parse error: Expected 'EOF', got '}' at position 39: …cdot (1 - ln(m)}?)

可以看到，当m取e时达到最大值，但是鉴于m只能为整数，所以很简单的可以得出结论：

• 尽可能将其拆分为3可以令结果最大化。

唯一区别在于当$n\le 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。

不过需要注意的是，这里使用了pow(a, b, m)函数，其含义为$a^{b}mod(m)$，如果直接使用a**b % m则会出现超时问题，算是一个不大不小的坑吧……