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 × 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. 題目四

給出題目四的試題鏈接如下：

• 1808. Maximize Number of Nice Divisors

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則會出現超時問題，算是一個不大不小的坑吧……