LeetCode 2023/12/11-2023/12/20 每日一題

每日第1題為中文站(LCCN) ，第2題為英文站(LCUS) ，題目連結皆統一為英文站的題目連結。
Easy 、Medium 、Hard 難度的題目分別用🟢🟡🔴表示。
若為周賽題目會額外標註由 @zreotrac 零神計算的rating分數。

All problems solved by python

---

2023-12-11

🟡 1631. Path With Minimum Effort 1948

題意

• 給定一個二維陣列 $heights$，表示一個地圖，每個格子的高度為 $heights[i][j]$，從左上角 $(0, 0)$ 到右下角 $(m-1, n-1)$，每次可以上下左右四個方向移動，求從左上角到右下角的 最小體力消耗 。
• 最小體力消耗 的定義是：所選路徑上，相鄰格子之間 高度差絕對值 的 最大值 決定的。

思路：BFS + Binary Search / Disjoint Set (Kruskal) / Dijkstra

方法一：BFS + Binary Search

• 先把問題簡化成：是否存在一條路徑，使得所有格子之間的高度差絕對值的最大值不超過 $k$ ，此時可以用BFS檢查是否存在這樣的路徑。
• 再來就是如何找到最小的 $k$ ，由於 $k$ 超過答案值後，一定符合條件，反之則一定不符合，故符合單調性 ，因此可以用Binary Search找到最小的 $k$ 。
• 時間複雜度：$O(mn \log C)$，其中 $C$ 為最大高度差絕對值，本題中 $C \leq 10^6$ 。
• 空間複雜度：$O(mn)$，即BFS需要用到的空間。

方法二：Disjoint Set (Kruskal)

• 類似MST中的Kruskal演算法，將所有邊按照權重排序，從小到大加入，若加入後起點和終點在同一個集合中，則表示已經連通，此時的權重即為答案。
• 對於每個點，可以將其二維座標轉換為一維座標，方便使用Disjoint Set。
• 時間複雜度：$O(mn \log(mn))$，排序的時間複雜度為 $O(mn \log(mn))$，Disjoint Set的時間複雜度為 $O(mn \alpha(mn))$，其中 $\alpha$ 為Ackermann函數的反函數。 $\alpha(mn)$ 可以視為常數，因此時間複雜度為 $O(mn \log(mn))$
• 空間複雜度：$O(mn)$，Disjoint Set需要用到的空間。

方法三：Dijkstra

• 依照Dijkstra的思路，對於每個點，維護一個距離陣列 $dist$ ，表示從起點到該點的最小體力消耗(Single Source Shortest Path)，初始值為無限大，起點為 $dist[0][0] = 0$ 。
• 對於每個點，維護一個是否已經訪問過的陣列 $visited$ ，初始值為 $False$ 。
• 每次從 $dist$ 中選擇一個最小的值，並且標記為已訪問，然後更新與其相鄰的點的距離，直到終點被訪問過。
• 時間複雜度：$O(mn \log(mn))$，每個點最多被訪問一次，每次訪問需要 $O(\log(mn))$ 的時間。
• 空間複雜度：$O(mn)$，Dijkstra需要用到的空間。

BFS二分Disjoint SetDijkstra

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:。
        m, n = len(heights), len(heights[0])
        
        def check(k): # BFS 檢查當前 mid 是否可到達終點
            DIR = [(0, 1), (0, -1), (1, 0), (-1, 0)]
            q = deque([(0, 0)])
            visited = set([(0, 0)])
            while q:
                x, y = q.popleft()
                for dx, dy in DIR:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited:
                        if abs(heights[x][y] - heights[nx][ny]) <= k:
                            q.append((nx, ny))
                            visited.add((nx, ny))
            return (m - 1, n - 1) in visited
        
        left, right = 0, 10**6
        while left <= right: # [left, right]
            mid = (left + right) // 2
            if check(mid): # 可以到達終點，縮小右邊界
                right = mid - 1 
            else:
                left = mid + 1
        return left

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m, n = len(heights), len(heights[0])
        edges = [] # (u, v, w)
        # 對每個點，如果右邊或下面有點，就加入edges
        for i in range(m):
            for j in range(n):
                idx = i * n + j # 為了方便，把每個點編號
                if i + 1 < m:
                    edges.append((idx + n, idx, abs(heights[i + 1][j] - heights[i][j])))
                if j + 1 < n:
                    edges.append((idx + 1, idx, abs(heights[i][j + 1] - heights[i][j])))
        edges.sort(key=lambda x: x[2]) # 按照 weight 排序

        # Disjoint Set
        p = [i for i in range(m * n)]
        def find(x):
            if x != p[x]:
                p[x] = find(p[x])
            return p[x]
        def union(x, y):
            px, py = find(x), find(y)
            if px != py:
                p[px] = py
        # Kruskal
        st, ed = 0, m * n - 1 # 起點和終點的index
        for u, v, w in edges:
            union(u, v)
            if find(st) == find(ed):
                return w
        return 0 # 起點=終點，返回0

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m, n = len(heights), len(heights[0])
        dist = [[float('inf')] * n for _ in range(m)] # dist[i][j] 表示從起點到 (i, j) 的最小體力消耗
        dist[0][0] = 0 
        visited = [[False] * n for _ in range(m)] # 記錄是否已經訪問過

        DIR = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        q = [(0, 0, 0)] # (dist, x, y)
        while q:
            d, x, y = heapq.heappop(q)
            if visited[x][y]:
                continue
            visited[x][y] = True
            for dx, dy in DIR:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n:
                    nd = max(d, abs(heights[x][y] - heights[nx][ny])) # 更新體力消耗
                    if nd < dist[nx][ny]: # 更新 dist
                        dist[nx][ny] = nd
                        heapq.heappush(q, (nd, nx, ny))
        return dist[-1][-1]

參考資料

• 最小体力消耗路径
• 阿克曼函數 - 維基百科，自由的百科全書

---

🟢 1287. Element Appearing More Than 25% In Sorted Array 1179

題意

給定一個非遞減的 有序 整數陣列 $arr$，已知其中恰好有一個整數的出現次數超過陣列元素總數的 25%，返回這個整數。

思路：Counter / Binary Search

方法一：雜湊表統計(Counter)

• 統計每個元素出現的次數，根據題意，只有一個元素的出現次數超過25%，因此然後找到出現次數最多，或是出現次數超過25%的元素即可。
• 時間複雜度：$O(n)$，Counter的時間複雜度為 $O(n)$，找到出現次數最多的元素的時間複雜度為 $O(n)$。
• 空間複雜度：$O(n)$，Counter需要用到的空間。

方法二：二分搜尋(Binary Search)

• 將 $arr$ 分成4等分，由於題目已經給定 $arr$ 是有序的，出現超過25%的元素在 $arr$ 中的分布會有兩種情況：
  1. 全部在其中一個四等分中
  2. 橫跨兩個四等分
• 不管是情況1還是情況2，在四個四等分中，必有至少一個四等分的第一個元素是出現超過25%的元素。
• 因此只要檢查每一個等分的第一個元素，檢查其出現次數是否超過25%即可。由於 $arr$ 是有序的，因此可以用二分搜尋找到每個等分的第一個元素出現的左界和右界，然後計算出現次數即可。
  • bisect.bisect_right 回傳 $>x$ 的第一個下標 (相當於C++中的upper_bound)，
  • bisect.bisect_left 回傳 $\geq x$ 第一個下標 (相當於C++中的lower_bound)。
• 時間複雜度：$O(4 * \log n) = O(\log n)$，二分搜尋的時間複雜度為 $O(\log n)$，需要執行4次。
• 空間複雜度：$O(1)$，不需要額外的空間。

雜湊表統計二分搜尋

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        return Counter(arr).most_common(1)[0][0]

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        span = n // 4 + 1 # 每隔 span 個元素檢查一次
        for i in range(0, n, span):
            l = bisect_left(arr, arr[i])
            r = bisect_right(arr, arr[i])
            if r - l >= span: # 出現次數超過25%
                return arr[i]
        return -1

---

2023-12-12

🔴 2454. Next Greater Element IV 2175

題意

• 給定一個非負整數陣列 $nums$ ，找到 $nums$ 中每個元素的的 第二大 整數，如果不存在，則為 $-1$ 。
• 如果 $nums[j]$ 滿足下列條件，那麼我們稱它為 nums[i] 的 第二大 整數：
  1. $j > i$
  2. $nums[j] > nums[i]$
  3. 恰好存在 一個 $k$ 滿足 $i < k < j$ 且 $nums[k] > nums[i]$ 。
• 題目有點繞，但其實就是找到 $nums[i]$ 的 下下個 比 $nums[i]$ 大的數，下一個數和下下一個數的大小關係不用考慮。

思路：單調棧(monotonic stack) + Heap

方法一：單調棧 + Min Heap

• 在 $O(n)$ 時間內找到下一個比 $nums[i]$ 大的數，可以用單調棧來解決，對於每個 $nums[i]$ ，維護一個單調遞減的棧，棧中存放的是 $nums[i]$ 的下標，並且棧頂元素是最小的。
• 當 $nums[i]$ 比棧頂元素大時，棧頂元素就是下一個比 $nums[i]$ 大的數，此時若要題目要求是下一個比 $nums[i]$ 大的數，將其從棧中彈出，並且更新答案即可。
• 但此題目要求是下下個比 $nums[i]$ 大的數，因此需要再維護一個最小堆，來找到下下個比 $nums[i]$ 大的數。
• 時間複雜度：$O(n \log n)$，單調棧的時間複雜度為 $O(n)$，最小堆的時間複雜度為 $O(n \log n)$。
• 空間複雜度：$O(n)$，單調棧和最小堆需要用到的空間。

方法二：兩個單調棧

• 承上，在找第二個比 $nums[i]$ 大的數時，也具有單調性，因此可以用兩個單調棧來解決。
• 一個單調棧維護下一個比 $nums[i]$ 大的數，另一個單調棧維護下下個比 $nums[i]$ 大的數。
• 但需要注意，第一個單調棧元素由於是由後往前(小到大)彈出，加入到第二個單調棧中會破壞單調遞減性，因此需要對新增的部分進行反轉，使其仍然是單調遞減的。
• 時間複雜度：$O(n)$，兩個單調棧的時間複雜度為 $O(n)$。
• 空間複雜度：$O(n)$，兩個單調棧需要用到的空間。

單調棧+最小堆兩個單調棧

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        st = [] # monotonic stack, decreasing
        hp = [] # heap, increasing
        ans = [-1] * n

        for idx, num in enumerate(nums): # idx = j
            while hp and hp[0][0] < num: # num 是**第二個**比 nums[i] 大的數
                _, i = heappop(hp)
                ans[i] = num

            while st and nums[st[-1]] < num:  # num 是**第一個**比 nums[i] 大的數
                i = st.pop()
                heappush(hp, (nums[i], i))
            st.append(idx)
        return ans

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        st1 = [] # monotonic stack, decreasing
        st2 = []
        ans = [-1] * n

        for idx, num in enumerate(nums): # idx = j
            while st2 and nums[st2[-1]] < num: # num 是**第二個**比 nums[i] 大的數
                i = st2.pop()
                ans[i] = num
            size = len(st2)
            while st1 and nums[st1[-1]] < num:  # num 是**第一個**比 nums[i] 大的數
                i = st1.pop()
                st2.append(i)
            if size != len(st2): # 反轉新加入的部分
                st2[size:] = reversed(st2[size:])
            st1.append(idx)
        return ans

類題

單調棧

• 🟡 739. Daily Temperatures（单调栈模板题）
• 🟢 1475. Final Prices With a Special Discount in a Shop 1212
• 🟢 496. Next Greater Element I
• 🟡 503. Next Greater Element II
• 🟡 1019. Next Greater Node In Linked List 1571
• 🟡 901. Online Stock Span 1709
• 🟡 1124. Longest Well-Performing Interval 1908
• 🟡 456. 132 Pattern
• 🟡 2866. Beautiful Towers II 2072
• 🔴 2454. Next Greater Element IV 2175
• 🟡 2289. Steps to Make Array Non-decreasing 2482
• 🟡 2832. Maximal Range That Each Element Is Maximum in It (Premium)

矩形系列

• 🔴 84. Largest Rectangle in Histogram
• 🔴 85. Maximal Rectangle
• 🟡 1504. Count Submatrices With All Ones 1845

字典序(最小)

• 🟡 316. Remove Duplicate Letters
• 🟡 221021天池-03. 整理书架
  316 延伸題，重複個數不超過 limit
• 🟡 402. Remove K Digits
• 🟡 1673. Find the Most Competitive Subsequence 1802
• 🔴 321. Create Maximum Number

貢獻法（計算所有子陣列的……的和）

• 🟡 907. Sum of Subarray Minimums 1976
• 🟡 2104. Sum of Subarray Ranges 1504
• 🟡 1856. Maximum Subarray Min-Product 2051
• 🔴 2818. Apply Operations to Maximize Score 2397
• 🔴 2281. Sum of Total Strength of Wizards 2621

題單來自：@灵茶山艾府

參考資料

• O(n) 一次遍历+双单调栈（附题单）Python/Java/C++/Go/JS/Rust
• [Java] 一个单调栈 & 双单调栈 & 单调栈 +堆 三种解法

---

🟢 1464. Maximum Product of Two Elements in an Array 1121

題意

• 給定一個整數陣列 $nums$，返回 $(nums[i]-1)*(nums[j]-1)$ 的最大值，其中 $i \neq j$。
• $1 \leq nums[i] \leq 10^3$

思路：簡單模擬

• 由於題目限制了 $nums[i] \geq 1$，這題只要考慮最大和次大的值的乘積，因此可以用兩個變數來維護最大和次大的值就可以了。
• 若是沒有限制 $nums[i] \geq 1$，則需要維護最小和次小的負數，以及最大和次大的正數，然後比較兩者的乘積。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        mx1 = mx2 = -1
        for num in nums:
            if num > mx1:
                mx1, mx2 = num, mx1
            elif num > mx2:
                mx2 = num
        return (mx1 - 1) * (mx2 - 1)

---

2023-12-13

🟢 2697. Lexicographically Smallest Palindrome 1304

題意

• 給定一個由 小寫英文字母 組成的字串 $s$，在每次操作中，可以用其他小寫英文字母 取代 $s$ 中的一個字元。
• 請你找到操作次數最少的方案，使得 $s$ 變成一個 回文字串 。如果有多種方案，只需選取 字典序最小 的方案。返回最後的回文字串。

思路：貪心

• 要使 $s$ 變成回文字串，只需要將 $s$ 的前半部分和後半部分對稱即可，因此若對應的字元不同，對兩者取字典序較小的字元即可。

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        n = len(s)
        res = list(s)
        for i in range((n+1)//2):
            if s[i] != s[n-1-i]:
                res[i] = res[n-1-i] = min(s[i], s[n-1-i])
        return ''.join(res)

---

🟢 1582. Special Positions in a Binary Matrix 1321

題意

• 給定一個矩陣 $mat$，其中 $mat[i][j]$ 是 $0$ 或 $1$，請回傳矩陣中 特殊位置 的數量。
• 若 $mat[i][j]=1$，第 $i$ 行和第 $j$ 列中的所有其他元素均為 $0$，則 $(i, j)$ 被認為是一個 特殊位置

思路：簡單模擬

• 先處理每行每列中 $1$ 的數量，然後再檢查是否為特殊位置即可。
• 由於 $mat[i][j]$ 只有 $0$ 和 $1$，因此可以用用每行每列的和來計算 $1$ 的數量，不用判斷 $mat[i][j]$ 是否為 $1$。

class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        row, col = [0] * m, [0] * n
        for i in range(m):
            for j in range(n):
                row[i] += mat[i][j]
                col[j] += mat[i][j]
        ans = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1 and row[i] == 1 and col[j] == 1:
                    ans += 1
        return ans

2023-12-14

🔴 2132. Stamping the Grid 2364

題意

給定一個二維矩陣 $grid$ ， 若 $grid[i][j] = 0$ 表示該位置為空，若 $grid[i][j] = 1$ 表示該位置被占據，給定郵票的大小 $stampHeight \times stampWidth$，我們想用郵票把空的位置都填滿，且不能覆蓋到被占據的位置，郵票可以相互重疊，但不能旋轉，郵票必須完全在矩陣內，可以放入任意數量的郵票。若可以填滿，則返回 $true$，否則返回 $false$。

思路：貪心 + 二維前綴和 + 二維差分

由於之前的 abc331 D ，所以看到題目的時候，很快就想到用二維前綴和檢查區域是否可以放置郵票，並貪心放置所有可能的位置。但一開始標記放置了多少張郵票的時候用了最暴力的 $O(HW)$ 方式，因此總時間複雜度為 $O(mnHW)$，很明顯會 TLE 。看了題解才知道可以用二維差分來標記放置了郵票的位置，這樣時間複雜度就可以降到 $O(mn)$ 了，又學到了一招。

• 由於不限制郵票的數量，且郵票可以相互重疊，因此可以用貪心的思路，先將所有可以放置郵票的位置都放置郵票，然後檢查是否有沒有放置郵票的位置，若有，則不可行。因此問題主要分成兩個部分
  1. 如何 檢查 某個區域是否可以放置郵票；
  2. 如何 標記 某個區域放置了郵票。
• 對於第一個問題，可以用二維前綴和來檢查，對於第二個問題，可以用二維差分來標記。
• 首先對 $grid$ 做二維前綴和，表示區域中有幾個 $1$，即不能放置郵票的位置數量，對於左上角為 $(a, b)$，右下角為 $(c, d)$ 的區域，其不能放置郵票的位置數量為 $s[c][d] - s[a-1][d] - s[c][b-1] + s[a-1][b-1]$。
• 若區域中不能放置郵票的位置數量為 $0$，則可以放置郵票，在 $diff$ 中的四個位置標記放置了郵票，即 $diff[a-1][b-1] += 1, diff[c][b-1] -= 1, diff[a-1][d] -= 1, diff[c][d] += 1$。
• 最後對所有位置做二維差分前綴和，並檢查所有位置，若可放置郵票(即 $grid[i][j] = 0$)，但卻沒有放置郵票(即 $diff[i][j] = 0$)的位置，則返回 $false$，否則返回 $true$。
• 時間複雜度：$O(mn)$，二維前綴和的時間複雜度為 $O(mn)$，二維差分的時間複雜度為 $O(mn)$，二維差分前綴和的時間複雜度為 $O(mn)$。
• 空間複雜度：$O(mn)$，二維前綴和和二維差分需要用到的空間。

class Solution:
    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:
        # 1. 對grid做二維前綴和，表示區域中有幾個1，即不能放置郵票的位置數量
        m, n = len(grid), len(grid[0])
        pre_sum = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                pre_sum[i + 1][j + 1] = pre_sum[i + 1][j] + pre_sum[i][j + 1] - pre_sum[i][j] + grid[i][j]
        # print(*pre_sum, sep='\n')

        # 2. 對所有可以放置郵票的位置，做二維差分，表示這個區域放置了郵票
        diff = [[0] * (n + 2) for _ in range(m + 2)]
        for c in range(stampHeight, m + 1):
            for d in range(stampWidth, n + 1):
                a, b = c - stampHeight + 1, d - stampWidth + 1 # 左上角
                if pre_sum[c][d] - pre_sum[a - 1][d] - pre_sum[c][b - 1] + pre_sum[a - 1][b - 1] == 0: # 如果中間的區域不可放置的位置數量為0，則可以放置郵票，
                    diff[a - 1][b - 1] += 1
                    diff[c][b - 1] -= 1
                    diff[a - 1][d] -= 1
                    diff[c][d] += 1
        # print(*diff, sep='\n')

        # 3. 對二維差分做前綴和，若有可放置郵票，但卻沒有放置郵票的位置，則不可行
        for i in range(m):
            for j in range(n):
                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1] # 二維差分前綴和
                if grid[i][j] == 0 and diff[i][j] == 0: # 有可放置郵票，但卻沒有放置郵票的位置
                    return False
        return True

類題

• 🟡 1277. Count Square Submatrices with All Ones 1613
• 🟡 221. Maximal Square
• 🟡 1504. Count Submatrices With All Ones 1845
• 🟡 304. Range Sum Query 2D - Immutable

題單來自：@灵茶山艾府、@newhar

參考資料

• 【图解】从一维差分到二维差分（Python/Java/C++/Go/JS/Rust）
• 二维前缀和+二维差分（图解）

---

🟡 2482. Difference Between Ones and Zeros in Row and Column 1373

題意

給定一個 $m \times n$ 的二進位矩陣 $grid$，返回一個相同大小的差值矩陣 $diff$ ， $diff[i][j] = onesRow_i + onesCol_j - zerosRow_i - zerosCol_j$ ，其中

• $onesRow_i$ 表示第 $i$ Row $1$ 的數目；
• $onesCol_j$ 表示第 $j$ Col $1$ 的數目；
• $zerosRow_i$ 表示第 $i$ Row $0$ 的數目；
• $zerosCol_j$ 表示第 $j$ Col $0$ 的數目。

思路：簡單模擬

• 由於是二進位矩陣，因此只需要計算每行每列的 $1$ 的數量即可，$zerosRow_i=n-onesRow_i$，$zerosCol_j=m-onesCol_j$，因此 $diff[i][j] = 2 * onesRow_i + 2 * onesCol_j - m - n$。

class Solution:
    def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        rows = [0] * m
        cols = [0] * n
        for i in range(m):
            for j in range(n):
                rows[i] += grid[i][j]
                cols[j] += grid[i][j]
        diff = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                # diff[i][j] = rows[i] + cols[j] - (n - rows[i]) - (m - cols[j])
                diff[i][j] = 2 * rows[i] + 2 * cols[j] - m - n
        return diff

---

2023-12-15

🟡 2415. Reverse Odd Levels of Binary Tree 1431

題意

• 給定一個二元樹 $root$，將所有奇數層的節點的值反轉，偶數層的節點的值不變，並返回反轉後的二元樹。
• 定義樹根為第 $0$ 層，且這棵樹是 full binary tree 。

註：full/compelete/perfect binary tree的差別，說明及圖例來源自參考資料。

• full binary tree ：除了樹葉以外，每個節點都有兩個小孩。
• complete binary tree ：各層節點全滿，除了最後一層，最後一層節點全部靠左。
• perfect binary tree ：各層節點全滿。同時也是 full binary tree 和 complete binary tree 。

思路：BFS (Level Order Traversal)

• 由於要求偶數層的節點的值不變，因此可以在基於 BFS (Level Order Traversal) 的基礎上來解決，對於每一層，若是奇數層，則將節點的值反轉，否則不變。
• 由於是 perfect binary tree ，因此每個節點都有對應的節點存在，直接交換對應節點的值即可。

class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        level = 0
        q = deque([root])
        while q:
            n = len(q)
            if level % 2 == 1:
                for i in range(n // 2):
                    q[i].val, q[-i - 1].val = q[-i - 1].val, q[i].val
            for _ in range(n):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level += 1
        return root

參考資料

• Binary Tree - 演算法筆記

---

🟢 1436. Destination City 1192

題意

給定一個二維矩陣 $paths$ ，其中 $paths[i] = [cityA_i, cityB_i]$ ，表示一條從 $cityA_i$ 到 $cityB_i$ 的有向邊，返回旅途的終點，即沒有任何可以通往其他城市的路徑的城市。

思路：簡單模擬

• 統計每個點的outdegree，若outdegree為 $0$，則為答案。
• 或是直接用一個Hash Set紀錄所有可以通往其他城市的城市 $cityA_i$，最後檢查 $cityB_i$ 是否在 Hash Set 中，若不在則為答案。

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        outdegree = defaultdict(int)
        for u, v in paths:
            outdegree[u] += 1
            outdegree[v] += 0 # 為了建立所有點的索引
        
        for node in outdegree:
            if outdegree[node] == 0:
                return node
        return ""

---

2023-12-16

🔴 2276. Count Integers in Intervals 2222

本月第3次未做先看題解，雖然遇到過好幾次線段樹了，但一直沒有好好了解，只能說該來的還是朵不掉。

題意

• 給定一個 空 的區間集合，每次給你一個區間，要求你將這個區間加入到區間集合之中，並且統計出現在 至少一個 區間的整數個數。
• 實作 CountIntervals 類別：
  • CountIntervals() 使用區間的空集合初始化對象
  • void add(int left, int right) 增加區間 $[left, right]$ 到區間集合之中。
  • int count() 傳回出現在 至少一個 區間的整數個數。
• **注意：**區間 $[left, right]$ 表示滿足 $left <= x <= right$ 的所有整數 $x$ 。

思路：珂朵莉樹(Chtholly Tree) / 線段樹(Segment Tree)

方法一：珂朵莉樹(Chtholly Tree) / 老司機樹(Old Driver Tree，ODT)

暴力的美學

• 珂朵莉樹(Chtholly Tree)，又稱 老司機樹(Old Driver Tree，ODT)，起源於CF896C，因為題目背景主角是《末日時在做什麼？有沒有空？可以來拯救嗎？》的主角 珂朵莉 ，因此該資料結構被稱為珂朵莉樹。該題目要求實作一種資料結構，可以較快實現以下四種操作：
  1. 區間加：將區間 $[L,R]$ 中的所有數加上 $v$
  2. 區間賦值：將區間 $[L,R]$ 中的所有數改成 $v$
  3. 求區間第k大值：輸出區間 $[L,R]$ 中第 $k$ 大的數
  4. 求區間n次方和：輸出 $\sum_{i=L}^{R}a_i^n$ ，即區間 $[L,R]$ 內元素的 $n$ 次幂和
• 珂朵莉樹 可以實現區間推平操作，並且支持區間修改和區間查詢。因此適用於這類 有區間推平又有隨機操作 的題目。
• 珂朵莉樹 的核心思想在於隨機賦值操作很可能讓大量元素變成同一個數，因此我們可以用三元組 $(l,r,v)$ 來表示一個節點，其中 $l$ 表示節點的左端點， $r$ 表示節點的右端點， $v$ 表示 $l$ 和 $r$ 之間的所有元素都是 $v$ 。
• 在保存這些三元組時，需要使用 有序集合 維護這些區間，以左端點作為關鍵字進行升序排列，這樣方便進行一些操作的時候方便查找到我們想要修改的區間。在 C++ 中 的 std::set 即是一種有序集合，而在 Python 中，可以使用 sortedcontainers 來實現有序集合。雖然看似與樹無關，但實際上 std::set 是用 紅黑樹(Red-Black Tree) 實現的，因此 珂朵莉樹 也可以看作是一種樹。
• 在進行區間操作時，可能會把原本連續的區間斷開，因此需要一個函數來實現斷開操作，把 $(l,r,v)$ 斷成 $(l,pos-1,v)$ 和 $(pos,r,v)$ ，可以使用 Binary Search 來找到需要斷開的位置。
• 回到本題，本題要求實現以下兩種操作：
  1. 區間染色：將區間 $[L,R]$ 中的所有數從 $0$ 改成 $1$
  2. 求區間和：輸出 $\sum_{i=L}^{R}a_i$ ，即區間 $[L,R]$ 內元素的和
• 由於本題染色只會從 $0$ 改成 $1$，因此三元組中的 $v$ 只有 $1$ 一種情況，因此可以省略 $v$，只用 $(l,r)$ 來表示一個節點。

方法二：線段樹(Segment Tree)

• 待補

珂朵莉樹線段樹

from sortedcontainers import SortedList

class CountIntervals:
    def __init__(self):
        self.sl = SortedList(key=lambda x: x[1]) # 用右區間當索引key
        self.ans = 0 # 被染色的區間的長度和

    def add(self, left: int, right: int) -> None:
        i = self.sl.bisect_left((0, left)) # 找到第一個大於等於 left 的 key
        # print(left, right, i)
        # 遍歷所有被 [left,right] 覆蓋到的區間（部分覆蓋也算）
        while i < len(self.sl) and self.sl[i][0] <= right:
            l, r = self.sl[i]
            left = min(left, l) # 合併後的新區間，其左端點為所有被覆蓋的區間的左端點的最小值
            right = max(right, r) # 合併後的新區間，其右端點為所有被覆蓋的區間的右端點的最大值
            self.ans -= r - l + 1
            self.sl.pop(i)
        self.ans += right - left + 1
        self.sl.add((left, right))
        # print(self.sl)

    def count(self) -> int:
        return self.ans

class CountIntervals:
    __slots__ = 'left', 'right', 'l', 'r', 'cnt'

    def __init__(self, l=1, r=10 ** 9):
        self.left = self.right = None # 左右子樹
        self.l, self.r, self.cnt = l, r, 0 # 區間左右端點，被染色的區間的長度和

    def add(self, L: int, R: int) -> None:
        if self.cnt == self.r - self.l + 1: return # self 已被完全染色，無需操作
        if L <= self.l and self.r <= R: # self 已被 [L,R] 完全覆蓋，直接染色
            self.cnt = self.r - self.l + 1
            return
        mid = (self.l + self.r) // 2 # self 的中點
        if self.left is None: self.left = CountIntervals(self.l, mid) # 動態開點
        if self.right is None: self.right = CountIntervals(mid + 1, self.r) # 動態開點
        if L <= mid: self.left.add(L, R) # 將 [L,R] 覆蓋到 self 的左子樹
        if mid < R: self.right.add(L, R) # 將 [L,R] 覆蓋到 self 的右子樹
        self.cnt = self.left.cnt + self.right.cnt # 更新 self 的被染色的區間的長度和

    def count(self) -> int:
        return self.cnt

類題

珂朵莉樹(Chtholly Tree)

• [CF896C] Willem, Chtholly and Seniorious
• [CF915E] Physical Education Lessons
  和本題相同，都是區間染色問題

線段樹(Segment Tree)

• Segment Tree - LeetCode

參考資料

• 两种做法：珂朵莉树 / 动态开点线段树（Python/Java/C++/Go）
• 算法学习笔记(15): 珂朵莉树 - 知乎
• 线段树 - OI Wiki
• 珂朵莉树/颜色段均摊 - OI Wiki

---

🟢 242. Valid Anagram

題意

給定兩個字串 $s$ 和 $t$，判斷 $t$ 是否為 $s$ 的 Anagram(字母異位詞) ，也就是說， $s$ 和 $t$ 中的字元出現的次數都相同，或是說， $s$ 可以重新排列成 $t$。

思路：排序 / 雜湊表

方法一：排序

• 將 $s$ 和 $t$ 排序後，判斷兩者是否相同即可。
• 時間複雜度：$O(nlogn)$，排序的時間複雜度為 $O(nlogn)$，比較兩個字串是否相同的時間複雜度為 $O(n)$。
• 空間複雜度：$O(n)$，排序需要用到的空間。

方法二：雜湊表

• 統計每個元素出現的次數，然後比較兩個字串中每個元素出現的次數是否相同。
• 時間複雜度：$O(n)$，統計每個元素出現的次數的時間複雜度為 $O(n)$，比較兩個字串中每個元素出現的次數是否相同的時間複雜度為 $O(n)$。
• 空間複雜度：$O(n)$，統計每個元素出現的次數需要用到的空間。

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # return sorted(s) == sorted(t)
        return Counter(s) == Counter(t)

---

2023-12-17

🟢 746. Min Cost Climbing Stairs 1358

題意

• 給定一個Array $cost$，其中 $cost[i]$ 表示從第 $i$ 個台階向上爬的花費，每次可以選擇向上爬一個或兩個台階，返回達到樓梯頂部的最低花費。
• 可以選擇從下標 0 或下標為 1 的階梯開始。

思路：動態規劃

• 定義 $dp[i]$ 為爬到第 $i$ 個台階的最低花費，則轉移方程式為 $dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])$。
• 需要注意的是，可以選擇從下標 0 或下標為 1 的階梯開始，因此 $dp[0] = dp[1] = 0$。

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0]*(n+1)
        dp[0], dp[1] = 0, 0
        for i in range(2, n+1):
            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
        return dp[-1]

---

🟡 2353. Design a Food Rating System 1782

題意

實作 FoodRatings 類別：

• FoodRatings(String[] foods, String[] cuisines, int[] ratings) 初始化。 食物由 $foods$、$cuisines$ 和 $ratings$ 描述，長度均為 $n$ 。
  • $foods[i]$ 是第 $i$ 種食物的名字。
  • $cuisines[i]$ 是第 $i$ 種食物的烹調方式。
  • $ratings[i]$ 是第 $i$ 種食物的初步評分。
• void changeRating(String food, int newRating) 修改名字為 $food$ 的食物的評分為 $newRating$ 。
• String highestRated(String cuisine) 傳回指定烹調方式 cuisine 下評分最高的食物的名字。 如果存在並列，則傳回 字典序較小 的食物名字。

思路：雜湊表 + 有序集合/懶刪除堆

方法一：雜湊表 + 有序集合

• 使用雜湊表 $fd$ 來紀錄食物的評分和所屬烹調方式，雜湊表 $cs$ 來紀錄烹調方式下所屬的食物和評分，並使用有序集合來維護。
• 對於 changeRating 操作，只需要在 $fd$ 中修改食物的評分，並在 $cs$ 中刪除原本的食物，再將修改後的食物加入 $cs$ 中即可。
• 對於 highestRated 操作，只需要在 $cs$ 中找到指定烹調方式下評分最高的食物即可，由於是有序集合，因此可以直接取第一個元素。

方法二：雜湊表 + 懶刪除堆

• 但我們 只在意評分最高的食物 ，因此也可以使用 懶刪除堆 來實現，在更改分數的時候不需要刪除原本的食物，直接添加新的食物即可。
• 當我們需要取得評分最高的食物時，只需要檢查堆頂的食物是否被修改過，若被修改過，則捨棄，直到堆頂的食物沒有被修改過，則為評分最高的食物。

雜湊表 + 有序集合雜湊表 + 懶刪除堆

from sortedcontainers import SortedSet
class FoodRatings:

    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.fd = dict()
        ss = lambda: SortedSet([], key=lambda x: (-x[1], x[0])) # 有序集合，key為評分降序，字典序升序
        self.cs = defaultdict(ss)
        for f, c, r in zip(foods, cuisines, ratings):
            self.fd[f] = (c, r)
            self.cs[c].add((f, r))

    def changeRating(self, food: str, newRating: int) -> None:
        c, r = self.fd[food]
        self.cs[c].remove((food, r))
        self.cs[c].add((food, newRating))
        self.fd[food] = (c, newRating)

    def highestRated(self, cuisine: str) -> str:
        return self.cs[cuisine][0][0]

class FoodRatings:
    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.fd = dict()
        self.cs = defaultdict(list) # Heap
        for f, c, r in zip(foods, cuisines, ratings):
            self.fd[f] = (c, r)
            self.cs[c].append((-r, f))
        for c in self.cs:
            heapq.heapify(self.cs[c])

    def changeRating(self, food: str, newRating: int) -> None:
        c, r = self.fd[food]
        heappush(self.cs[c], (-newRating, food)) # 直接添加，不刪除原本的
        self.fd[food] = (c, newRating)

    def highestRated(self, cuisine: str) -> str:
        hp = self.cs[cuisine]
        while -hp[0][0] != self.fd[hp[0][1]][1]: # 不一樣代表被修改過，直接捨棄
            heappop(hp)
        return hp[0][1]

參考資料

• 哈希表套平衡树 / 懒删除堆（Python/Java/C++/Go）

---

2023-12-18

🟡 162. Find Peak Element

題意

• 給定一個整數陣列 $nums$ ，找到一個 峰值元素 並返回其索引。 陣列可能包含多個峰值，在這種情況下，返回 任何一個峰值 所在位置即可。
• 峰值元素 是嚴格大於左右相鄰值的元素。
• 可以假設 $nums[-1] = nums[n] = -∞$ 。
• 需要以 $O(log n)$ 的時間複雜度來解決此問題。
• 對於所有有效的 $i$ 都有 $nums[i] \neq nums[i + 1]$

思路：簡單模擬 / 找最大值 / 二分搜尋

方法一：簡單模擬

• 根據題目的假設： $nums[-1] = nums[n] = -∞$ ，在陣列前後添加 $-∞$ 後，從頭開始遍歷，找到第一個滿足 $nums[i-1] < nums[i] > nums[i+1]$ 的 $i$ 即可。
• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$

方法二：找最大值

• 由於題目假設 $nums[-1] = nums[n] = -∞$ ，且 $nums[i] \neq nums[i + 1]$ ，因此最大值的所在位置一定是峰值元素，找出最大值的所在位置即可。
• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$，不計算輸入的空間。

方法三：二分搜尋

• 題目要求實作 $O(log⁡n)$ 時間複雜度的演算法，這基本上就是在暗示我們使用「二分搜尋」了。
• 由於題目確保 $nums[-1] = nums[n] = -∞$ 且 $nums[i] \neq nums[i + 1]$ ，在以 $mid$ 為分界點的陣列上，根據 $nums[mid]$ 與 $nums[mid±1]$ 的大小關係，可以確定其中一段滿足「必然有解」，另外一段不滿足「必然有解」（可能有解，可能無解）。
  • 若 $nums[x] > nums[x-1]$，則 $nums[x]$ 的右邊一定存在峰值。
  • 若 $nums[x] > nums[x+1]$，則 $nums[x]$ 的左邊一定存在峰值。
• 以上結論可由證明以下兩點得出，具體證明過程此處省略，請參考參考資料。
  1. 對於任意陣列而言，一定存在峰值（一定有解）
  2. 二分不會錯過峰值
• 時間複雜度：$O(log⁡n)$
• 空間複雜度：$O(1)$，不計算輸入的空間。

簡單模擬找最大值二分搜尋

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        n = len(nums)
        nums = [float('-inf')] + nums + [float('-inf')]
        for i in range(1, n+1):
            if nums[i-1] < nums[i] > nums[i+1]:
                return i-1
        return -1

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        ans = 0
        for i, x in enumerate(nums):
            if x > nums[ans]:
                ans = i
        return ans

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = 0, n-1
        while(left <= right): # [left, right]
            mid = (left + right) // 2
            if mid == (n-1) or nums[mid] > nums[mid+1]: # 若 mid 已經是最後一個元素，則不用比較
                right = mid - 1
            else:
                left = mid + 1
        return left

參考資料

• 【宫水三叶の相信科学系列】关于能够「二分」的两点证明

---

🟢 1913. Maximum Product Difference Between Two Pairs 1145

題意

• 給定一個整數陣列 $nums$，選出四個 不同的 下標 $w$、$x$、$y$ 和 $z$，使數對$(nums[w], nums[x])$ 和 $(nums[y], nums[z])$ 之間的 product difference 有 最大值。
• 兩個數對 $(a, b)$ 和 $(c, d)$ 之間的 product difference 定義為 $(a \times b) - (c \times d)$ 。
• 返回 product difference 的 最大值 。

思路：貪心

• 要使 product difference 有最大值，很明顯 $(a \times b)$ 的值要盡可能的大，$(c \times d)$ 的值要盡可能的小。
• 因此只要取出 $nums$ 中的最大和最小的各兩個數字，計算後即可。
• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$

class Solution:
    def maxProductDifference(self, nums: List[int]) -> int:
        mx1, mx2 = float('-inf'), float('-inf')
        mn1, mn2 = float('inf'), float('inf')
        for num in nums:
            if num > mx1:
                mx1, mx2 = num, mx1
            elif num > mx2:
                mx2 = num
            if num < mn1:
                mn1, mn2 = num, mn1
            elif num < mn2:
                mn2 = num
        return mx1 * mx2 - mn1 * mn2

---

2023-12-19

🟡 1901. Find a Peak Element II

題意

• 給定一個 $m \times n$ 的矩陣 $mat$，找到一個 峰值元素 並返回其位置。 陣列可能包含多個峰值，在這種情況下，返回 任何一個峰值 所在位置即可。
• 二維陣列中的 峰值元素 是嚴格大於其相鄰(上、下、左、右)元素的元素。
• $mat$ 內所有元素皆為正整數，即 $1 \leq mat[i][j]$ 。
• 可以假設整個矩陣週邊環繞著一圈值為 $-1$ 的格子。
• 任兩個相鄰元素均不相等
• 需要以 $O(m log(n))$ 或 $O(n log(m))$ 的時間複雜度來解決此問題。

思路：找最大值 / 二分搜尋

• 昨天的每日一題的進階版，只是把一維陣列改成二維陣列。

方法一：找最大值

• 基本上說明和昨天的每日一題一樣，就不再贅述。
• 時間複雜度：$O(mn)$
• 空間複雜度：$O(1)$，不計算輸入的空間。

方法二：二分搜尋

• 在以 $mid$ 為分界點的陣列上，根據 $max(mat[mid])$ 和他下面的相鄰數字的大小關係，可以確定其中一段滿足「必然有解」，另外一段不滿足「必然有解」（可能有解，可能無解）。
  • 若 $max(mat[mid])$ 比他下面的相鄰數字小，則存在一個峰頂，其行號 $>mid$，縮小二分範圍，更新二分區間左端點 $left$。
  • 若 $max(mat[mid])$ 比他下面的相鄰數字大，則存在一個峰頂，其行號 $\leq mid$ ，縮小二分範圍，更新二分區間右端點 $right$。
• 對於本題，如果每次二分，都是 $max(mat[mid])$ 比它下面的相鄰數字小，那麼最後會判斷出 峰頂行號 $> (m-2)$，此時可以直接確定最後一行必然包含峰頂。這表示 $m-1$ 不需要在初始二分範圍內，因此二分範圍為 $[0, m-2]$。
• 時間複雜度：$O(m log(n))$
• 空間複雜度：$O(1)$，不計算輸入的空間。

找最大值二分搜尋

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        m, n = len(mat), len(mat[0])
        ans = [0, 0]
        for i in range(m):
            for j in range(n):
                if mat[i][j] > mat[ans[0]][ans[1]]:
                    ans = [i, j]
        return ans

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        m, n = len(mat), len(mat[0])
        left, right = 0, m - 2
        while left <= right:
            mid = (left + right) // 2
            mx, idx = max((v, i) for i, v in enumerate(mat[mid]))
            if mx > mat[mid + 1][idx]: # 峰頂在這row或在上半部分，row_idx <= i
                right = mid - 1 
            else: # 峰頂在下半部分，row_idx > i
                left = mid + 1
        i = left
        _, j = max((v, j) for j, v in enumerate(mat[i]))
        return [i, j]

類題：二分題單

二分答案

• 🟡 275. H-Index II
• 🟡 1283. Find the Smallest Divisor Given a Threshold 1542
• 🟡 2187. Minimum Time to Complete Trips 1641
• 🟡 2226. Maximum Candies Allocated to K Children 1646
• 🟡 1870. Minimum Speed to Arrive on Time 1676
• 🟡 1011. Capacity To Ship Packages Within D Days 1725
• 🟡 875. Koko Eating Bananas 1766
• 🟡 1898. Maximum Number of Removable Characters 1913
• 🟡 1482. Minimum Number of Days to Make m Bouquets 1946
• 🟡 1642. Furthest Building You Can Reach 1962
• 🟡 2861. Maximum Number of Alloys 1981
• 🔴 2258. Escape the Spreading Fire 2347

最小化最大值

• 🟡 2064. Minimized Maximum of Products Distributed to Any Store 1886
• 🟡 1760. Minimum Limit of Balls in a Bag 1940
• 🟡 2439. Minimize Maximum of Array 1965
• 🟡 2560. House Robber IV 2081
• 🔴 778. Swim in Rising Water 2097
• 🟡 2616. Minimize the Maximum Difference of Pairs 2155
• 🟡 2513. Minimize the Maximum of Two Arrays 2302

最大化最小值

• 🟡 1552. Magnetic Force Between Two Balls 1920
• 🟡 2861. Maximum Number of Alloys 1987
• 🟡 2517. Maximum Tastiness of Candy Basket 2021
• 🟡 2812. Find the Safest Path in a Grid 2154
• 🔴 2528. Maximize the Minimum Powered City 2236

題單來自：@灵茶山艾府

參考資料

• 【图解】利用行最大值判断峰顶位置，附二分题单（Python/Java/C++/Go/JS/Rust）

---

🟢 661. Image Smoother

題意

• 給定一個大小為 $3 \times 3$ 的 image smoother ，用於對影像的每個單元格平滑處理，平滑處理後單元格的值為該單元格的平均灰階值。
• 每個單元格的 平均灰階值 定義為：此單元格本身及其周圍的 8 個單元格的平均值，結果 需向下取整 。 （即，需要計算藍色平滑器中 9 個單元格的平均值）。
• 如果一個單元格周圍存在單元格缺失的情況，則計算平均灰階值時不考慮缺少的單元格（即，需要計算紅色平滑器中 4 個單元格的平均值）。

思路：模擬 / 二維前綴和

方法一：模擬

• 用一個 $8$ 方向的方向陣列來表示周圍的單元格，然後遍歷每個單元格，計算周圍單元格的數量和灰階值，最後計算平均灰階值即可。
• 時間複雜度：$O(C*m*n)$，$m$ 和 $n$ 分別為影像的行數和列數，$C$ 為image smoother 的大小，本題為 $3 \times 3 = 9$。
• 空間複雜度：$O(m*n)$，需要用到一個 $m \times n$ 的二維陣列。

方法二：二維前綴和

• 在方法一中，對於每個像素點，都需要檢查其 $8$ 個方向，若擴大 kernel 的大小，則需要檢查更多的單元格，這個計算過程可以使用二維前綴和來優化。
• 定義 $s[i][j]$ 為 $img$ 中 $(0, 0)$ 至 $(i-1, j-1)$ 區域的灰階和，則 $(a, b)$ 至 $(c, d)$ 區域的灰階和為 $s[c+1][d+1] - s[c+1][b] - s[a][d+1] + s[a][b]$ 。
• 在計算 $[x,y]$ 單元格的平均灰階值時，需計算 $(x-1, y-1)$ 至 $(x+1, y+1)$ 區域的灰階和，然而為了避免越界，需要對 $x$ 和 $y$ 進行限制，即 $a = max(0, x-1)$、$b = max(0, y-1)$、$c = min(m-1, x+1)$、$d = min(n-1, y+1)$ 。
• 時間複雜度：$O(m*n)$，$m$ 和 $n$ 分別為影像的行數和列數。
• 空間複雜度：$O(m*n)$，需要用到一個 $(m+1) \times (n+1)$ 的二維陣列 $s$ ，以及一個 $m \times n$ 的二維陣列 $ans$ 。

模擬二維前綴和

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        DIRS = [(-1, -1), (-1, 0), (-1, 1), (0, -1),
                (0, 1), (1, -1), (1, 0), (1, 1)]
        m, n = len(img), len(img[0])
        ans = [[0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                cnt, s = 1, img[i][j]
                for di, dj in DIRS:
                    ni, nj = i+di, j+dj
                    if 0 <= ni < m and 0 <= nj < n:
                        cnt += 1
                        s += img[ni][nj]
                ans[i][j] = s // cnt
        return ans

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        m, n = len(img), len(img[0])
        s = [[0] * (n + 2) for _ in range(m + 2)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + img[i - 1][j - 1]
        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                a, b = max(0, i - 1), max(0, j - 1) # 避免越界
                c, d = min(m - 1, i + 1), min(n - 1, j + 1) # 避免越界
                cnt = (c - a + 1) * (d - b + 1) # 有效單元格的數量
                tot = s[c + 1][d + 1] - s[a][d + 1] - s[c + 1][b] + s[a][b] # 二維前綴和
                ans[i][j] = tot // cnt
        return ans

---

2023-12-20

🟢 2828. Check if a String Is an Acronym of Words 1152

第2次週賽的題目，沒想到還沒補到那時候的題目，就已經出現在每日一題了。

題意

給定一個字串陣列 $words$ 和一個字串 $s$，判斷 $s$ 是否為 $words$ 的 縮寫 。

思路：簡單模擬

• 若 $s$ 的長度不等於 $words$ 的長度，則肯定不是縮寫。否則就檢查 $s$ 的每個字元是否為對應的 $words$ 中的字串的首字元即可。
• 時間複雜度：$O(n)$，$n$ 為 $words$ 的長度。

class Solution:
    def isAcronym(self, words: List[str], s: str) -> bool:
        # return len(words) == len(s) and all(word[0] == s[idx] for idx, word in enumerate(words))
        if len(words) != len(s):
            return False
        for idx, word in enumerate(words):
            if word[0] != s[idx]:
                return False
        return True

---

🟢 2706. Buy Two Chocolates 1208

還好我聖誕節不用買巧克力送人

題意

• 給定一個整數陣列 $prices$ ，表示若干種巧克力的價格，同時給定一個整數 $money$，表示擁有的金錢數量
• 返回購買兩種巧克力後，最多能剩下多少錢。如果無法購買任兩種巧克力，則返回 $money$。

思路：簡單模擬

• 很顯然購買價格最低的兩種巧克力即可滿足條件，遍歷一遍 $prices$，找到最小的兩個價格，然後計算剩下的錢即可。
• 時間複雜度：$O(n)$，$n$ 為 $prices$ 的長度。
• 空間複雜度：$O(1)$。

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        min1 = min2 = float('inf')
        for p in prices:
            if p < min1:
                min2 = min1
                min1 = p
            elif p < min2:
                min2 = p
        return money - (min1 + min2) if money >= min1 + min2 else money

---

寫在最後

瞧瞧你發現了什麼？你看，是一串魔法咒語！

(masterpiece, best quality), 1girl, solo, cowboy_shot Musician, Musical attire, Recording studio, Composing music, Performing live, playing guitar, Collaborating with other musicians, gotou1, gotou1, gotou hitori, solo, skirt, pink jacket, track jacket, bangs, hair between eyes, long sleeves,<lora:gotou_hitori_v1:0.800000>
Negative prompt: (worst quality, low quality:1.4), negative_hand-neg, EasynegativeV2, bad-artist-anime, verybadimagenegative_v1.3, bad_prompt_version2
Steps: 30, Sampler: DPM++ 2M Karras, CFG scale: 8.0, Seed: 416831509, Size: 960x540, Model: CamelliaMix_V3: 1757182f367d", TI hashes: "negative_hand-neg, EasyNegativeV2, bad-artist-anime, verybadimagenegative_v1.3, bad_prompt_version2", Version: v1.6.0.109-2-gd1c0272