🟢 3856. Trim Trailing Vowels 1140

tags: 字串(String)

Problem Statement

題目簡述

給定一個由小寫英文字母組成的字串 s，移除其所有尾部母音（a, e, i, o, u）後回傳結果字串。

Constraints

約束條件

  • 1≤s.length≤1001 \le s.length \le 100
  • s 僅由小寫英文字母組成

思路：反向掃描

從字串尾端向前掃描，跳過所有母音字元，找到第一個非母音字元的位置 i，回傳 s[:i+1] 即可。

庫函數寫法

Python 內建的 str.rstrip() 可以直接移除尾部指定字元集合：s.rstrip("aeiou")。

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n)
  • 空間複雜度：O(n)\mathcal{O}(n)，回傳的新字串

Code

1
2
3
4
5
6
7
class Solution:
    def trimTrailingVowels(self, s: str) -> str:
        # return s.rstrip("aeiou")
        i = len(s) - 1
        while i >= 0 and s[i] in "aeiou":
            i -= 1
        return s[:i + 1]

🟡 3857. Minimum Cost to Split into Ones 1322

tags: 動態規劃(Dynamic Programming), 記憶化搜索(Memoization), 數學(Math), 圖論(Graph Theory), 等價轉化(Equivalence Transformation)

Problem Statement

題目簡述

給定一個整數 nn。
每次操作可以將一個整數 xx 拆分為兩個正整數 aa 和 bb（滿足 a+b=xa+b=x），其代價為 a×ba \times b。
求將 nn 拆分為 nn 個 11 的最小總代價。

Constraints

約束條件

  • 1≤n≤5001 \le n \le 500

思路

這道題從直觀上看，是一個經典的尋找最優解的動態規劃問題。然而，在深入分析後，我們會發現其背後隱藏著一個優美的圖論結論：無論採取何種拆分順序，最終的總代價都是一個固定值。

方法一：記憶化搜索 (Memoization)

首先，從最直覺的角度出發，如果我們要計算拆分 nn 的最小代價，可以嘗試枚舉所有可能的拆分方式。

給定整數 nn，我們可以將其拆分為兩個正整數 xx 和 n−xn-x。為了避免重複計算並利用對稱性，可以讓 xx 從 11 遍歷到 ⌊n2⌋\lfloor \frac{n}{2} \rfloor。
每次拆分後，總代價等於「當次拆分的代價 x×(n−x)x \times (n-x)」加上「繼續拆分 xx 的最小代價」與「繼續拆分 n−xn-x 的最小代價」。

我們可以利用記憶化搜索（Memoization）來記錄已經計算過的結果，避免重複展開相同的子問題。

狀態轉移方程式如下：

dfs(n)=min⁡1≤x≤⌊n2⌋(dfs(x)+dfs(n−x)+x⋅(n−x))\text{dfs}(n) = \min_{1 \le x \le \lfloor \frac{n}{2} \rfloor} (\text{dfs}(x) + \text{dfs}(n-x) + x \cdot (n-x))

遞迴邊界：當 n=1n=1 時，已無法再拆分，代價為 00。

複雜度分析

  • 時間複雜度：O(n2)\mathcal{O}(n^2)，共 nn 個狀態，每個狀態枚舉約 n2\frac{n}{2} 次。
  • 空間複雜度：O(n)\mathcal{O}(n)。

方法二：數學推導（完全圖斷邊模型）

在補題才發現，本題除了動態規劃之外，還可以使用數學推導的方法來做到 O(1)O(1) 的時間複雜度。

如果我們仔細觀察題意中的代價計算方式 a×ba \times b，可以將其巧妙地對映到圖論中的「完全圖（Complete Graph）」模型。

我們可以將拆分問題轉換為以下過程：

  1. 初始狀態：想像有一個包含 nn 個節點的完全圖，任意兩個節點之間皆有一條無向邊。總邊數為 C(n,2)=n(n−1)2C(n,2) = \frac{n(n-1)}{2} 條。
  2. 拆分操作的對映：將大小為 x=a+bx=a+b 的集合拆分為大小為 aa 和 bb 的兩個子集，這相當於將這 xx 個節點劃分成 AA 和 BB 兩組。
  3. 操作代價的本質：劃分後，組 AA 到組 BB 之間所有的連邊都被切斷了。因為 AA 有 aa 個節點、BB 有 bb 個節點，被斷開的邊數剛好是 a×ba \times b 條！也就是說，題目的拆分代價，等價於被斷開的邊數。
  4. 遞迴與終止：對已經分開的各組繼續遞迴拆分，直到所有組別的大小都變為 11（即圖中只剩下孤立的節點，無法再切斷任何邊為止）。
關鍵洞察

當所有節點最終全都被拆成單獨的 11 時，代表初始狀態下這張完全圖中的所有邊都已經被徹底斷開。
既然無論採取什麼順序去拆分，最終得到的都是 nn 個孤立的點，那麼總共被斷開的邊數必定等於初始的總邊數 C(n,2)C(n,2)。

這意味著，無論如何去拆分，總結算代價必定是一個常數：n(n−1)2\frac{n(n-1)}{2}。

複雜度分析

  • 時間複雜度：O(1)\mathcal{O}(1)。
  • 空間複雜度：O(1)\mathcal{O}(1)。

參考資料

Code

方法一：記憶化搜索 (Memoization)

將記憶化函數寫在主函數之外，方便在不同測試用例中共享。

1
2
3
4
5
6
7
8
9
10
11
12
@cache
def dfs(n: int) -> int:
    if n == 1:
        return 0
    res = float("inf")
    for x in range(1, n // 2 + 1):
        res = min(res, dfs(x) + dfs(n - x) + x * (n - x))
    return res

class Solution:
    def minCost(self, n: int) -> int:
        return dfs(n)

方法二：數學推導（完全圖斷邊模型）

1
2
3
class Solution:
    def minCost(self, n: int) -> int:
        return n * (n - 1) // 2

🟡 3858. Minimum Bitwise OR From Grid 1947

tags: 貪心(Greedy), 位運算(Bit Manipulation), 試填法

Problem Statement

題目簡述

給定一個大小為 m×nm \times n 的整數矩陣 grid。
你必須從每一橫列(row)中恰好選擇一個整數，求出所有選定整數的最小可能位元或（Bitwise OR）。

Constraints

約束條件

  • 1≤m×n≤1051 \le m \times n \le 10^5
  • 1≤grid[i][j]≤1051 \le grid[i][j] \le 10^5

思路：試填法（從高位貪心）

注意

第 b 位是指二進位底數從 00 開始計算的位元位置（即代表數值 2b2^b 的位置）。例如最低位為第 00 位、次低位為第 11 位。

位元或的性質是「只增不減」——一旦某個位元被設為 1，就無法消去。因此高位的 1 對結果的影響遠大於所有低位的總和，我們應盡力讓高位為 0。

貪心策略

從最高位到最低位，逐位判斷答案 ans 的第 b 位能否為 0：

  • 能為 0：每一橫列(row)都存在至少一個數字 x，使得選它不會在第 b 位及更高位引入多餘的 1。此時保持第 b 位為 0，繼續處理下一位。
  • 必須為 1：某一橫列(row)的所有數字都無法滿足上述條件，說明該列無論怎麼選都會發生衝突（迫使第 b 位或更高位出現不該有的 1）。因為更高位在先前的步驟中已經驗證並固定，只需令當前的第 b 位為 1（即 ans |= (1 << b)）即可，然後處理下一位。

判定條件

對於候選數字 x，我們可以用以下條件驗證「假設第 b 位為 0，選 x 是否相容」：

((x∣ans)≫b)≪b=ans((x \mid ans) \gg b) \ll b = ans

理解這個條件

>> b << b 的作用是清除低於第 b 位（<b< b）的所有位元。由於我們從高到低填入，ans 在 ≤b\le b 的位元此刻一定全為 0，而第 b 位我們正好需要假設為 0。
因此等式成立代表：x | ans 在 ≥b\ge b 的位元與 ans 完全一致——x 既沒有在已確定為 0 的高位引入 1，也沒有在第 b 位產生 1。

複雜度分析

  • 時間複雜度：O(B⋅m⋅n)\mathcal{O}(B \cdot m \cdot n)，其中 B=log⁡2(105)≈17B = \log_2(10^5) \approx 17，m⋅n≤105m \cdot n \le 10^5。
  • 空間複雜度：O(1)\mathcal{O}(1)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minimumOR(self, grid: List[List[int]]) -> int:
        ans = 0
        B = max(map(max, grid)).bit_length()
        # 判斷 ans 的第 b 位是否可以為 0
        for b in range(B - 1, -1, -1):
            for row in grid:
                for x in row:
                    if ((x | ans) >> b) << b == ans:
                        break
                else:
                    # 在高位的限制下，第 b 位只能為 1
                    ans |= (1 << b)
                    break
        return ans

🔴 3859. Count Subarrays With K Distinct Integers 2302

tags: 雙指標(Two Pointers), 滑動窗口(Sliding Window), 雜湊表(Hash Table)

Problem Statement

題目簡述

給定一個整數陣列 nums 和兩個整數 k 與 m。
求出滿足以下兩個條件的子陣列數量：

  1. 子陣列中恰好包含 k 個不同的數字。
  2. 子陣列中的每個不同數字，都出現至少 m 次。

Constraints

約束條件

  • 1≤nums.length≤1051 \le nums.length \le 10^5
  • 1≤nums[i]≤1051 \le nums[i] \le 10^5
  • 1≤k,m≤nums.length1 \le k, m \le nums.length

思路：恰好型滑動窗口

隨著窗口的範圍變大，窗口內不同整數的數量與每個整數出現的頻率都是單調遞增的，因此可以用滑動窗口解題。

本題的難點在於「恰好包含 kk 個不同整數」。但所有「恰好 kk 個」的計數問題，都可以透過差分轉化為：「至少 kk 個」減去「至少 k+1k+1 個」，或是「至多 kk 個」減去「至多 k−1k-1 個」。

轉化技巧

恰好 kk 個 == (至少 kk 個) −- (至少 k+1k+1 個)
恰好 kk 個 == (至多 kk 個) −- (至多 k−1k-1 個)
這是處理「恰好型滑動窗口」的經典手法。

以本題為例，因為恰好只有 kk 個不同數字，所以條件可轉化為：

  • 「子陣列至少包含 kk 個不同整數，且至少 kk 個整數出現次數 ≥m\ge m」
  • 減去「子陣列至少包含 k+1k+1 個不同整數，且至少 kk 個整數出現次數 ≥m\ge m」
為什麼兩個條件都是「至少 kk 個整數出現次數 ≥m\ge m」？

因為我們在這裡的容斥目標只是為了精確定位「恰好 kk 個不同整數」，而把「有 kk 個整數頻率達標」當作一個固定的門檻。
如果在減去大範圍時，將條件改成「至少 k+1k+1 個達標」，就會漏扣掉「有 k+1k+1 種數字，但只有 kk 種數字達標」的不合法子陣列！

定義 calc(lim) 計算「至少 lim 種不同數字、且至少 k 種數字出現 ≥m\ge m 次」的子陣列數，則：

Ans=calc(k)−calc(k+1)\text{Ans} = \text{calc}(k) - \text{calc}(k + 1)

calc(lim) 用標準滑動窗口實作：右端 right 每次右移一格，將 nums[right] 加入哈希表 cnt，並用 good 記錄出現次數 ≥m\ge m 的種類數。當條件滿足時，不斷右移 left 直到條件被破壞，此時以 right 為結尾的有效子陣列數量恰為 left。

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n)，因為 calc 函數中 left 和 right 指針都只會不斷向右移動，最多遍歷陣列一次，哈希表操作時間為 O(1)\mathcal{O}(1)。呼叫兩次函數總時間仍為 O(n)\mathcal{O}(n)。
  • 空間複雜度：O(n)\mathcal{O}(n)，最糟情況下哈希表需儲存 nn 個不同的數字。

類題

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def countSubarrays(self, nums: list[int], k: int, m: int) -> int:
        # 當有至少 lim 個不同的數字、且有 k 個數字出現至少 m 次時，有多少個子陣列符合條件
        def calc(lim: int) -> int:
            res = left = good = 0
            cnt = defaultdict(int)
            for right, x in enumerate(nums):
                cnt[x] += 1
                if cnt[x] == m:
                    good += 1
                while len(cnt) >= lim and good >= k:
                    y = nums[left]
                    if cnt[y] == m:
                        good -= 1
                    cnt[y] -= 1
                    if cnt[y] == 0:
                        del cnt[y]
                    left += 1
                res += left
            return res
        # 恰好 k 個 = 至少 k 個 - 至少 k + 1 個
        return calc(k) - calc(k + 1)

寫在最後

PROMPT

masterpiece, best quality, high quality, good quality, 32K UHD, colorful, official art, illustration, in the style of fashion photography, dynamic, dynamic force picture, (Visual impact:1.2), impactful picture, extreme aesthetic, A shot with tension, sharp focus, The Ninth Art, depth of field, cinematic lighting, light particles, lens flare, movie perspective, (Tyndall Effect:1.4), light particles, light, shadow, scenery, temperate atmosphere, (artist:pigeon666:0.83), (Yomu:0.4), (remsrar:0.45), (quasarcake:0.3),

1girl, solo, tachibana sherry, yellow eyes, blue hair, short hair, hair ornament, braid, hair rings, braided hair rings, hat, black headwear, blue necktie, necktie, black necktie bow, black capelet, grey vest, collared shirt, long sleeves, blue skirt, pleated skirt, plaid skirt, frilled skirt, single thighhigh, footwear bow, frilled socks, asymmetrical legwear, single leg pantyhose, black pantyhose, playful pose, hands near head, cat pose, smiling, open mouth, looking at viewer, bust shot, close-up, blue sky background, cloudless sky, white bird, mascot, floating bird, sparkles, shining, star (symbol), bright lighting, vibrant colors, high-key lighting,

The character is captured in a vibrant close-up bust shot, posing playfully with her hands raised near her head in a charming, cat-like gesture. She gazes directly at the viewer with shimmering yellow eyes and a beaming, joyful smile that radiates energy. The background is a crisp, brilliant blue sky adorned with floating white stars and a small, round white bird mascot hovering nearby. Sunlight drenches the scene, creating high-contrast shadows and a brilliant glow that emphasizes the vivid blue of her hair and the clean aesthetic of her silhouette, resulting in a lively and heart-warming atmosphere.

本場 VP，以下銳評：

  • Q2: 很有趣的題目，等價轉化的思路太妙了！
  • Q3: 感覺已經變成套路了
  • Q4: 因為之前不小心瞄到了影片標題，所以一下就出來了，賽時應該不可能這麼順利