LeetCode Weekly Contest 374 解題紀錄

那一天，人類終於回想起了，只寫出1題的絕望

Q2 有完全相同的題目，Q3的關鍵在可以固定窗口大小，Q4是反元素的運用，總之還是題目寫的不夠多

All problems solved by python

Q1: 🟢 2951. Find the Peaks 1189

tags: `陣列(Array)` `枚舉(Enumeration)`

題意

給定一個Array $mountain$ ，找出比左右兩側高的數之下標

思路：枚舉

打卡題

class Solution:
    def findPeaks(self, mountain: List[int]) -> List[int]:
        n = len(mountain)
        ans = []
        for i in range(1, n-1):
            if mountain[i] > mountain[i-1] and mountain[i] > mountain[i+1]:
                ans.append(i)
        return ans

Q2: 🟡 2952. Minimum Number of Coins to be Added 1784

tags: `陣列(Array)` `貪心(Greedy)` `排序(Sorting)`

題意

給定一個整數 $target$ 和 Array $coins$ ，求使用 $coins$ 構造出 $[1, target]$ 間所有整數，需要在 $coins$ 中添加的元素數量。

思路：歸納法+貪心

由小到大構造目標數，令 $s$ 表示當前可以構造的最大值，則 $s+1$ 為下一個要構造的值。
當前可以構造的數範圍是 $[0, s]$ $[0, s]$ ，在此基礎上若新增一個數 $c$ $c$ ，則可構造出 $[c, s+c]$ $[c, s + c]$ 。
- 若 $c <= s$ ，則兩區間存在重疊，合併後可構造的範圍變成 $[0, s+c]$
- 若 $c == s+1$ ，則兩區間洽連續，也可合併成 $[0, s+c]$
- 若 $c > s+1$ ，則兩區間不連續，無法構造出 $[0, s+c]$
根據上述討論，先對coins做排序，若 $coin[i] <= s + 1$ ，則可以構造出 $[0, s + coin[i] ]$ 中的所有整數
否則代表無法構造出 $s+1$ ，以貪心的方式補充 $s+1$ 的硬幣，補充後可以構造出 $[0, s + (s + 1) ]$ 中的所有整數
Time Complexity: $O(nlogn + log(target))$

類題

🟡 1798. Maximum Number of Consecutive Values You Can Make 1931
能夠構造的最大值，else後面改成直接break就可以了
🔴 330. Patching Array
一模一樣，改個變數名稱就可以直接AC

class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        coins.sort()
        n = len(coins)
        ans, idx, s = 0, 0, 0
        
        while s < target:
            if idx < n and coins[idx] <= s + 1:
                s += coins[idx] # 可以構造出 [0, s + coins[idx] ] 中的所有整數
                idx += 1
                continue
            else: # 因為後面的硬幣都 > s+1 ，所以無法構造出 s+1 了，需要補充 s+1
                s += s + 1
                ans += 1
        return ans

Q3. 🔴 2953. Count Complete Substrings 2449

tags: `分組循環` `雜湊表(Hash Table)` `字串(String)` `滑動窗口(Sliding Window)`

題意

給定一個字串 $word$ 和一個整數 $k$ ，若 $word$ 的子字串 $s$ 滿足以下兩者條件，則被認為是complete的。

$s$ 中的每個字元恰好出現 $k$ 次。
兩個相鄰字元之間的差異最多為 2。

求 $word$ 的完整子字串的數量。

思路：分組循環 + 枚舉窗口大小 + 滑動窗口

限制2「相鄰字母相差至多為 2」，可以將 $word$ 分成多個子串，每個字串 $s$ 可以分別處理，且分組後不用關心第二個限制。
對於每個子字串 $s$ ，枚舉出現的字母數量 $m$ $(1<=m<=26)$ ，則根據限制1，窗口大小為 $k * m$ ，此時可以用滑動窗口求出答案。
使用長度為26的Array或Hash Table紀錄字母的出現次數，更新窗口時檢查是否滿足條件1。
- 若逐個字母檢查出現次數，此部分的時間複雜度為 $O(26)$
- 若統計出現次數的出現次數，則不用逐個字母檢查，此部分的時間複雜度為 $O(1)$
Time: $O(n * 26 * 26)$ 或 $O(n * 26 * 1)$

類題

🟡 395. Longest Substring with At Least K Repeating Characters
🟢 1763. Longest Nice Substring 1522

class Solution:
    def countCompleteSubstrings(self, word: str, k: int) -> int:
        n = len(word)
        ans = 0

        def f(s: str) -> int: # Sliding window
            res = 0
            for m in range(1, 27): # 枚舉出現的字母數量 m，且根據題目，每個字母需出現k次，故窗口大小為 k * m
                if k * m > len(s): # 窗口大小超過字串長度
                    break
                cnt = [0] * 26 # 窗口內每個字母出現的次數
                cnt_cnt = [0] * (k * m + 1) # 窗口內每個字母出現的次數的次數
                for right, ch in enumerate(s):
                    c_in = ord(ch) - ord('a')
                    cnt_cnt[cnt[c_in]] -= 1
                    cnt[c_in] += 1
                    cnt_cnt[cnt[c_in]] += 1
                    if right >= k * m - 1: # 窗口大小為 k * m，故窗口內的字母數量不足 k * m 時，不計算
                        left = right + 1 - k * m
                        c_out = ord(s[left]) - ord('a')
                        # 窗口內的字母數量都為 k 時，res + 1
                        # res += all(cnt[c] == 0 or cnt[c] == k for c in range(26)) # O(26)
                        if cnt_cnt[k] == m: # O(1)
                            res += 1
                        cnt_cnt[cnt[c_out]] -= 1
                        cnt[c_out] -= 1
                        cnt_cnt[cnt[c_out]] += 1
            return res
        
        # 分組循環
        j = 0 # j is the right pointer
        while j < n:
            i = j
            j += 1
            while j < n and abs(ord(word[j]) - ord(word[j - 1])) <= 2:
                j += 1
            ans += f(word[i:j])
        return ans

Q4. 🔴 2954. Count the Number of Infection Sequences 2645

tags: `陣列(Array)` `數學(Math)` `組合數學(Combinatorics)` `乘法反元素(Inverse Element)`

題意

以長度為 $n$ 的一維Array表示小朋友的感染狀態，下標為 0 到 n-1，給定 $sick$ 表示感染源的下標。可以感染左右兩側的人，求未被感染的人的感染順序有幾種。

思路：組合數學 + 乘法反元素(逆元)

首先，依照感染源將小朋友分成若干段區間，將每段視為同一種顏色，排列方式為 $n! / (n1! * n2! * n3! * ...)$ ，其中 $n1$ , $n2$ , $n3$ , … 為各段的長度
再來考慮每個區間的感染方式：
- 對於只有一側感染的區間(最左和最右)，其感染的方法數只有 $1$ 種
- 對於兩側都感染的區間，其每次都能感染區間內最左或最右人，但最後一次只剩下一個人，故感染的方法數為 $2 ^ (d_i - 1)$ 種，其中 $d_i$ 為該區間的長度
範例：sick = [0, 4, 8, 12], n = 16, XaaaXbbbXcccXddd (X表感染)
- 非感染區間的長度分別為 0, 3, 3, 3, 3，總長度為 12
- 所求為 $12! / (3! * 3! * 3! * 3!) * 2 ^ {3 - 1} * 2 ^ {3 - 1} * 2 ^ {3 - 1}$
根據題目限制，區間長度為 $10^5$ ，預先處理 $[1, 10^5]$ 內的所有階層，因為數字可能會很大，所以計算時對 $(10^9 +7)$ 取餘數。
對於 m = (a / b) % MOD 的問題，因為除法不能用同餘定理，我們需要將除法轉換成乘法，也就是取 b 在模MOD下的乘法反元素，記做 $inv(b, MOD)$ $in v (b, MO D)$
- (a / b) % MOD = (a * inv(b, MOD)) % MOD = (a % MOD * inv(b, MOD) % MOD) % MOD
- 而 inv(b, MOD) = b ^ (MOD - 2) % MOD，證明如下：
- b * inv(b, MOD) = 1 % MOD
- b * inv(b, MOD) = b ^ (MOD - 1) % MOD (費馬小定理)
- inv(b, MOD) = b ^ (MOD - 2) % MOD ，得證

類題

🔴 1916. Count Ways to Build Rooms in an Ant Colony 2486

MAX_N = 10 ** 5
MOD = 10 ** 9 + 7

fac = [1]
for i in range(1, MAX_N+ 1): # 計算階乘
    fac.append(fac[-1] * i % MOD)

def inv(x): # 求 x 在 MOD 下的乘法逆元(乘法反元素)
    return pow(x, MOD-2, MOD)
    
class Solution:
    def numberOfSequence(self, n: int, sick: List[int]) -> int:
        dl = sick[0] # 最左段的長度
        dr = n - 1 - sick[-1] # 最右段的長度
        ans = fac[n - len(sick)] # n - len(sick) 為非感染區間的總長度
        for i in range(1, len(sick)): # 枚舉存在兩側感染的區間
            di = sick[i] - sick[i-1] - 1 # 兩個感染源之間的長度
            if di == 0:
                continue
            ans = ans * pow(2, di-1, MOD) % MOD # 2 ^ (di - 1)，此感染區間的感染方式數
            ans = ans * inv(fac[di]) % MOD # 除去這個區間內重複的排列方式
        ans = ans * inv(fac[dl]) * inv(fac[dr]) # 除去左右兩端區間內的重複排列方式
        return ans % MOD