LeetCode Biweekly Contest 119 解題紀錄

這次前三題沒怎麼動腦，11分鐘就寫完了，第四題寫完Floyd-Warshall想了很久怎麼選點，沒注意到n = 10，把所有狀態跑一遍就可以了 …

All problems solved by python

Q1: 🟢 2956. Find Common Elements Between Two Arrays 1215

tags: `陣列(Array)` `雜湊表(Hash Table)`

題意

給定 $nums1$ 和 $nums2$ 兩個陣列，分別有 $n$ 和 $m$ 個元素。

統計 $0 \leq i < n$ 且 $nums1[i]$ 在 $nums2$ 中至少出現一次的元素個數。
統計 $0 \leq i < m$ 且 $nums2[i]$ 在 $nums1$ 中至少出現一次的元素個數。

思路：計數 + 雜湊表

先列出 $nums1$ 和 $nums2$ 的元素出現次數，再分別計算 $nums1$ 和 $nums2$ 中的每個元素在另一個 Array 中有無出現即可。可以用Hash Table或Hash Set加速，若遍歷整個Array的話，時間複雜度會變成 $O(n \cdot m)$ 。

複雜度分析

時間複雜度： $O(n + m)$
空間複雜度： $O(n + m)$

class Solution:
    def findIntersectionValues(self, nums1: List[int], nums2: List[int]) -> List[int]:
        cnt1 = Counter(nums1)
        cnt2 = Counter(nums2)
        res1 = sum([1 for x in nums1 if x in cnt2])
        res2 = sum([1 for x in nums2 if x in cnt1])
        return [res1, res2]

Q2: 🟡 2957. Remove Adjacent Almost-Equal Characters 1430

tags: `分組循環` `字串(String)` `貪心(Greedy)`

題意

給定一個字串 $word$ ，每次可以選擇一個下標 $i$ ，將 $word[i]$ 修改成任一個小寫英文字母。求使得 $word$ 中沒有 almost-equal characters 的最少操作次數。

若 $abs(ord(a) - ord(b)) <= 1$ 則 a 和 b 是 almost-equal characters (近似相等字元)

思路：貪心 + 分組循環

若連續出現 $k$ 個 近似相等字元，則最少需要 $k // 2$ 次操作將其修改成不同的字母，用分組循環的方式計算連續出現的 近似相等字元 的個數即可。

class Solution:
    def removeAlmostEqualCharacters(self, word: str) -> int:
        n = len(word)
        ans = 0
        i = 0
        while i < n:
            st = i
            while i + 1 < n and abs(ord(word[i]) - ord(word[i + 1])) <= 1:
                i += 1
            i += 1
            ans += (i - st) // 2
        return ans

Q3: 🟡 2958. Length of Longest Subarray With at Most K Frequency 1535

tags: `滑動窗口(Sliding Window)` `陣列(Array)` `雜湊表(Hash Table)`

題意

給定一個整數 Array $nums$ 和一個整數 $k$ ，如果一個陣列中所有元素的出現次數都 $\leq k$ ，那麼我們稱這個陣列為 good array ，返回請你回傳 nums 中 longest good subarray 的長度。

思路：滑動窗口(Sliding Window)

入窗口時，檢查新入元素的出現次是否超過 $k$ ，若超過則持續移動左指標，否則更新答案。

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        ans = 0
        left = 0
        cnt = Counter()
        for idx, num in enumerate(nums):
            cnt[num] += 1
            while cnt[num] > k:
                cnt[nums[left]] -= 1
                left += 1
            ans = max(ans, idx - left + 1)
        return ans

類題

Q4: 🔴 2959. Number of Possible Sets of Closing Branches 2077

tags: `狀態壓縮` `二進位枚舉` `圖(Graph)` `最短路徑(Shortest Path)` `Floyd-Warshall` `枚舉(Enumeration)` `位運算(Bit Manipulation)`

題意

給定一張 Undirected Multigraph ，其中有 $n$ 個點，給定Array $roads$ ，其中 $roads[i] = [u_i, v_i, w_i]$ 表示一條從 $ui$ 到 $vi$ 長度為 $wi$ 的無向邊。
刪除一些節點和與其相鄰的邊，使得剩下的節點之間任意點的最長距離不超過 $maxDistance$ ，求有多少種刪除節點的方案。
注意，兩個分部之間可能會有多條道路。

限制：

$1 \leq n \leq 10$

思路：暴力枚舉 + 狀態壓縮 + Floyd-Warshall

$n \leq 10$ ，所以可以暴力枚舉所有的狀態，然後用 Floyd-Warshall 計算所有點對之間的最短路徑，再檢查是否有點對的距離超過 $maxDistance$ 。
狀態可以用一個整數表示，第 $i$ 個 bit 為 $1$ 表示第 $i$ 個點被選擇，否則表示沒有被選擇。
Time Complexity： $O(2^n \cdot n^3)$ , $n \leq 10$

class Solution:
    def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
        # 建圖只要一次
        g = [[inf] * n for _ in range(n)]
        for i in range(n):
            g[i][i] = 0
        for x, y, w in roads:
            g[x][y] = min(g[x][y], w)
            g[y][x] = min(g[y][x], w)

        ans = 0
        g2 = [None] * n # subgraph
        for mask in range(1 << n):
            # Copy subgraph
            for i, row in enumerate(g):
                if mask >> i & 1: # 這個點在子圖裡
                    g2[i] = row[:] # copy

            # Floyd-Warshall
            for k in range(n):
                if (mask >> k & 1) == 0: continue # k 不在子圖裡
                for i in range(n):
                    if (mask >> i & 1) == 0: continue # i 不在子圖裡
                    for j in range(n):
                        if g2[i][k] + g2[k][j] < g2[i][j]:
                            g2[i][j] = g2[i][k] + g2[k][j]
            # Check
            flag = True
            for i in range(n):
                if (mask >> i & 1) == 0: continue # i 不在子圖裡
                for j in range(n):
                    if (mask >> j & 1) == 0: continue # j 不在子圖裡
                    if g2[i][j] > maxDistance:
                        flag = False
                        break
            if flag:
                ans += 1
        return ans