LeetCode Weekly Contest 377 解題紀錄

難得的大爆發，雖然排名會和中文站(LCCN) 合併，但只看英文站(LCUS) 的排名的話，也算是進前百了。Q3因為一個小失誤吃了 WA ， Q4一直影響不大的地方嘗試優化，結果一直 TLE 。如果能冷靜點，少吃點罰時，就真的是前百了。

All problems solved by python

Q1: 🟢 2974. Minimum Number Game 1185

tags: `模擬(Simulation)` `堆(Heap)` `排序(Sorting)`

題意

給定一個長度為偶數的陣列 nums ，每次從 $nums$ 中取出兩個最小的元素，並反序添加到 $arr$ 中，直到 $nums$ 為空。返回 $arr$ 。

思路：Heap 模擬 / 排序後交換

方法一：Heap 模擬

建立一個Min Heap，按照題意模擬即可。
時間複雜度： $O(n \log n)$ ，heapify 的時間複雜度為 $O(n)$ ，heappop 的時間複雜度為 $O(\log n)$ ，總共執行 $n$ 次。
空間複雜度： $O(n)$

方法二：排序後交換

先由小到大排序，再倆倆一對，交換相鄰的元素。
時間複雜度： $O(n \log n)$ ，排序的時間複雜度為 $O(n \log n)$ ，交換的時間複雜度為 $O(1)$ ，總共執行 $n/2$ 次。
空間複雜度： $O(1)$ ，原地修改，不需要額外空間。

class Solution:
    def numberGame(self, nums: List[int]) -> List[int]:
        ans = []
        hp = [x for x in nums]
        heapify(hp)
        while len(hp) > 1:
            x = heappop(hp)
            y = heappop(hp)
            ans.append(y)
            ans.append(x)
        return ans

class Solution:
    def numberGame(self, nums: List[int]) -> List[int]:
        n = len(nums)
        nums.sort()
        for i in range(1, n, 2):
            nums[i-1], nums[i] = nums[i], nums[i-1]
        return nums

Q2: 🟡 2975. Maximum Square Area by Removing Fences From a Field 1873

tags: `暴力(Brute Force)` `枚舉(Enumeration)` `集合(Set)`

賽時的寫法有點繞，用了差分+前綴和，但其實和直接暴力枚舉是一樣的，這裡改成比較直觀的寫法。

題意

給定一個 $(m-1) \times (n-1)$ 的土地田地，其兩個對角座標分別是 $(1, 1)$ 和 $(m, n)$ ，土地內部有一些水平柵欄和垂直柵欄，分別由陣列 $hFences$ 和 $vFences$ 表示。水平柵欄的座標為 $(hFences[i], 1)$ 到 $(hFences[i], n)$ ，垂直柵欄的座標為 $(1, vFences[i])$ 到 $(m, vFences[i])$ 。
現在要移除一些柵欄，使得剩下的柵欄能形成一個最大面積的正方形田地，並返回這個正方形田地的面積。如果無法形成正方形田地則返回 $-1$ ，由於答案可能很大，所以請傳回結果對 $10^9 + 7$ 取餘後的值。
注意：土地外圍兩個水平柵欄（座標 $(1, 1)$ 到 $(1, n)$ 和座標 $(m, 1)$ 到 $(m, n)$ ）以及兩個垂直柵欄（座標 $(1, 1)$ 到 $(m , 1)$ 和座標 $(1, n)$ 到 $(m, n)$ ）作為邊界，不能被移除。

限制

$3 \leq m, n \leq 10^9$
$1 \leq hFences.length, vFences.length \leq 600$

思路：暴力枚舉 + 集合

這題和 Biweekly Contest 118 的 2943. Maximize Area of Square Hole in Grid 很像，甚至範例的圖都是一樣的。差別在 2943 是移除柵欄後，所構成的正方形內部沒有柵欄即可，這題需要用柵欄將正方形圍起來。
同樣是對水平和垂直分開討論，若水平方向可以有長度為 $k$ 的邊長，垂直方向也可以有長度為 $k$ 的邊長，則可以構成一個邊長為 $k$ 的正方形。
因此，我們可以先對水平和垂直方向的柵欄做排序，暴力枚舉出所有可能的邊長，最後對水平和垂直方向的結果做交集，若交集不為空，則表示可以構成一個正方形，取其中的最大邊長即可。若交集為空，則表示無法構成正方形，返回 $-1$ 。
時間複雜度： $O(h^2 + v^2)$ ，其中 $h$ 和 $v$ 分別為水平和垂直方向的柵欄數量，主要花在暴力枚舉邊長上。
空間複雜度： $O(h^2 + v^2)$ ，建立水平和垂直方向的柵欄集合。

class Solution:
    def maximizeSquareArea(self, m: int, n: int, hFences: List[int], vFences: List[int]) -> int:
        def helper(fences: List[int], mx: int) -> Set[int]:
            fences.sort()
            fences = [1] + fences + [mx] # 加上邊界
            res = set()
            for i in range(1, len(fences)): # 枚舉所有可能的邊長
                for j in range(i):
                    res.add(fences[i] - fences[j])
            return res
        h = helper(hFences, m)
        v = helper(vFences, n)
        intersection = h & v # 取交集
        return pow(max(intersection), 2, 10**9+7) if intersection else -1

類題

🟡 2943. Maximize Area of Square Hole in Grid 1677

Q3: 🟡 2976. Minimum Cost to Convert String I 1882

tags: `圖論(Graph)` `最短路徑(Shortest Path)` `Floyd-Warshall` `動態規劃(Dynamic Programming)`

題意

給定兩個長度為 $n$ ，全由小寫英文字母組成的字串 $source$ 和 $target$ ，以及兩個下標為 $0$ 開始的字元陣列 $original$ 和 $changed$ ，以及一個整數陣列 $cost$ ，其中 $cost[i]$ 代表將字元 $original[i]$ 更改為字元 $changed[i]$ 的花費。
對字串 $source$ 做一系列操作，每次操作可以選擇字串中的一個字元，並將其更改為另一個字元，並且花費為 $cost[i]$ 。操作結束後，若 $source$ 與 $target$ 相同，則返回操作的總花費，否則返回 $-1$ 。
返回將字串 $source$ 轉換為字串 $target$ 所需的最小成本。如果不可能完成轉換，則傳回 $-1$ 。
注意，可能存在下標 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。

思路：Floyd-Warshall 最短路徑

由範例中可以得出，對於將字元 $a$ 轉換為 $c$ ，可以由中間的字元 $b$ 來轉換，即 $a \rightarrow b \rightarrow c$ 。
因此可以建立一個有向圖，將每個字元 $a$ 看成一個節點，若 $a \rightarrow b$ 的花費為 $w$ ，則在節點 $a$ 和節點 $b$ 之間連一條權重為 $w$ 的邊。求出所有節點之間的最短路徑，即可得到答案。
由於題目只存在小寫英文數字，因此建圖時直接建 26 個節點即可，並且將所有邊的權重初始化為 $+\infty$ ，表示不可連通。
由於題目可能存在重複的邊，因此在由 $original$ 和 $changed$ 建圖時，若兩個字元相同，則將邊的權重更新為最小值。
計算答案時，對於字串 $source$ 中的每個字元 $a$ ，若 $a \rightarrow b$ 的權重為 $+\infty$ ，則表示無法將 $a$ 轉換為 $b$ ，因此返回 $-1$ 。否則將所有權重相加即可。
時間複雜度： $O(m+n+\Sigma^3)$ ，其中 $m$ 和 $n$ 分別為 $source$ 和 $cost$ 的長度， $\Sigma$ 為字元集合的大小，本題中為 $26$ 。
空間複雜度： $O(\Sigma^2)$ ，建立的圖的大小為 $\Sigma^2$ 。

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        # 建圖
        g = [[float("inf")] * 26 for _ in range(26)]
        for i in range(26):
            g[i][i] = 0
        for u, v, w in zip(original, changed, cost):
            uu, vv = ord(u)-ord('a'), ord(v)-ord('a')
            g[uu][vv] = min(g[uu][vv], w) # 這裡要注意，因為可能有重複的邊，所以要取最小值

        # Floyd-Warshall
        for k in range(26):
            for i in range(26):
                if g[i][k] == float("inf"): continue # 不可能由 g[i][k] 轉移到其他點
                for j in range(26):
                    g[i][j] = min(g[i][j], g[i][k]+g[k][j])
        
        ans = 0
        for u, v in zip(source, target):
            uu, vv = ord(u)-ord('a'), ord(v)-ord('a')
            if g[uu][vv] == float("inf"): # 不連通，不可能修改成 target
                return -1
            ans += g[uu][vv]
        return ans

類題

Floyd-Warshall

🔴 2642. Design Graph With Shortest Path Calculator 1811
🟡 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance 1811
🟡 2101. Detonate the Maximum Bombs 1880
🔴 2959. Number of Possible Sets of Closing Branches 2077

題單來自：@灵茶山艾府

Q4: 🔴 2977. Minimum Cost to Convert String II 2696

tags: `圖論(Graph)` `最短路徑(Shortest Path)` `Floyd-Warshall` `動態規劃(Dynamic Programming)` `字典樹(Trie)`

賽時寫法跟看完題解後的寫法雖然思路相同，但速度差了10幾倍，希望不會被 rejudge …

題意

同上題，但每次可以更改的字元數量從 $1$ 個變成多個，同樣求最小花費。

思路：Floyd-Warshall + DP

由於每次可以更改多個字元，因此在計算最小花費時要考慮多種情況，換句話說就是要考慮多個轉移來源，可以用 DP 來解決。
令 $dp[i]$ $d p [i]$ 表示修改 $source[:i]$ $so u rce [: i]$ 為 $target[:i]$ $t a r g e t [: i]$ 的最小代價
- 則 $dp[i]$ 可以由 $dp[j]$ 轉移而來，其中 $j < i$ 且 $source[j:i]$ 可以在若干次操作後修改成 $target[j:i]$ 。
- 若 $source[i-1] == target[i-1]$ ，則可以選擇不修改，因此 $dp[i] = min(dp[i], dp[i-1]]$ 。
在建圖和最短路徑的部分和上題一樣，但因為每次可以更改多個字元，因此可以分不同長度的情況來處理，將不同長度的節點記錄到 $len\_to\_nodes$ 。在執行 Floyd-Warshall 時，只需要處理長度相同的節點即可
在枚舉轉移來源時，可以直接枚舉轉移起始點 $j$ ，或是枚舉轉移部份的長度 $size$ 。但枚舉 $j$ 需要注意最大長度，以及判斷 $len\_to\_nodes$ 中是否有當前長度的節點；直接從 $len\_to\_nodes$ 中枚舉 $size$ 則不需要考慮這些問題，且速度更快。
時間複雜度： $O(n^3)$
空間複雜度： $O(n^2)$

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        # 這裡的建圖方法其實不是很好，對於不存在的路徑，建成 float("inf") ，後續 Floyd-Warshall 很容易會 TLE
        g = defaultdict(lambda: defaultdict(lambda: float("inf")))
        len_to_nodes = defaultdict(set) # 不同長度的字串在不同的連通分量(連通塊)中
        for u, v, w in zip(original, changed, cost):
            g[u][v] = min(g[u][v], w)
            len_to_nodes[len(u)].add(u)
            len_to_nodes[len(v)].add(v)
            g[u][u] = 0
            g[v][v] = 0
        # Floyd-Warshall
        for nodes in len_to_nodes.values(): # 不同長度的字串在不同的連通分量(連通塊)中，所以可以分開處理
            for k in nodes:
                for i in nodes:
                    if g[i][k] == float("inf"): # 不可能由 g[i][k] 轉移到其他點，巨大優化
                        continue
                    for j in nodes:
                        g[i][j] = min(g[i][j], g[i][k]+g[k][j])
        max_len = max(len_to_nodes.keys())
        # dp[i] 表示 修改 source[:i] 為 target[:i] 的最小代價
        n = len(source)
        dp = [float("inf")] * (n+1)
        dp[0] = 0
        for i in range(1, n+1):
            if source[i-1] == target[i-1]: # 可以選擇不修改
                dp[i] = dp[i-1]
            # 1. 枚舉轉移起始點 j
            # for j in range(max(0, i-max_len), i): 
            #     size = i - j
            #     if size not in len_to_nodes: # 不加會 TLE ，測資中可能有很多不存在於[0, max_len] 之間的長度
            #         continue
            #     nodes = len_to_nodes[size]
            # 2. 枚舉轉移部份的長度 size ，比枚舉 j 快很多
            for size, nodes in len_to_nodes.items(): 
                if i < size:
                    continue
                j = i-size
                # 取出 source[j:i] 與 target[j:i] ，並判斷是否存在於 g 中
                u = source[j:i]
                v = target[j:i]
                if v in nodes and u in nodes:
                    dp[i] = min(dp[i], dp[j]+g[u][v])
        return dp[n] if dp[n] != float("inf") else -1