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 ) O(K \times N) O(K×N)。其中, K K K为pattern的种类。
不过,事先先把pattern记录下来之后,后面可以直接使用 O ( N ) O(N) 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 ) O(N) O(N),因此这里就不再多做展开了。
4. 题目四
给出题目四的试题链接如下:
1. 解题思路
这一题事实上就是一道数学题目。
事实上就是要解如下数学问题:
- 已知: ∑ n i = n \sum{n_i} = n ∑ni?=n,求解: m a x ∏ i n i max{\prod_i{n_i}} max∏i?ni?
由不等式关系: ∏ i m n i n ≤ ∑ i n i m = n m \sqrt[n]{\prod_i^m{n_i}} \leq \frac{\sum_i{n_i}}{m} = \frac{n}{m} n∏im?ni??≤m∑i?ni??=mn?
我们可以快速地看出,显然当所有的因子尽可能相同时能够得到最大的解。
剩下的问题就是看要怎么拆分总数n。
我们给出一般的计算公式如下:
f ( m ) = m n m f(m) = m^{\frac{n}{m}} f(m)=mmn?
对其求对数不会影响其单调关系,即有: f ( m ) = n m ? l n ( m ) f(m) = \frac{n}{m} \cdot ln(m) f(m)=mn??ln(m)。
对其求导即有:
KaTeX parse error: Expected 'EOF', got '}' at position 39: …cdot (1 - ln(m)}?)
可以看到,当m取e时达到最大值,但是鉴于m只能为整数,所以很简单的可以得出结论:
- 尽可能将其拆分为3可以令结果最大化。
唯一区别在于当 n ≤ 4 n \leq 4 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。
不过需要注意的是,这里使用了pow(a, b, m)
函数,其含义为
a
b
m
o
d
(
m
)
a^b mod(m)
abmod(m),如果直接使用a**b % m
则会出现超时问题,算是一个不大不小的坑吧……