LeetCode Weekly Contest 375 解題紀錄

這兩次週賽都已經做到10分鐘內寫完Q1、Q2了，Q3一開始用前綴和 + 雜湊表統計吃了TLE 。先去看Q4發現就是區間合併的問題，但忘了用 $qpow$ ，吃了 RE 。回去看Q3發現是滑動窗口，喜提第一次 AK 4題！

All problems solved by python

Q1: 🟢 2960. Count Tested Devices After Test Operations 1169

tags: `陣列(Array)` `模擬(Simulation)` `差分陣列(Difference Array)` `前綴和(Prefix Sum)`

題意

給定一個長度為 $n$ 的整數陣列 $batteryPercentages$ ，表示 $n$ 個裝置的電池百分比，你的任務是按照順序測試每個設備 $i$ ，執行以下測試操作：

如果 $batteryPercentages[i] > 0$ $ba tt ery P erce n t a g es [i] > 0$ ：
- 增加答案數，表示已測試設備的計數。
- 將下標在 $[i + 1, n - 1]$ 的所有設備的電池百分比減少 $1$ ，確保它們的電池百分比不會低於 $0$ ，即 $batteryPercentages[j] = max(0, batteryPercentages[j] - 1)$ 。
- 移動到下一個裝置。
否則，請移動到下一個設備而不執行任何測試。
返回已測試設備的數量。

思路：直接模擬 / 差分陣列

方法一：直接模擬

按照題目要求模擬即可
時間複雜度 $O(n^2)$

方法二：差分陣列

對於每個設備，其需要減少的電量為前面已測試設備的數量，因此若前面已測試設備的數量大於當前電量，則當前設備不需要測試。
時間複雜度 $O(n)$

class Solution:
    def countTestedDevices(self, batteryPercentages: List[int]) -> int:
        n = len(batteryPercentages)
        ans = 0
        for i, b in enumerate(batteryPercentages):
            if b > 0:
                batteryPercentages[i] += 1
                for j in range(i+1, n):
                    batteryPercentages[j] = max(0, batteryPercentages[j]-1)
                ans += 1
        return ans

class Solution:
    def countTestedDevices(self, batteryPercentages: List[int]) -> int:
        ans = 0
        for i, x in enumerate(batteryPercentages):
            if x - ans > 0:
                ans += 1
        return ans

Q2: 🟡 2961. Double Modular Exponentiation 1451

tags: `模擬(Simulation)` `快速冪(Fast Power)` `數學(Math)` `陣列(Array)`

題意

給定一個二維陣列 $variables$ ，其中 $variables[i] = [a_i, b_i, c_i, m_i]$ ，以及一個整數 $target$ 。求滿足 $((a_i^{b_i} \mod 10)^{c_i} \mod m_i) = target$ 的 $i$ 的集合。

思路：暴力 + 快速冪

對於每個 $i$ ，計算 $((a_i^{b_i} \mod 10)^{c_i} \mod m_i)$ 即可。
對於 $a^b \mod m$ $a^{b} mod m$ ，可以使用快速冪計算，時間複雜度 $O(\log b)$ $O (lo g b)$
- Python 中， $pow(a, b, m)$ 可以直接計算 $a^b \mod m$ ，時間複雜度 $O(\log b)$
時間複雜度 $O(n \log U)$ ，其中 $n$ 為 $variables$ 的長度， $U$ 為 $b_i, c_i$ 的最大值。

class Solution:
    def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:
        ans = []
        for i, (a, b, c, m) in enumerate(variables):
            if pow(pow(a, b, 10), c, m) == target:
                ans.append(i)
        return ans

類題

🟡 50. Pow(x, n)

Q3: 🟡 2962. Count Subarrays Where Max Element Appears at Least K Times 1701

tags: `陣列(Array)` `滑動窗口(Sliding Window)` `前綴和(Prefix Sum)` `二分搜尋(Binary Search)`

題意

給定一個整數陣列 $nums$ 和一個正整數 $k$ 。統計有多少個子陣列滿足「 $nums$ 中的最大元素至少出現 $k$ 次」，並返回滿足這一條件的子陣列的數目。

思路：滑動窗口 / 前綴和 + 二分搜索

方法一：滑動窗口

讓窗口保持在向左擴張1次就能滿足條件的狀態，即保證 $[left-1, right]$ 中 $mx$ 出現的次數恰好為 $k$ 。
由於上述性質，對於每個 $right$ ，都可以往左擴張 $left$ 次，使其滿足題目條件，因此答案增加 $left$ 。
以 $nums=[1,3,2,3,2,3]$ $n u m s = [1, 3, 2, 3, 2, 3]$ , $k=2$ $k = 2$ 為例， $mx=3$ $m x = 3$ ：
- $right=0$ ， $left=0$ ， $cnt=0$ ， $left=0$ ， $ans+=0=0$ 。
- $right=1$ ， $left=0$ ， $cnt=1$ ， $left=0$ ， $ans+=0=0$ 。
- $right=2$ ， $left=0$ ， $cnt=1$ ， $left=0$ ， $ans+=0=0$ 。
- $right=3$ ， $left=2$ ， $cnt=1$ ， $left=2$ ， $ans+=2=2$ 。
- $right=4$ ， $left=2$ ， $cnt=1$ ， $left=2$ ， $ans+=2=4$ 。
- $right=5$ ， $left=4$ ， $cnt=1$ ， $left=4$ ， $ans+=4=8$ 。
時間複雜度 $O(n)$

方法二：前綴和 + 二分搜索

先用前綴和 $pre$ 統計 $nums$ 中最大元素出現的次數，則 $pre[i]$ 表示 $nums[:i]$ 中 $mx$ 出現的次數。
對於每個左端點 $i$ ，找到 $pre[i] + k$ 的位置 $j$ ，則 $nums[i:j]$ 中 $mx$ 出現的次數恰好為 $k$ ，subarray可以繼續向右，故延伸答案增加 $n - (j - 1)$ 。
還是以 $nums=[1,3,2,3,2,3]$ $n u m s = [1, 3, 2, 3, 2, 3]$ , $k=2$ $k = 2$ 為例， $mx=3$ $m x = 3$ ， $pre=[0, 0, 1, 1, 2, 2, 3]$ $p re = [0, 0, 1, 1, 2, 2, 3]$ ：
- $i=0$ ， $j=4$ ， $nums[i:j]=[1,3,2,3]$ ， $ans+=3=3$ 。
- $i=1$ ， $j=4$ ， $nums[i:j]=[3,2,3]$ ， $ans+=3=6$ 。
- $i=2$ ， $j=6$ ， $nums[i:j]=[2,3,2,3]$ ， $ans+=1=7$ 。
- $i=3$ ， $j=6$ ， $nums[i:j]=[3,2,3]$ ， $ans+=1=8$ 。
- $i=4$ ， $j=7$ ， $nums[i:j]=[2,3]$ ， $ans+=0=8$ 。(此時已經找不到滿足條件的j了)
- $i=5$ ， $j=7$ ， $nums[i:j]=[3]$ ， $ans+=0=8$ 。
時間複雜度 $O(n \log n)$

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        mx = max(nums)

        ans = 0
        cnt = 0 # count of mx
        left = 0
        for right in range(n):
            if nums[right] == mx:
                cnt += 1
            while cnt == k: # 讓窗口保持在 left -= 1 就能滿足 cnt == k 的狀態
                if nums[left] == mx:
                    cnt -= 1
                left += 1
            ans += left
        return ans

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        mx = max(nums)

        pre = [0]
        for num in nums:
            pre.append(pre[-1] + (num == mx))
        ans = 0
        for i in range(n): # 對於每個 i，找到 pre[i] + k 的位置
            j = bisect_left(pre, pre[i] + k)
            ans += n - (j - 1)
        return ans

類題

Q4. 🔴 2963. Count the Number of Good Partitions 1985

tags: `區間合併(Interval Merge)` `快速冪(Fast Power)` `陣列(Array)` `排序(Sorting)` `雜湊表(Hash Table)` `數學(Math)` `組合數學(Combinatorics)`

題意

給定一個由 正整數 組成的陣列 $nums$ ，將其分割成一個或多個連續子陣列，如果不同子陣列中不包含相同數字，則認為是一種 好分割方案。求好分割方案的數目。
由於答案可能很大，返回對 $10^9 + 7$ 取餘的結果。

思路：區間合併

題目要求相同數字必在同一個子陣列中，因此可以將每個數字出現的位置視為一個區間，對於重疊的區間，需合併成一個區間，則問題變為「求合併後的區間數量」。
若剩下區間數量為 $m$ ，則有 $m-1$ 個位置可選擇連接或不連接，可能的分割方案數量為 $2^{m-1}$ 種。
對於每個數字，可以使用雜湊表統計其出現的最左和最右位置，再將區間按照最左位置排序，即可合併區間。
- 若當前區間的左端點大於前一個區間的右端點，則不重疊，新增當前區間。
- 否則當前區間與前一個區間重疊，更新前一個區間的右端點。
對於 $a^b \mod m$ $a^{b} mod m$ ，可以使用快速冪計算，時間複雜度 $O(\log b)$ $O (lo g b)$
- Python 中， $pow(a, b, m)$ 可以直接計算 $a^b \mod m$ ，時間複雜度 $O(\log b)$
時間複雜度 $O(n \log n)$ ，其中 $n$ 為 $nums$ 的長度，排序的時間複雜度為 $O(n \log n)$ ，合併區間的時間複雜度為 $O(n)$ 。
空間複雜度 $O(n)$ ，用來存放雜湊表和合併後的區間。

class Solution:
    def numberOfGoodPartitions(self, nums: List[int]) -> int:
        MOD = 10 ** 9 + 7
        # 區間
        n = len(nums)
        cnt = defaultdict(list) # 每個數字出現的最左和最右位置
        for i, num in enumerate(nums):
            cnt[num].append(i)

        # 區間合併
        intervals = []
        for num, indices in cnt.items():
            intervals.append((indices[0], indices[-1]))
        intervals.sort(key=lambda x: x[0])

        res = []
        for x, y in intervals:
            if not res or x > res[-1][1]: # not overlap
                res.append([x, y])
            else:
                res[-1][1] = max(res[-1][1], y) # overlap, update interval
        return pow(2, len(res) - 1, MOD)