【待更新】LeetCode Biweekly Contest 118 解題紀錄

All problems solved by python

Q1. 🟢 2942. Find Words Containing Character 1182

題意

• 給定一個下標從 0 開始的字串陣列 $words$ 和一個字元 $x$ ，回傳一個 下標陣列，表示該下標在陣列中對應的單字包含字元 $x$ 。
• 可以以 任意順序 回傳答案。

思路：簡單模擬

• 模擬題，直接遍歷即可
• 時間複雜度： $O(L)$ ，其中 $L$ 為所有字串的長度總和。
• 空間複雜度： $O(1)$ ，不計算答案的空間。

class Solution:
    def findWordsContaining(self, words: List[str], x: str) -> List[int]:
        # return [idx for idx, word in enumerate(words) if x in word]
        ans = []
        for idx, word in enumerate(words):
            if x in word:
                ans.append(idx)
        return ans

---

Q2. 🟡 2943. Maximize Area of Square Hole in Grid 1677

題意

• 給定一個網格圖，由 $n + 2$ 條 橫線段 和 $m + 2$ 條 垂直線段 組成，一開始所有區域均為 $1 \times 1$ 的單元格，所有線段的編號從 1 開始。
• 給定兩個整數 $n$ 和 $m$ ，同時給定兩個整數陣列 $hBars$ 和 $vBars$ 。
  • $hBars$ 包含區間 $[2, n + 1]$ 內 互不相同 的橫線段編號。
  • $vBars$ 包含 $[2, m + 1]$ 內 互不相同 的垂直線段編號。
• 如果滿足以下條件之一，你可以 移除 兩個陣列中的部分線段：
  • 如果移除的是橫線段，它必須是 $hBars$ 中的值。
  • 如果移除的是垂直線段，它必須是 $vBars$ 中的值。
• 返回移除一些線段後（可能不移除任何線段），剩餘網格圖中 最大正方形空洞 的面積，正方形空洞的意思是正方形內部 不含有任何線段。

思路：

<++>

class Solution:
    def maximizeSquareHoleArea(self, n: int, m: int, hBars: List[int], vBars: List[int]) -> int:
        hBars.sort()
        vBars.sort()

        def helper(bars):
            res = 1
            i = 0
            while i < len(bars) - 1:
                tmp = 1
                while i < len(bars) - 1 and bars[i] + 1 == bars[i + 1]:
                    tmp += 1
                    i += 1
                res = max(res, tmp)
                i += 1
            return res

        maxWidth = min(helper(hBars) + 1, helper(vBars) + 1)
        return pow(maxWidth, 2)

---

Q3. 🟡 2944. Minimum Number of Coins for Fruits

題意

<++>

思路：

<++>

class Solution:
    """
        Dynamic Programming
        dp[i][j] 表示買i個水果的最小花費，第j個水果是否買
        - dp[i][1] = min(dp[i-1][1] , dp[i-1][0]) + prices[i]
        - 如果前k個有買，那這個可以不買
          k + k <= i => k <= i//2
        
    """
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)
        ans = 0
        dp = [[float("inf")] * (2) for _ in range(n + 1)]
        # dp[0][0] = dp[0][1] = 0 # 
        dp[1][1] = prices[0] # 第一個水果一定要買
        for i in range(2, n + 1):
            dp[i][1] = min(dp[i-1][1] , dp[i-1][0]) + prices[i-1]
            for k in range(1, i//2+1):
                dp[i][0] = min(dp[i][0], dp[i-k][1])
        return min(dp[n][0], dp[n][1])

---

Q4. 🔴 2945. Find Maximum Non-decreasing Array Length

題意

<++>

思路：

<++>

class Solution:
    """
        DP + Monotonic Queue

        錯誤思路：Greedy (x)
        - 1, 2, 1, 3, 3
            - 1, 2, 7 (X)
            - 1, 3 ,3, 3 (O)
        正確思路：單調隊列優化DP (O)
    """
    def findMaximumLength(self, nums: List[int]) -> int:
        n = len(nums)
        pre_sum = [0] + list(accumulate(nums))

        dp = [0] * (n + 1)
        last = [0] * (n + 1)

        q = deque([0])
        for i in range(1, n + 1):
            # 1. 去掉隊首無用數據
            # - j1 < j2 < i
            while len(q) > 1 and pre_sum[q[1]] + last[q[1]] <= pre_sum[i]:
                q.popleft()
            
            # 2. 計算轉移
            j = q[0]
            dp[i] = dp[j] + 1
            last[i] = pre_sum[i] - pre_sum[j]
            
            # 3. 去掉隊尾無用數據
            while q and pre_sum[q[-1]] + last[q[-1]] >= pre_sum[i] + last[i]:
                q.pop()
            q.append(i)
        return dp[n]

---