LeetCode Weekly Contest 373 解題紀錄

這次40分鐘做出了前三題，Q1沒注意 $k$ 可能比 $n$ 大吃了一發 WA ；Q2雖然相較Q4的範圍小，但一開始寫得太暴力了吃了 TLE ；Q3很快想到了用分組討論，直接 AC 了；Q4前兩個關鍵點都想到了，只差用兩個限制條件去做統計了，可惜了。

All problems solved by python

Q1: 🟢 2946. Matrix Similarity After Cyclic Shifts 1406

tags: `陣列(Array)` `數學(Math)` `矩陣(Matrix)` `模擬(Simulation)`

題意

給定一個下標從 $0$ 開始且大小為 $m x n$ 的整數矩陣 $mat$ 和整數 $k$ 。將矩陣中的奇數行循環右移 $k$ 次，偶數行循環左移 $k$ 次。如果初始矩陣和最終矩陣完全相同，則傳回 true ，否則傳回 false 。

思路：模擬

切片模擬即可，注意 $k$ 可能比 $n$ 大，所以要取模。
向左移動 $k$ 次和原本的列相同，等於向右移動 $k$ 次和原本的列相同，所以不用特別處理左移右移的問題。

class Solution:
    def areSimilar(self, mat: List[List[int]], k: int) -> bool:
        m, n = len(mat), len(mat[0])
        if k > n:
            k %= n
        for row in mat:
            if row[-k:] + row[:-k] != row:
                return False
        return True

Q2: 🟡 2947. Count Beautiful Substrings I 1451

tags: `字串(String)` `前綴和(Prefix Sum)` `枚舉(Enumeration)`

題意

給定一個字串 $s$ 和一個正整數 $k$ ， $s$ 中的母音字母和子音字母的數量分別用 $vowels$ 和 $consonants$ 表示。如果 $s$ 滿足以下條件，則稱為 beautiful ：

vowels == consonants，即母音字母和子音字母的數量相等。
(vowels * consonants) \% k == 0 ，即母音字母和子音字母的數量的乘積能被 $k$ 整除。

返回字串 $s$ 中 non-empty beautiful substrings 的數量。

限制：

$1 <= s.length <= 1000$
$1 <= k <= 1000$

思路：前綴和 + 暴力枚舉

直接暴力會 TLE ，用前綴和紀錄母音字母和子音字母的數量，然後枚舉所有子字串，判斷是否符合條件即可。

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        ans = 0
        vowels = consonants = 0
        pre_v = [0] * (n+1)  
        pre_c = [0] * (n+1)
        for i in range(n):
            if s[i] in "aeiou":
                vowels += 1
            else:
                consonants += 1
            pre_v[i+1] = vowels
            pre_c[i+1] = consonants
        for i in range(n): # 枚舉起點
            for j in range(i + 1, n+1): # 枚舉終點
                vowels = pre_v[j] - pre_v[i]
                consonants = pre_c[j] - pre_c[i]
                if vowels == consonants and vowels * consonants % k == 0:
                    ans += 1
        return ans

Q3: 🟡 2948. Make Lexicographically Smallest Array by Swapping Elements 2047

tags: `分組循環` `排序(Sorting)` `並查集(Union Find)` `互斥集(Disjoint Sets)` `陣列(Array)`

題意

給定下標從 $0$ 開始的 Array $nums$ 和一個正整數 $limit$ 。
在每次操作中，可以選擇任兩個下標 $i$ 和 $j$ ，如果滿足 $|nums[i] - nums[j]| <= limit$ ，則交換 $nums[i]$ 和 $nums[j]$ 。
返回執行任意次操作後能得到的 lexicographically smallest array。
- 注意：這裡的字典序是以元素做定義的，例如， $[2,10,3]$ 比陣列 $[10,2,3]$ 字典序更小，下標 0 處是兩個陣列第一個不同的位置，且 $2 < 10$ 。

思路：分組討論(分組循環) + 排序

可以從觀察範例中得出，若一組數字裡面的元素可以互相交換，則這組數字中連續兩個數字的差值一定 $\leq limit$ 。
先把 $nums$ 依照數值大小由小到大排序，並記錄原本的下標。
由小到大枚舉 $nums$ 中的每個元素，假設當前枚舉到的元素為 $num_i$ ，則我們要找到所有可以與 $num_i$ 交換的元素，也就是差值小於等於 $limit$ 的元素，並將這組數字中的最後一個下標記錄下來。
對於同一組內的元素，我們可以任意交換，所以我們可以把元素小的放在前面，元素大的放在後面，這樣就可以保證字典序最小，這裡用了Min Heap來實現，用排序也可以。
時間複雜度： $O(nlogn)$

類題

🟡 1202. Smallest String With Swaps 1855

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        n = len(nums)
        ans = [0] * n

        lst = [(num, idx) for idx, num in enumerate(nums)]
        lst.sort()

        i = 0
        while i < n:
            num, idx = lst[i]
            hp_idx = []
            hp_num = []
            heappush(hp_idx, idx)
            heappush(hp_num, num)
            j = i + 1
            while j < n and lst[j][0] - lst[j-1][0] <= limit:
                heappush(hp_idx, lst[j][1])
                heappush(hp_num, lst[j][0])
                j += 1
            while hp_idx:
                ans[heappop(hp_idx)] = heappop(hp_num)
            i = j
        return ans

Q4: 🔴 2949. Count Beautiful Substrings II 2445

tags: `質因數分解` `雜湊表(Hash Table)` `字串(String)` `數學(Math)` `數論(Number Theory)` `前綴和(Prefix Sum)`

題意

同 Q2，但是 $s$ 的長度從 $1000$ 增加到 $5 * 10^4$ 。

$1 \leq s.length \leq 5 * 10^4$
$1 \leq k \leq 1000$

思路：質因數分解 + 前綴和 + 雜湊表

首先，由於條件1 $vowels = consonants$ ，所以當子字串長度為 $L$ ，則 $vowels = consonants = \frac{L}{2}$ 。故條件2可以改寫為 $\frac{L^2}{4} \bmod k = 0 \Rightarrow L^2 \bmod 4k =0$ 。
對 $4k$ $4 k$ 做質因子分解，得到 $4k = p_1^{a_1} * p_2^{a_2} * ... * p_n^{a_n}$ $4 k = p_{1}^{a_{1}} * p_{2}^{a_{2}} * ... * p_{n}^{a_{n}}$ ，其中 $p_i$ $p_{i}$ 為質數， $a_i$ $a_{i}$ 為指數。對於 $4k$ $4 k$ 的每個質因數 $p_i$ $p_{i}$ ，無論 $a_i$ $a_{i}$ 是奇數或偶數，皆滿足 $L \bmod p_i^{\lceil \frac{a_i}{2} \rceil} = 0$ $L mod p_{i}^{⌈ \frac{a _{i}}{2} ⌉} = 0$ ，故條件2可改寫成 $L \bmod k_2 = 0$ $L mod k_{2} = 0$ ，其中 $k_2 = p_1^{\lceil \frac{a_1}{2} \rceil} * p_2^{\lceil \frac{a_2}{2} \rceil} * ... * p_n^{\lceil \frac{a_n}{2} \rceil}$ $k_{2} = p_{1}^{⌈ \frac{a _{1}}{2} ⌉} * p_{2}^{⌈ \frac{a _{2}}{2} ⌉} * ... * p_{n}^{⌈ \frac{a _{n}}{2} ⌉}$ 。
- 但由於 $k \leq 1000$ ，可以直接暴力計算出 $k_2$ 。
再來，我們可以令前綴和 $pre\_sum[i]$ 表示 $s$ 的前 $i$ 個字元中，母音字母的數量減去輔音字母的數量，或是可以將母音想成 $+1$ ，子音想成 $-1$ 。
若子字串 $s[i:j]$ $s [i : j]$ ( 左閉右開 $[i, j)$ $[i, j)$ ) 為 beautiful ，則需滿足
1. $pre\_sum[j] - pre\_sum[i] = 0$ ，即 $s[i:j]$ 中母音字母和輔音字母的數量相等。
2. 滿足 $L \bmod k_2 = 0$ ，即 $(j - i) \bmod k_2 = 0 \Rightarrow i \bmod k_2 = j \bmod k_2$
故我們可以枚舉 $i$ ，並用雜湊表紀錄 $(i \bmod k_2, pre\_sum[i])$ 出現的次數，並在枚舉 $i$ 的同時計算答案。

類題

🟡 560. Subarray Sum Equals K
🟡 974. Subarray Sums Divisible by K 1676
🟡 1590. Make Sum Divisible by P 2039
🟡 523. Continuous Subarray Sum
🟡 525. Contiguous Array
🟡 1915. Number of Wonderful Substrings 2235
🟡 930. Binary Subarrays With Sum 1592
🟡 1371. Find the Longest Substring Containing Vowels in Even Counts 2041
🔴 1542. Find Longest Awesome Substring 2222

題單來自：@灵茶山艾府

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        # 1. 對 4k 做質因數分解
        k = 4 * k
        for p in range(int(k**0.5), 1, -1): # k <= 1000
            if k % (p ** 2) == 0:
                k //= p
                break

        # 2. 前綴和
        vowels_set = set("aeiou")
        pre_sum = [0]
        for ch in s:
            x = 1 if ch in vowels_set else -1
            pre_sum.append(pre_sum[-1] + x)

        # 3. 雜湊表，統計 (i % k, pre_sum[i]) 出現的次數
        ans = 0
        cnt = Counter()
        for i, s in enumerate(pre_sum):
            p = (i % k, s)
            ans += cnt[p]
            cnt[p] += 1
        return ans