LeetCode Weekly Contest 376 解題紀錄

被第3題繞暈了，一開始試了一些暴力的作法，後來才想到題目的問的就是數線上距離，從中位數兩側取就可以了。第4題想到了中位數+前綴和計算花費，但是就是沒想到可以用滑動窗口，又是臨門一腳，特別難受。

All problems solved by python

---

Q1: 🟢 2965. Find Missing and Repeated Values _

tags: 計數(Counting) 陣列(Array) 雜湊表(Hash Table) 數學(Math) 矩陣(Matrix)

題意

• 給定一個大小為 $n \times n$ 的二維矩陣 $grid$，其中的值在 $[1, n^2]$ 範圍內。除了 $a$ 出現兩次，$b$ 缺失之外，每個整數都恰好出現一次。
• 返回一個長度為 2 的整數陣列 $ans$，其中 $ans[0]$ 等於 $a$，$ans[1]$ 等於 $b$。

思路：計數

• 用一個陣列 $cnt$ 紀錄每個數字出現的次數
• 掃過一次 $cnt$，找出 $cnt[i] == 0$ 的 $i$，即為 $b$，找出 $cnt[i] == 2$ 的 $i$，即為 $a$
• 時間複雜度：$O(n^2)$
• 空間複雜度：$O(n^2)$

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        cnt = [0] * (n * n + 1)
        for i in range(n):
            for j in range(n):
                cnt[grid[i][j]] += 1
        ans1, ans2 = 0, 0
        for i in range(1, n * n + 1):
            if cnt[i] == 0:
                ans2 = i
            elif cnt[i] == 2:
                ans1 = i
        return [ans1, ans2]

---

Q2: 🟡 2966. Divide Array Into Arrays With Max Difference 1396

tags: 貪心(Greedy) 排序(Sorting) 陣列(Array)

題意

• 給定一個長度為 $n$ 的整數陣列 $nums$，以及一個正整數 $k$ ，將這個陣列分成一個或多個長度為 $3$ 的子陣列，並滿足以下條件：
  1. $nums$ 中的 每個 元素都必須 恰好 存在於某個子陣列中。
  2. 子陣列中 任意 兩個元素的差必須小於或等於 $k$ 。
• 傳回一個 二維陣列 ，包含所有的子陣列。 如果不可能滿足條件，就回傳一個空陣列。 如果有多個答案，返回 任一個 即可。

思路：排序

• 由於條件1要求每個元素都要恰好存在於某個子陣列中，因此可以將答案視為將 $n$ 個數字分成 $n/3$ 個子陣列，每個子陣列長度為 $3$。
• 為了滿足條件2，我們可以讓同一個子陣列中的元素盡量接近，因此我們可以先將 $nums$ 排序後，每次取出 $3$ 個數字，檢查是否滿足條件，如果滿足條件，就加入答案中，否則回傳空陣列。
• 時間複雜度：$O(n \log n)$ ，排序的時間複雜度為 $O(n \log n)$ ，每次取出 $3$ 個數字的時間複雜度為 $O(1)$ ，因此總時間複雜度為 $O(n \log n)$ 。
• 空間複雜度：$O(n)$ ，排序的空間複雜度為 $O(n)$ ，答案的空間複雜度為 $O(n)$ ，因此總空間複雜度為 $O(n)$ 。

class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = [nums[i*3:i*3+3] for i in range(n // 3)]
        for row in ans:
            if row[2] - row[0] > k:
                return []
        return ans

---

Q3: 🟡 2967. Minimum Cost to Make Array Equalindromic _

tags: 中位數貪心 數學(Math) 貪心(Greedy) 排序(Sorting) 陣列(Array)

題意

• 給定一個長度為 $n$ 的整數陣列 $nums$ ， 可以對 $nums$ 執行 任意次 操作，每一次操作可以把 $nums[i]$ 中的一個元素變為任意正整數 $x$ ，所需花費為 $|nums[i] - x|$ 。
• 目標是把 $nums$ 的所有元素都變成相同的數字，且這個數字是一個 回文數，且所需花費最小，返回最小花費。

思路：中位數貪心

• 首先先不考慮回文數的限制，我們可以發現，如果我們把所有數字都變成中位數，那麼所需花費最小，可以由 畫數線 來證明，所需花費即為數線上兩點的距離。
  • 若 $n$ 為奇數，則中位數為 $nums[n//2]$，將所有數變成 $nums[n//2]$ 的代價最小。
  • 若 $n$ 為偶數，則不管取 $[nums[n//2-1], nums[n//2]]$ 之間的任意數字都可以使代價最小。
• 若中位數為 回文數 ，則將其作為目標數 $x$ 即為答案，所需代價為 $\sum_{i=0}^{n-1} |nums[i] - x|$。
• 若中位數不是 回文數 ，則我們可以找兩側最接近的回文數，並計算所需代價，取較小的那個。
• 若 $n$ 為奇數很好處理，因為中位數只有一個，我們只要找到左右兩側最接近的回文數即可；若 $n$ 為偶數，則中位數有兩個，但不管取哪一個的左右兩側最接近的回文數皆可，為了在 $n$ 為奇數或偶數時都能統一處理，取 $nums[n//2]$ 為中位數。
  • 若 $[nums[n//2-1], nums[n//2]]$ 存在回文數 ，則不管取 $nums[n//2-1]$ 或 $nums[n//2]$ 作為中位數，和不管兩點之間的回文數數量，都可以找到兩點之間的回文數，根據上面的推論，所需代價皆相同。
  • 若 $[nums[n//2-1], nums[n//2]]$ 不存在回文數 ，則取 $nums[n//2-1]$ 或 $nums[n//2]$ 向兩側所搜尋到的回文數必定相同。
• 因此，我們只要找到 $nums$ 中最接近中位數的回文數，即可得到答案。
• 時間複雜度：$O(n \log n)$ ，排序的時間複雜度為 $O(n \log n)$ 。
• 空間複雜度：$O(1)$，不考慮排序的空間複雜度

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()

        def check(s: str) -> bool: # 檢查 s 是不是回文數
            nn = len(s)
            for i in range(nn):
                if s[i] != s[nn - i - 1]:
                    return False
            return True

        median = nums[n // 2]
        if check(str(median)): # 中位数是回文數
            return sum([abs(x - median) for x in nums])
        l = median - 1
        while (not check(str(l))) and l > 0: # 找到左邊最近的回文數
            l -= 1
        r = median + 1
        while (not check(str(r))) and r < 10 ** 9: # 找到右邊最近的回文數
            r += 1
        cost1 = sum([abs(x - l) for x in nums])
        cost2 = sum([abs(x - r) for x in nums])
        return min(cost1, cost2) # 返回最小的 cost

---

Q4: 🔴 2968. Apply Operations to Maximize Frequency Score _

tags: 中位數貪心 數學(Math) 貪心(Greedy) 排序(Sorting) 前綴和(Prefix Sum) 滑動窗口(Sliding Window) 陣列(Array) 二分搜尋(Binary Search)

題意

• 給定一個整數陣列 $nums$ 和一個整數 $k$ ，可以對陣列執行 最多 $k$ 次操作，每次操作可以讓陣列中的一個元素 $nums[i]$ 增加或減少 $1$ 。
• 定義陣列的 頻率分數 為陣列中眾數的 出現次數， 返回操作後最大的頻率分數。

思路：中位數貪心 + 前綴和 + 滑動窗口

• 這題本質上和上一題類似，都是要找到一個數字，使得陣列中的數字變成這個數字，且代價越小越好。為了使代價盡可能的小，我們可以先將陣列 排序 ，則對目標數字 $x$ 來說，我們只需要操作 $x$ 左右兩側的數字即可。
• 排序後，此問題變成是否能存在一個子陣列，使得子陣列中的數字都變成相同的數 $x$ ，且所需 $cost \leq k$ ，且子陣列的長度最長。
• 承上題的說明，中位數 可以使子陣列變成相同的數字，且所需花費最小。
• 再來考慮如何快速計算花費，我們可以先將陣列的 前綴和 計算出來，則對於一個子陣列 $[l, r]$ 來說，我們可以用 $cost(l, i, r) = (i - l) \times nums[i] - (pre\_sum[i] - pre\_sum[l]) + (pre\_sum[r+1] - pre\_sum[i+1]) - (r - i) \times nums[i]$ 來表示將 $nums[l:r+1]$ 變成 $nums[i]$ 所需花費，其中 $pre\_sum$ 為陣列的前綴和。
• 最後可以用 滑動窗口 的方式來找到最長的子陣列，若當前窗口的 $cost > k$ ，則將窗縮小窗口，直到 $cost \leq k$ 為止，更新答案。
• 時間複雜度：$O(n \log n)$ ，排序的時間複雜度為 $O(n \log n)$ ，計算前綴和的時間複雜度為 $O(n)$ ，滑動窗口的時間複雜度為 $O(n)$ ，因此總時間複雜度為 $O(n \log n)$ 。
• 空間複雜度：$O(n)$ ，排序的空間複雜度為 $O(n)$ ，前綴和的空間複雜度為 $O(n)$ ，因此總空間複雜度為 $O(n)$ 。

class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()

        pre_sum = [0] + list(accumulate(nums))

        def cost(l, i, r): # 把 nums[l:r+1] 變成 nums[i]，所需要的 cost
            d1 = (i - l) * nums[i] - (pre_sum[i] - pre_sum[l]) # left side
            d2 = (pre_sum[r+1] - pre_sum[i+1]) - (r - i) * nums[i] # right side
            return d1 + d2
        
        # Sliding Window
        ans = 0
        left = 0
        for right in range(n):
            while cost(left, (left+right)//2, right) > k :
                left += 1
            ans = max(ans, right - left + 1) # 更新答案的最大長度
        return ans

類題

• 🟡 2602. Minimum Operations to Make All Array Elements Equal 1903
  相比本題只少了滑動窗口

---