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 ：

1. vowels == consonants，即母音字母和子音字母的數量相等。
2. (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$ 做質因子分解，得到 $4k = p_1^{a_1} * p_2^{a_2} * ... * p_n^{a_n}$，其中 $p_i$ 為質數，$a_i$ 為指數。對於 $4k$ 的每個質因數 $p_i$，無論$a_i$是奇數或偶數，皆滿足 $L \bmod p_i^{\lceil \frac{a_i}{2} \rceil} = 0$，故條件2可改寫成 $L \bmod 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 \leq 1000$ ，可以直接暴力計算出 $k_2$。
• 再來，我們可以令 前綴和 $pre\_sum[i]$ 表示 $s$ 的前 $i$ 個字元中，母音字母的數量減去輔音字母的數量，或是可以將母音想成 $+1$，子音想成 $-1$。
• 若子字串 $s[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

---