LeetCode Weekly Contest 492 解題紀錄

🟢 3861. Minimum Capacity Box _

tags: 陣列(Array), 模擬(Simulation)

Problem Statement

題目簡述

給定一個整數陣列 capacity 表示各個箱子的容量，以及一個整數 itemSize 表示要放入的物品大小。
請找出能裝下物品（即容量 $\ge$ itemSize）的箱子中，容量最小的箱子的索引。
如果有多個箱子符合「能裝下且容量最小」的條件，則回傳其中索引最小的。若沒有任何箱子能裝下物品，則回傳 -1。

Constraints

約束條件

• $1 \le \text{capacity.length} \le 10^5$
• $1 \le \text{capacity}[i], \text{itemSize} \le 10^9$

---

思路：一次遍歷 (One Pass)

線性掃描陣列，維護目前容量最小且能裝下物品的箱子索引 ans。對每個箱子，若 c >= itemSize 且容量比目前最佳更小，就更新 ans。

複雜度分析

• 時間複雜度：$\mathcal{O}(n)$，其中 $n$ 是 capacity 陣列的長度。僅需線性掃描陣列一次。
• 空間複雜度：$\mathcal{O}(1)$，僅使用了常數個額外的追蹤變數。

---

Code

class Solution:
    def minimumIndex(self, capacity: list[int], itemSize: int) -> int:
        ans = -1
        for i, c in enumerate(capacity):
            if c >= itemSize and (ans == -1 or c < capacity[ans]):
                ans = i
        return ans

---

🟡 3862. Find the Smallest Balanced Index _

tags: 陣列(Array), 前綴和(Prefix Sum)

Problem Statement

題目簡述

給定一個整數陣列 nums。
一個索引 i 被稱為 平衡 (balanced) 的條件為：i 左側元素的 總和 等於 i 右側元素的 乘積。
（若左側沒有元素，總和視為 $0$；若右側沒有元素，乘積視為 $1$。）
請回傳 最小的 平衡索引。若沒有平衡索引存在，則回傳 $-1$。

Constraints

約束條件

• $1 \le \text{nums.length} \le 10^5$
• $1 \le \text{nums}[i] \le 10^9$

---

思路：前後綴分解

答案的唯一性

因為 $\text{nums}[i] \ge 1$，從右往左掃描時，左側前綴和 pre 單調遞減，右側後綴乘積 suf 單調遞增。
兩者變化方向相反，交點最多一個，故平衡索引若存在則唯一。

利用此單調性，我們從右向左遍歷，維護前綴和 pre 與後綴乘積 suf，並在 suf > pre 時剪枝。

為什麼要從右往左？

若從左往右遍歷，初始的後綴乘積是整個陣列的乘積，數值可達 $(10^9)^{10^5}$，根本無法計算。
反過來，從右往左時 suf 從 $1$ 開始逐步增長，搭配 suf > pre 的剪枝可以在 suf 變得過大之前提早終止，完全迴避了大數問題。

複雜度分析

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

---

Code

class Solution:
    def smallestBalancedIndex(self, nums: list[int]) -> int:
        n = len(nums)
        pre, suf = sum(nums), 1
        for i in range(n - 1, -1, -1):
            x = nums[i]
            pre -= x
            if suf > pre:  # 剪枝：若後綴乘積大於前綴和，則後續差距只會更大
                break
            if suf == pre:  # 因為答案是唯一的，所以找到即可返回
                return i
            suf *= x
        return -1

---

🟡 3863. Minimum Operations to Sort a String _

tags: 字串(String), 分類討論(Case Analysis), 貪婪(Greedy)

Problem Statement

題目簡述

給定一個由小寫英文字母組成的字串 s。
你可以執行操作：選擇 s 中一個 非整體 的子字串，並將其依英文字母順序重新排序。
請問最少需要幾次操作，才能使 s 變為按非遞減順序排列？如果不可能達成，請回傳 -1。

Constraints

約束條件

• $1 \le \text{s.length} \le 10^5$
• s 僅由小寫英文字母組成。

---

思路：分類討論

核心觀察

「選擇的子字串不能是整個字串」等價於：子字串不能同時包含 s[0] 和 s[-1]。
換言之，每次操作只能排序 s[0:j]（不含末字元）或 s[i:]（不含首字元）這類區間。
而排序更大的區間一定不虧（若 $A \subseteq B$，排序 $B$ 後 $A$ 也有序），所以每一步操作都應盡量選最大的真子字串：s[:-1] 或 s[1:]。

由此可知，若首字元或末字元已經在正確的位置上（s[0] == min(s) 或 s[-1] == max(s)），只需再排另一側就能一步搞定。
整個問題便化為：需要幾次操作才能把至少一端擺到正確位置？ 從小到大依序討論：

情況一：$k = 0$（已排序）

s 本身已經有序，不需任何操作，直接回傳 0。

情況二：$k = -1$（無解）

s 尚未排序且 $n = 2$：能選的真子字串只有 s[0:1] 和 s[1:2]，長度都是 $1$。對單一字元排序等於什麼都沒做，兩個字元的相對順序永遠不變，無解，回傳 -1。

情況三：$k = 1$（端點已就位）

首字元或末字元已經在正確的位置上，只需一步排好另一側：

• s[0] == min(s)：排序 s[1:] 即可。
• s[-1] == max(s)：排序 s[:-1] 即可。

情況四：$k = 3$（兩步才能達情況三）

唯一的極端情況

當 s[0] 是全域唯一最大值、s[-1] 是全域唯一最小值（即 s[0] == max(s) 且 s[-1] == min(s) 且兩者各只出現一次），s[1:-1] 中既無最大值也無最小值，無論先排哪一側都無法一步將任一端擺正。

此時需要 $2$ 步才能達到情況三，加上最後一步排序，共 $3$ 次：

1. 排序 s[:-1]：最大值被排到 s[-2]。
2. 排序 s[1:]：最大值被推到 s[-1]（就位），同時最小值被排到 s[1]。
3. 排序 s[:-1]：最小值被推到 s[0]（就位），整個字串有序。

情況五：$k = 2$（一步可達情況三）

排除以上所有情況後，s[1:-1] 中必然包含全域最小值或全域最大值（或兩者），只需一步就能將端點擺正，轉為情況三：

• 若 s[1:-1] 含最小值：先排序 s[:-1]，最小值被推到 s[0] → 變成情況三，再排序 s[1:]。共 $2$ 次。
• 若 s[1:-1] 含最大值：先排序 s[1:]，最大值被推到 s[-1] → 變成情況三，再排序 s[:-1]。共 $2$ 次。

複雜度分析

• 時間複雜度：$\mathcal{O}(n)$，判定有序性、最大最小值、字母頻率皆為線性掃描。
• 空間複雜度：$\mathcal{O}(|\Sigma|)$，其中 $|\Sigma|$ 為字元集大小，本題中 $|\Sigma| \le 26$。

---

Code

class Solution:
    def minOperations(self, s: str) -> int:
        n = len(s)
        if all(x <= y for x, y in pairwise(s)):
            return 0
        if n == 2:
            return -1

        cnt = Counter(s)
        mn, mx = min(s), max(s)
        if s[0] == mn or s[-1] == mx:
            return 1
        if s[0] == mx and s[-1] == mn and cnt[mx] == 1 and cnt[mn] == 1:
            return 3
        return 2

---

🔴 3864. Minimum Cost to Partition a Binary String _

tags: 分治(DivideAndConquer), 前綴和(PrefixSum), 遞迴(Recursion)

Problem Statement

題目簡述

給定一個二進位字串 s，以及兩個整數 encCost 和 flatCost。
我們可以將字串進行分割，初始時整個字串為一個區段。對於一長度為 $L$、且包含 $X$ 個 '1'（敏感元素）的區段：

• 若 $X = 0$，則成本為 flatCost。
• 若 $X > 0$，則成本為 $L \times X \times \text{encCost}$。

若區段長度為 偶數，你可以選擇將其切分為兩個長度 相等 的相鄰子區段，切割後的總成本為這兩個子區段的成本之和。
請問透過合法分割方案，可以達到的 最小總成本 是多少？

Constraints

約束條件

• $1 \le \text{s.length} \le 10^5$
• s 僅包含字元 '0' 與 '1'。
• $1 \le \text{encCost}, \text{flatCost} \le 10^5$

---

思路：分治法 (Divide and Conquer)

注意到題目的切割規則：偶數長度的區間只能從正中央等分為二，這恰好對應分治法的精神——切分方式唯一，子問題之間互不重疊（No Overlapping Subproblems），因此只需遞迴遍歷所有可能的分割並取最小值，完全不需要記憶化搜索 (Memoization)。

具體做法：先建立前綴和陣列 pre，以便 $\mathcal{O}(1)$ 查詢任意子區間內 '1' 的個數，再定義遞迴函式 dfs(l, r) 回傳區間 s[l..r] 的最小成本。

令區間長度 $L = r - l + 1$，敏感元素個數 $X = \text{pre}[r+1] - \text{pre}[l]$，中間點 $m = \lfloor \dfrac{l+r}{2} \rfloor$。

不分割的成本為：

$$\text{cost}(l, r) = \begin{cases} L \times X \times \text{encCost} & \text{if } X > 0 \\ \text{flatCost} & \text{if } X = 0 \end{cases}$$

狀態轉移方程式為：

$$\text{dfs}(l, r) = \begin{cases} \min\!\big(\text{cost}(l, r),\; \text{dfs}(l, m) + \text{dfs}(m+1, r)\big) & \text{if } L \text{ is even} \\ \text{cost}(l, r) & \text{if } L \text{ is odd} \end{cases}$$

複雜度分析

• 時間複雜度：$\mathcal{O}(n)$，可由 Master Theorem 證明。
• 空間複雜度：$\mathcal{O}(n)$，前綴和陣列需 $\mathcal{O}(n)$ 空間，遞迴呼叫堆疊最大深度為 $\mathcal{O}(\log n)$。

時間複雜度證明：Master Theorem

由分治法的遞迴方程式可知 $T(n) = 2T(n/2) + \mathcal{O}(1)$（每次精準切分為兩個規模減半的子問題，且依賴前綴和達成的合併成本為 $\mathcal{O}(1)$）。
根據 Master Theorem，$a = 2,\ b = 2$，由於 $f(n) = \mathcal{O}(1)$ 遠小於 $n^{\log_b a} = n^1$，符合主定理的第一種情況（Case 1），故總時間複雜度為 $\mathcal{O}(n^{\log_b a}) = \mathcal{O}(n)$。

---

Code

class Solution:
    def minCost(self, s: str, encCost: int, flatCost: int) -> int:
        n = len(s)
        pre = list(accumulate(map(int, s), initial=0))

        def dfs(l: int, r: int) -> int:
            ln = r - l + 1
            x = pre[r + 1] - pre[l]
            res = (ln * x * encCost) if x > 0 else flatCost
            if ln & 1 == 0:
                mid = (l + r) // 2
                res = min(res, dfs(l, mid) + dfs(mid + 1, r))
            return res

        return dfs(0, n - 1)

---

寫在最後

PROMPT

masterpiece, best quality, high quality, good quality, 32K UHD, colorful, official art, illustration, 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,

1girl, solo, sakuraba ema, pink eyes, x hair ornament, white hair, gradient hair, pink hair, black headwear, beret, hat flower, hairclip, short hair, black ribbon, shirt, flower, long sleeves, ribbon, hat, black choker, white shirt, brooch, white bowtie, white bow, jewelry, black jacket, frilled shorts, belt, o-ring thigh strap, lying gracefully on the floor in a dimly lit traditional Japanese room with tatami mats and sliding shoji screens, surrounded by scattered cherry blossom petals gently falling from above, soft sunlight rays streaming through the screens creating dramatic light beams and subtle shadows on her body, relaxed pose with one arm extended outward and legs slightly bent, serene half-closed eyes gazing softly upward, close-up cinematic composition from a low three-quarter angle emphasizing her elegant form and the ethereal atmosphere of petals drifting in the air, in the style of Alphonse Mucha, with intricate Art Nouveau floral patterns, flowing organic lines, and decorative elegance that enhances the delicate beauty and symbolic floral motifs around the character,

Alphonse Mucha is a renowned Art Nouveau artist known for his iconic poster designs featuring ethereal women intertwined with elaborate floral and decorative elements, characterized by sinuous curves, rich ornamental details, and a sense of graceful harmony; this style is applied here to infuse the scene with vintage poster-like sophistication, amplifying the cherry blossom theme through stylized, flowing petal motifs and elegant linework while preserving the character’s poised serenity

20 分鐘 AK，但 Q3 吃了 4 發 WA 🤡