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)

LeetCode 解題筆記：628. Maximum Product of Three Numbers

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


LeetCode 題目連結：628. Maximum Product of Three Numbers

解題想法

簡單題。題目給一個陣列 $nums$，且 $-1000 \leq nums[i] \leq 1000$，從 $nums$ 之中選取 3 個數字相乘，回傳乘積最大值。先將 $nums$ 由小到大排序，答案可能是選最大的 3 個正整數相乘，或是選 1 個最大的正整數及2 個最小的負整數相乘，回傳兩種選擇的最大值。但是排序的時間複雜度為 $O(n \log n)$，如果想要將時間複雜度降到 $O(n)$ 就不能排序，改用 for 迴圈掃過 $nums$，用 if 更新最大的 3 個數字及最小的 2 個數字，最後再計算乘積最大值。

Python 程式碼

排序。Runtime: 19 ms, beats 64.08%. Memory: 20.50 MB, beats 17.11%.

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        return max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[-1])

for 迴圈。Runtime: 4 ms, beats 95.92%. Memory: 20.28 MB, beats 78.13%.

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        a = b = c = float('-inf')  # 最大的 3 個數字
        d = e = float('inf')  # 最小的 2 個數字
        for num in nums:
            if num >= a:  # 新的最大值
                a, b, c = num, a, b
            elif num >= b:  # 新的第二大
                b, c = num, b
            elif num > c:  # 新的第三大
                c = num
            if num <= e:  # 新的最小值
                e, d = num, e
            elif num < d:  # 新的第二小
                d = num
        return max(a*b*c, a*d*e)

LeetCode 解題筆記：3536. Maximum Product of Two Digits

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


LeetCode 題目連結：3536. Maximum Product of Two Digits

解題想法

簡單題。題目給一個數字 $n$，取出 $n$ 之中任意兩個數字相乘，回傳乘積最大值。基本上就是要找出最大的兩個數字相乘，我是用變數 $a$ 儲存最大的數字，變數 $b$ 儲存第二大的數字，用一個 while 迴圈檢查 $n$ 的每個數字，找出 $a, b$ 的乘，最後回傳 $a \times b$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.40 MB, beats 22.61%.

class Solution:
    def maxProduct(self, n: int) -> int:
        a, b = 0, 0  # 最大、第二大的數字
        while n > 0:
            d = n % 10
            n //= 10
            if d > a:  # 新的最大值
                a, b = d, a
            elif d > b:  # 新的第二大
                b = d
        return a*b