LeetCode 解題筆記：3310. Remove Methods From Project

作者：王一哲
日期：2026年8月5日


LeetCode 題目連結：3310. Remove Methods From Project

解題想法

中等難度題。對我而言，這題最大的困難在於看懂題目的意思。題目給一個計畫的方法之間先後順序的關係，方法數量為 $n$，編號為 $0$ 到 $n-1$，其中編號 $k$ 是可疑的方法，$k$ 之後的方法都被視為可疑的方法；但如果有這群可疑方法之外沒有問題的方法指向這個群組，則整群可疑的方法都不能被移除；最後要回傳剩下的方法。可以將這些方法視為有向圖的節點，先用 BFS 或 DFS 從節點 $k$ 出發，將 $k$ 及相連的節點都標記為可疑。再用一個 for 迴圈掃過所有節點，如果節點 $u$ 是沒有問題的節點，而且 $u$ 指向任何一個可疑的節點，則所有節點都不能被移除。如果需要移除可疑的節點，只回傳沒有問題的節點；反之，回傳所有節點。

Python 程式碼

BFS. Runtime: 227 ms, beats 90.15%. Memory: 99.66 MB, beats 89.39%.

class Solution:
    def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
        # 用接鄰矩陣儲存下一個相關的方法
        adj = [[] for _ in range(n)]
        for u, v in invocations:
            adj[u].append(v)
        
        # 用 BFS 標記可疑的方法
        suspicious = [False] * n
        que = deque([k])
        while que:
            u = que.popleft()
            suspicious[u] = True
            for v in adj[u]:
                if not suspicious[v]:
                    que.append(v)
        
        # 檢查是否有外部可用的方法呼叫任何可疑的方法，如果有，不能移除任何可疑的方法
        removed = True
        for u in range(n):
            if not suspicious[u]:
                for v in adj[u]:
                    if suspicious[v]:
                        removed = False
                        break
        
        # 回傳答案，如果需要移除可疑的方法，只回傳可用的方法
        if removed:
            return [i for i in range(n) if not suspicious[i]]
        else:  # 反之，不能移除任何方法，回傳全部的方法
            return list(range(n))

LeetCode 解題筆記：3731. Find Missing Elements

作者：王一哲
日期：2026年8月4日


LeetCode 題目連結：3731. Find Missing Elements

解題想法

簡單題。題目給一個陣列 $nums$，其中的數字皆不相同，先找出 $nums$ 之中的最小值與最大值，再找出最小值、最大值之間不在 $nums$ 之中的整數，將缺少的整數排序後再回傳，如果沒有缺少的整數則回傳空陣列。我們可以用 Python 的 max、min 或是 C++ 的 max_element、min_element 找出最大值 $high$ 與最小值 $low$。為了標記區間 $[low, high]$ 所有的數字是否在 $nums$ 之中，可以用一個長度為 $high - low + 1$ 陣列 $found$，將 $nums$ 之中所有數字 $num$ 標示為 $found[num - low] = True$。也可以將 $nums$ 轉成 Python 的 set 或是 C++ 的 unordered_set，直接用 in 或是 count 檢查數字是否在 $nums$ 之中。兩者寫法的速度都很快。

Python 程式碼

用串列標記狀態。Runtime: 0 ms, beats 100.00%. Memory: 19.45 MB, beats 18.85%.

class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        low, high = min(nums), max(nums)  # 最小值、最大值
        found = [False] * (high - low + 1)  # 是否有這個值
        for num in nums:  # 更新狀態
            found[num - low] = True
        
        ans = []  # 缺少的值
        for i in range(low + 1, high):
            if not found[i - low]:
                ans.append(i)
        return ans

用串列標記狀態，合併産生答案的程式碼。Runtime: 0 ms, beats 100.00%. Memory: 19.26 MB, beats 55.74%.

class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        low, high = min(nums), max(nums)  # 最小值、最大值
        found = [False] * (high - low + 1)  # 是否有這個值
        for num in nums:  # 更新狀態
            found[num - low] = True
        
        return [i for i in range(low + 1, high) if not found[i - low]]

LeetCode 解題筆記：1406. Stone Game III

作者：王一哲
日期：2026年8月3日


LeetCode 題目連結：1406. Stone Game III

解題想法

困難題。題目給一個長度為 $n$ 的陣列 $stoneValue$ 代表每個石頭的分數，玩家 Alice、Bob 每回合行動時，可以選擇取走目前編號最小的1到3個石頭並獲得這幾個石頭的分數，固定由 Alice 先行動，最後依照總分回傳答案，如果 Alice 總分較高回傳 Alice，如果 Bob 總分較高回傳 Bob，如果平手回傳 Tie。

這題考動態規畫，定義長度為 $n+1$ 的陣列 $dp$，$dp[i]$ 代表剩下 $i$ 個石頭時的最大分差，除了 $dp[n] = 0$，其它項初始化為負無窮大。更新時由 $i = n-1$ 往回更新到 $i = 0$，由於可以選擇拿1到3個石頭，再用一層 for 迴圈跑 $j = 1$ 到 $j = 3$，如果 $i+j \leq n$ 更新目前取石頭的總分 $val += stoneValue[i+j-1]$，$dp[i] = max(dp[i], val - dp[i+j])$。最後依照 $dp[0]$ 的值回傳答案，如果 $dp[0] > 0$ 回傳 Alice，如果 $dp[0] < 0$ 回傳 Bob，如果 $dp[0] = 0$ 回傳 Tie。

Python 程式碼

Runtime: 617 ms, beats 74.25%. Memory: 23.91 MB, beats 71.59%.

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        dp = [float('-inf')] * (n+1)  # dp[i] 代表取第 i 個時剩下的石頭最大分差
        dp[n] = 0  # 沒有剩下的石頭，之後的最大分差為 0
        # 由 stoneValue 後往前取值
        for i in range(n-1, -1, -1):
            val = 0  # 拿走的石頭得分
            for j in range(1, 4):  # 試著拿1、2、3個石頭
                if i + j <= n:  # 避免出界
                    val += stoneValue[i+j-1]  # 加上第 i+j-1 個石頭的分數
                    dp[i] = max(dp[i], val - dp[i+j])  # 更新 dp[i]，可能是 val 減掉對手於 dp[i+j] 的最大分差
        
        if dp[0] > 0: return "Alice"
        elif dp[0] < 0 : return "Bob"
        else: return "Tie"

LeetCode 解題筆記：877. Stone Game

作者：王一哲
日期：2026年8月2日


LeetCode 題目連結：877. Stone Game

解題想法

中等難度題。這題看起來與昨天的 486. Predict the Winner 幾乎一樣，題目給一個陣列 $piless$，兩個玩家 Alice、Bob 每次行動時可以從 $piles$ 兩端選取並移除一堆石頭，Alice 先行動，如果 Alice 拿到比較多的石頭回傳 True。這題一 樣可以用動態規畫解題，建立一個 $n \times n$ 的二維陣列 $dp[i][j]$ 代表可選的值剩下 $piles[i]$ ~ $piles[j]$ 時目前行動玩家與另一人的最大分差。更新狀態時有 2 種選擇：

1. 行動1，選 $piles[i]$，新的區間為 $piles[i+1]$ ~ $piles[j]$，最大分差為 $piles[i] - dp[i+1][j]$
2. 行動2，選 $piles[j]$，新的區間為 $piles[i] ~ piles[j-1]$，最大分差為 $piles[j] - dp[i][j-1]$

玩家採用最佳策略，從行動1、2之中選分數高的，因此 $$ dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]) $$ 當 $i = j$ 時，只能選擇一個數字，$dp[i][j] = piles[i]$。更新 $dp$ 時，要從長度 $2$ 開始，直到長度等於 $n$ 為止，因為長度較長的狀態，是基於長度較短的狀態更新數值。更新完畢之後，如果 $dp[0][n-1] \geq 0$，Alice 獲勝，回傳 True。

但是這題多加了兩個條件：$piles$ 的長度為偶數，$piles$ 所有的數量加起來為奇數，答案一定是 True。因為 Alice 可以選擇取走所有奇數索引值或是偶數索引值的石頭堆，選擇總數多的石頭堆就能獲勝。

Python 程式碼

dp. Runtime: 127 ms, beats 41.69%. Memory: 25.47 MB, beats 34.68%.

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)  # 長度
        # dp[i][j] 範圍為 piles[i] ~ piles[j] 對應的最大分差
        dp = [[0]*n for _ in range(n)]
        # 初始化，只剩下一堆能選
        for i in range(n):
            dp[i][i] = piles[i]
        # 更新 dp，外層更新長度 2 ~ n，內層更新起點 i = 0 ~ n - len
        for length in range(2, n+1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        # 如果 dp[0][n-1] > 0，Alice 獲勝，回傳 True
        return dp[0][n-1] > 0

Runtime: 0 ms, beats 100.00%. Memory: 19.33 MB, beats 55.87%.

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return True

LeetCode 解題筆記：486. Predict the Winner

作者：王一哲
日期：2026年8月1日


LeetCode 題目連結：486. Predict the Winner

解題想法

中等難度題。題目給一個陣列 $nums$，兩個玩家 A、B 每次行動時可以從 $nums$ 兩端選取並移除一個數字，獲得這個數字的分數，玩家 A 先行動，如果玩家 A 總分大於等於玩家 B，回傳 True。這題很適合用動態規畫解題，建立一個 $n \times n$ 的二維陣列 $dp[i][j]$ 代表可選數字剩下 $nums[i]$ ~ $nums[j]$ 時目前行動玩家與另一人的最大分差。更新狀態時有 2 種選擇：

1. 行動1，選 $nums[i]$，新的區間為 $nums[i+1]$ ~ $nums[j]$，最大分差為 $nums[i] - dp[i+1][j]$
2. 行動2，選 $nums[j]$，新的區間為 $nums[i] ~ nums[j-1]$，最大分差為 $nums[j] - dp[i][j-1]$

玩家採用最佳策略，從行動1、2之中選分數高的，因此 $$ dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]) $$ 當 $i = j$ 時，只能選擇一個數字，$dp[i][j] = nums[i]$。更新 $dp$ 時，要從長度 $2$ 開始，直到長度等於 $n$ 為止，因為長度較長的狀態，是基於長度較短的狀態更新數值。更新完畢之後，如果 $dp[0][n-1] \geq 0$，玩家 A 獲勝，回傳 True。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.11 MB, beats 94.32%.

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        # 初始化 dp
        dp = [[0]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = nums[i]
        # 由長度 2 開始填表格，直到長度 n 為止
        for length in range(2, n+1):
            for i in range(n - length + 1):  # 起點
                j = i + length - 1  # 終點
                dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
        # 回傳答案
        return dp[0][n-1] >= 0

LeetCode 解題筆記：3016. Minimum Number of Pushes to Type Word II

作者：王一哲
日期：2026年7月31日


LeetCode 題目連結：3016. Minimum Number of Pushes to Type Word II

解題想法

中等難度題，3014. Minimum Number of Pushes to Type Word I 的加強版，但是這題 $word$ 之中可以有相同的字母，需要修改一下程式碼。如果要求最低的次數，原則上是先處理 $word$ 之中數量多的字母，數量最多的前 8 個字母按 1 下，第二多的 8 個字母按 2 下，其餘依此類推。我在計算相異字母的數量時使用了，Python collections 函式庫的 Counter，這是專門用來計數的容器，速度很快；於 C++ 則是用 unordered_map，速度比較慢，改用表格計數快很多。

Python 程式碼

字典計數。Runtime: 91 ms, beats 89.97%. Memory: 19.91 MB, beats 77.26%.

class Solution:
    def minimumPushes(self, word: str) -> int:
        cnt = Counter(word)  # 計數器
        vals = sorted(cnt.values(), reverse=True)  # 各相異字母對應的數量
        n = len(vals)  # 相異字母數量
        idx = 0  # 從 vals 讀取資料的索引值
        ans = 0  # 答案
        cof = 1  # 要按幾下才能輸入一個字母
        while idx < n:
            m = 0  # 按 cof 下才能輸入的字母數量
            while idx < n and m < 8:  # 最多 8 個字母
                ans += cof * vals[idx]  # 答案加上 cof * 數量
                idx += 1  # 索引值加 1
                m += 1  # m 加 1
            cof += 1  # cof 加 1
        return ans

表格計數。Runtime: 175 ms, beats 39.47%. Memory: 19.86 MB, beats 93.65%.

class Solution:
    def minimumPushes(self, word: str) -> int:
        cnt = [0] * 26  # 計數器
        for c in word:
            cnt[ord(c) - ord('a')] += 1
        vals = sorted([val for val in cnt if val > 0], reverse=True)  # 各相異字母對應的數量
        n = len(vals)  # 相異字母數量
        idx = 0  # 從 vals 讀取資料的索引值
        ans = 0  # 答案
        cof = 1  # 要按幾下才能輸入一個字母
        while idx < n:
            m = 0  # 按 cof 下才能輸入的字母數量
            while idx < n and m < 8:  # 最多 8 個字母
                ans += cof * vals[idx]  # 答案加上 cof * 數量
                idx += 1  # 索引值加 1
                m += 1  # m 加 1
            cof += 1  # cof 加 1
        return ans

LeetCode 解題筆記：3014. Minimum Number of Pushes to Type Word I

作者：王一哲
日期：2026年7月30日


LeetCode 題目連結：3014. Minimum Number of Pushes to Type Word I

解題想法

簡單題。題目給一個字串 $word$，仿照用電話按鈕輸入字母的方式，但可以重新分配數字按鈕對應的字母，要計算輸入入 $word$ 至少要按幾下。共有 8 個按鈕可以對應到字母，如果 $word$ 的長度 $n \leq 8$，可以將 $n$ 個字母分配給不同的按鈕，各按 1 下即可；如果 $n > 8$，先處理 8 個字母，$n$ 更新為 $n-8$，下一步最多處理 8 個字母，各按 2 下即可輸入；重複以上的過程直到沒有字母需要輸入為止。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.18 MB, beats 83.33%.

class Solution:
    def minimumPushes(self, word: str) -> int:
        n = len(word)  # 字串長度
        ans, cof = 0, 1  # 答案，要按幾下才能輸入一個字母
        while n > 0:
            if n > 8:  # 剩下超過 8 個字母
                ans += 8 * cof  # 答案加上 8 * cof
                cof += 1  # cof 加 1
                n -= 8  # 字母數量減 8
            else:  # 剩下不到 8 個字母
                ans += n * cof  # 答案加上 n * cof
                n = 0  # 歸零
        return ans

LeetCode 解題筆記：6. Zigzag Conversion

作者：王一哲
日期：2026年7月29日


LeetCode 題目連結：6. Zigzag Conversion

解題想法

中等難度題。題目給一個字串 $s$、列數 $numRows$，要找出共有 $numRows$ 列的之字形排列字串。我先用一個 $numRows$ 列的陣列儲存每一列的字串內容，最後再把陣列內容接成一個很長的字串後回傳，主要的工作是在計算目前這個字元應該填在陣列中的哪一列。

Python 程式碼

Runtime: 7 ms, beats 84.25%. Memory: 19.24 MB, beats 79.60%.

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # 特例，只有一列，直接輸出 s
        if numRows == 1: return s
        # 一般狀況
        n = len(s)  # 長度
        grid = [""] * numRows  # 儲存答案用的串列
        r, d = 0, 0  # 目前所在的列，方向
        for ch in s:  # 依序讀取字元
            grid[r] += ch  # 加入字元 ch
            if d == 0:  # 向下移動
                r += 1
                if r == numRows - 1: d = 1  # 走到最下方，改成向上走
            else:  # 向上移動
                r -= 1
                if r == 0: d = 0  # 走到最上方，改成向下走
        # 從 grid 讀取字串，組合成字串 t 再回傳
        return "".join(grid)

LeetCode 解題筆記：3517. Smallest Palindromic Rearrangement I

作者：王一哲
日期：2026年7月28日


LeetCode 題目連結：3517. Smallest Palindromic Rearrangement I

解題想法

中等難度題，題目給一個迴文字串 $s$，要將 $s$ 重新排列成字典序最小的迴文字串。我一開始想到的寫法，是先計算各個字母的數量，如果字串 $s$ 長度 $n$ 為奇數，則所有的字母之中只有一個字母的數量是奇數。接下來依照字典序及數量産生需要使用的字母，開一個長度為 $n$ 的串列 $arr$ 儲存答案，由串列兩端向中央依序填入字母。如果 $n$ 是奇數，則 $arr$ 中央再填入唯一的奇數數量字母。最後將 $arr$ 組成字串後回傳。不過這樣寫實在太慢。

後來想到題目給的字串 $s$ 本身就是迴文字串，只要取 $s$ 的左半邊子字串 $left$ 再排序，答案的右半邊 $right$ 就是 $left$ 反序。如果 $s$ 的長度 $n$ 是奇數，$left$ 及 $right$ 之中再加上 $s[n/2]$ 即可。這個寫法的速度快很多。

Python 程式碼

Runtime: 375 ms, beats 21.66%. Memory: 22.32 MB, beats 5.07%.

class Solution:
    def smallestPalindrome(self, s: str) -> str:
        n = len(s)
        cnt = Counter(s)
        chars = []
        odd = ""  # 奇數數量字母
        # 依照字母順序取出數量為偶數的字母
        for ch, val in sorted(cnt.items()):
            if val % 2 == 1:
                chars += [ch] * (val - 1)
                odd = ch
            else:
                chars += [ch] * val
        # 由兩側向中央填入字母
        arr = [""] * n
        for i in range(n//2):
            arr[i] = arr[n-i-1] = chars[i*2]
        # 奇數長度，中間放唯一一個奇數數量的字母
        if n%2 == 1:  
            arr[n//2] = odd
        # 組成字串再回傳
        return "".join(arr)

Runtime: 247 ms, beats 59.91%. Memory: 20.66 MB, beats 91.71%.

class Solution:
    def smallestPalindrome(self, s: str) -> str:
        n = len(s)
        left = "".join(sorted(s[:n//2]))  # 取左半邊字母並排序
        if n%2 == 1:  # 奇數長度
            return left + s[n//2] + left[::-1]  # 右半邊字母為左半邊字母反序，加上中間的字母
        else:
            return left + left[::-1]  # 右半邊字母為左半邊字母反序

LeetCode 解題筆記：1464. Maximum Product of Two Elements in an Array

作者：王一哲
日期：2026年7月17日


LeetCode 題目連結：1464. Maximum Product of Two Elements in an Array

解題想法

簡單題。題目給一個陣列 $nums$，取出其中 2 個數字 $nums[i], nums[j]$，回傳 $(nums[i] - 1) \times (nums[j] - 1)$ 的最大值。由於這題的數值範圍是 $1 \leq nums[i] \leq 1000$，不需要考慮兩個負數相乘的狀況，只要用一個 for 迴圈掃過 $nums$，取出 2 個最大的數字 $a, b$，回傳 $(a-1) \times (b-1)$ 即可。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.20 MB, beats 68.04%.

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