LeetCode 解題筆記：1510. Stone Game IV

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


LeetCode 題目連結：1510. Stone Game IV

解題想法

困難題。題目給一個正整數 $n, ~ 1 \leq n \leq 10^5$，代表這堆石頭的數量，兩位玩家 Alice、Bob 輪流取走任意平方數的石頭，如果輪到自己時已經沒有石頭則輸掉比賽，固定由 Alice 先行動，回傳 Alice 的勝負狀態。這題用動態規畫解題，定義長度為 $n+1$ 的一維陣列 $dp$，$dp[i]$ 代表石頭數量為 $i$ 時 Alice 的勝負狀態，$dp$ 預設值皆為 False。用一個 for 迴圈更新 $i = 1$ 到 $i = n$，裡面再用一個 while 迴圈，更新 $j = 1$ 到 $j^2 \leq i$，如果任何一個 $dp[i - j*j] = false$，代表 $dp[i] = true$，就可以中止內層的 while 迴圈。最後回傳 $dp[n]$。

Python 程式碼

Runtime: 596 ms, beats 56.67%. Memory: 19.92 MB, beats 85.15%.

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        # dp[i] 代表數量為 i 時 Alice 的勝負狀態，0 顆必敗，dp[0] = False
        dp = [False] * (n+1)
        # 跑 i = 1 ~ n，檢查所有小於等於 i 的平方數 j，如果 dp[i - j*j] = False，則 dp[i] = True
        for i in range(1, n+1):
            j = 1
            while j*j <= i:
                if not dp[i - j*j]:
                    dp[i] = True
                    break
                j += 1
        return dp[n]

C++ 程式碼

Runtime: 31 ms, beats 81.44%. Memory: 8.85 MB, beats 90.65%.

class Solution {
public:
    bool winnerSquareGame(int n) {
        // dp[i] 代表數量為 i 時 Alice 的勝負狀態，0 顆必敗，dp[0] = False
        vector<bool> dp (n+1, false);
        // 跑 i = 1 ~ n，檢查所有小於等於 i 的平方數 j，如果 dp[i - j*j] = False，則 dp[i] = True
        for(int i = 1; i <= n; i++) {
            int j = 1;
            while(j*j <= i) {
                if (!dp[i - j*j]) {
                    dp[i] = true;
                    break;
                }
                j++;
            }
        }
        return dp[n];
    }
};

ZeroJudge 解題筆記：s573. 多項式 - 判斷正負

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


ZeroJudge 題目連結：s573. 多項式 - 判斷正負

解題想法

這題與 s562. 多項式 - 湊出 a_n 幾乎一樣。題目定義 $$ (1 - a)(1 - b)(1 - c)(1 - d) \dots = 1 - a - b + ab - c + ac + bc - abc - d + \dots $$ 測資第一行為 $t$，代表接下來有 $t$ 行數字 $n$，要回傳第 $n$ 項的正負號。實際上這題考的是二進位，先計算 $n$ 的二進位制之中有幾個 $1$，如果。$1$ 的數量為偶數輸出 $+$，數量為奇數輸出 $-$。

Python 程式碼

解題時間約為 0.2 s，使用記憶體約為 8.4 MB。

def solve():
    import sys

    t = int(sys.stdin.readline())
    for _ in range(t):
        n = int(sys.stdin.readline())
        b = n.bit_count()
        if b % 2 == 0:
            sys.stdout.write("+\n")
        else:
            sys.stdout.write("-\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：1140. Stone Game II

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


LeetCode 題目連結：1140. Stone Game II

解題想法

中等難度題，877. Stone Game 的加強版。題目給一個陣列 $piles$ 代表各個石堆的數量，兩位玩家 Alice 及 Bob 由 Alice 先行動，每回合可以從開頭拿走 $1 \leq X \leq 2M$ 堆的石頭，且下一回的 $M$ 更新為 $max(X, M)$，第一回合時 $X = 1$。題目要回傳 Alice 可以拿到的石頭數量最大值。

這題要用記憶化的動態規畫解題，在 Python 可以用裝飾器 (decorator) @cache 或是另外建一個字典儲存已經算過的值；但是 C++ 沒有裝飾器，可以用 map 儲存已經算過的值，但是 map 的速度較慢，再加上這題的 $piles$ 長度最多只有 $100$，用一個二維陣列儲存已經算過的值速度會快很多。解題步驟主要有 3 個：

1. 計算後綴和 $ssum$，$ssum[i] = piles[i] + \dots + piles[n-1]$
2. 定義函式 dfs，代入 (i, M)，計算目前的玩家由 $piles[i]$ 開始，最多可以拿 $2M$ 堆的最大數量。
3. 呼叫 dfs，代入 (0, 1)，回傳答案。

Python 程式碼

用 @cache 記憶化。Runtime: 67 ms, beats 94.78%. Memory: 26.07 MB, beats 52.86%.

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)  # 數量
        
        # 1. 建立後綴和，ssum[i] 代表 piles[i] ~ piles[n-1] 的數量加總
        ssum = [0] * n
        ssum[-1] = piles[-1]
        for i in range(n-2, -1, -1):
            ssum[i] = ssum[i+1] + piles[i]
        
        # 2. 記憶化 dfs
        @cache
        def dfs(i, M):  # 從 piles[i] 開始，最多能拿 2*M 堆
            # 遞迴出口，拿走剩下的堆
            if i + 2*M >= n:
                return ssum[i]
            # 試著拿 X 堆
            imax = 0
            for X in range(1, 2*M + 1):
                # 目前能拿的數量上限 = 現在剩下的數量 - 下一回對手能拿的數量上限
                val = ssum[i] - dfs(i+X, max(M, X))
                imax = max(imax, val)
            return imax
        
        # 3. 呼叫 dfs，由 (0, 1) 開始
        return dfs(0, 1)

用字典記憶化。Runtime: 87 ms, beats 75.73%. Memory: 23.01 MB, beats 67.30%.

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)  # 數量
        
        # 1. 建立後綴和，ssum[i] 代表 piles[i] ~ piles[n-1] 的數量加總
        ssum = [0] * n
        ssum[-1] = piles[-1]
        for i in range(n-2, -1, -1):
            ssum[i] = ssum[i+1] + piles[i]
        
        # 2. 記憶化 dfs
        memo = dict()
        def dfs(i, M):  # 從 piles[i] 開始，最多能拿 2*M 堆
            # 如果 memo 之中有已經算過的值，直接回傳
            if (i, M) in memo:
                return memo[i, M]
            # 遞迴出口，拿走剩下的堆
            if i + 2*M >= n:
                return ssum[i]
            # 試著拿 X 堆
            imax = 0
            for X in range(1, 2*M + 1):
                # 目前能拿的數量上限 = 現在剩下的數量 - 下一回對手能拿的數量上限
                val = ssum[i] - dfs(i+X, max(M, X))
                imax = max(imax, val)
            memo[i, M] = imax  # 填入 (i, M) 對應的計算結果
            return imax
        
        # 3. 呼叫 dfs，由 (0, 1) 開始
        return dfs(0, 1)

ZeroJudge 解題筆記：s562. 多項式 - 湊出 a_n

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


ZeroJudge 題目連結：s562. 多項式 - 湊出 a_n

解題想法

題目給一個函數定義 $$ \begin{align*} &~ (1 + qx)(1 + qx^2)(1 + qx^4)(1 + qx^8)(1 + qx^{16}) + \dots \\ &= a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots \end{align*} $$ 測資第一行為 $t$，代表接下來有 $t$ 行數字 $n$，要回傳 $a_n$ 對應的 $x$ 次方。實際上這題考的是二進位，$a_n$ 項的 $x$ 次方為 $n$ 的二進位制之中有幾個 $1$，例如 $a_6$ 為 $2 = 11_2$。

Python 程式碼

這題的記憶體限制很嚴格，只有 64 MB，而且測資數量極大。我一開始是用 for 迴圈及 input() 讀取資料，但是這樣會超時。後來改用 sys.stdin.read().split() 一次讀取所有測資，再用 sys.stdou.write() 輸出所有的答案，但是這樣寫會超出記憶體上限。最後是用 for 迴圈及 sys.stdin.readline() 讀取測資，計算完答案之後立刻用 sys.stdou.write() 輸出，才將時間壓在 0.5 s，記憶體壓在 8.5 MB。
超時。

t = int(input())
for _ in range(t):
    n = int(input())
    print(n.bit_count())

超出記憶體上限。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 1
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        result.append(f"{n.bit_count()}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

解題時間約為 0.5 s，使用記憶體約為 8.5 MB。

def solve():
    import sys

    t = int(sys.stdin.readline())
    for _ in range(t):
        n = int(sys.stdin.readline())
        sys.stdout.write(f"{n.bit_count()}\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3302. Find the Lexicographically Smallest Valid Sequence

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


LeetCode 題目連結：3302. Find the Lexicographically Smallest Valid Sequence

解題想法

中等難度題。題目給兩個字串 $word1$ 及 $word2$，如果最多可以改變 $word1$ 之中的一個字母，如何在 $word1$ 之中找出等於 $word2$ 的子字串，回傳最小字典序子字串於 $word1$ 之中的索引值。這題用貪心法解題比較方便。首先要找出 $word2[j]$ 及之後的字元於 $word1$ 可以被找到且在最右側的位置，將索引值存入陣列 right_match。接下來用貪心法，由 $word1$ 開頭往右找答案 $ans$，如果 $word1[i] = word2[j]$，$i$ 加入 $ans$；如果 $word1[i] \neq word2[j]$ 而且還沒有換過字母，如果已經找到 $word2[m-1]$ 或是 $word2[j+1]$ 及之後的字母可以在 $word1[i]$ 之後被找到，$i$ 加入 $ans$。最後檢查 $ans$ 的長度是否等於 $m$，如果相等回傳 $ans$，反之回傳空陣列。

Python 程式碼

Runtime: 425 ms, beats 84.78%. Memory: 48.21 MB, beats 47.83%.

class Solution:
    def validSequence(self, word1: str, word2: str) -> List[int]:
        n, m = len(word1), len(word2)  # 長度
        # 預處理，找出 word2[j] 及之後的字元於 word1 可以被找到且在最右側的位置
        right_match = [-1] * m
        j = m - 1
        for i in range(n-1, -1, -1):
            if j < 0: break  # 已經找完 word2，中止迴圈
            if word1[i] == word2[j]:
                right_match[j] = i
                j -= 1
        print(right_match)
        # 貪心法，由 word1 開頭往右找答案
        ans = []
        j = 0
        changed = False
        for i in range(n):
            # 已經找完 word2，中止迴圈
            if j == m: break
            # 相同的字母，直接加入 ans
            if word1[i] == word2[j]:
                ans.append(i)
                j += 1
            elif not changed:  # 不同的字母，還沒有換過字母
                # 如果已經找到 word2 最後一個字母或是 word2[j+1] 及之後的字母在 word1[i] 之後能被找到
                if j == m-1 or right_match[j+1] > i:
                    changed = True
                    ans.append(i)
                    j += 1
        # 如果 ans 長度等於 m，回傳 ans，反之回傳 []
        return ans if len(ans) == m else []

LeetCode 解題筆記：396. Rotate Function

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


LeetCode 題目連結：396. Rotate Function

解題想法

中等難度題。題目給一個長度為 $n$ 的陣列 $nums$，並定義 $arr_k$ 為 $nums$ 向右平移 $k$ 格，求以下的方程式最大值。 $$ F(k) = 0 \times arr_k [0] + 1 \times arr_k [1] + 2 \times arr_k [2] + \dots + (n-1) \times arr_k [n-1] $$ 這題考動態規畫，假設 $nums$ 長度為 $4$ 先列出前幾項 $F(k)$ 找規律 $$ \begin{align*} F(0) &= 0 \times nums[0] + 1 \times nums[1] + 2 \times nums[2] + 3 \times nums[3] \\ F(1) &= 0 \times nums[3] + 1 \times nums[0] + 2 \times nums[1] + 3 \times nums[2] \\ F(2) &= 0 \times nums[2] + 1 \times nums[3] + 2 \times nums[0] + 3 \times nums[1] \\ F(3) &= 0 \times nums[1] + 1 \times nums[2] + 2 \times nums[3] + 3 \times nums[0] \end{align*} $$ 定義 $isum = \sum nums[i]$。將以上相鄰兩式相減可得 $$ \begin{align*} F(1) - F(0) &= nums[0] + nums[1] + nums[2] - 3 \times nums[3] = isum - 4 \times nums[3] \\ F(2) - F(1) &= nums[3] + nums[0] + nums[1] - 3 \times nums[2] = isum - 4 \times nums[2] \\ F(3) - F(2) &= nums[2] + nums[3] + nums[0] - 3 \times nums[1] = isum - 4 \times nums[1] \\ \end{align*} $$ 規律為 $$ F(i) = F(i-1) + isum - n \times nums[n-i] $$ 由於計算 $F(i)$ 時只會用到 $F(i-1)$ 的值，可以用一個變數 $dp$ 儲存資料，不需要用陣列。解題時，先計算加總 $isum$ 及 $dp = F(0)$，將答案 $ans$ 先設為 $dp$，再用 for 迴圈依序更新 $i = 1$ 到 $i = n-1$ 對應的 $dp$ 值，同時更新 $ans$。

Python 程式碼

Runtime: 143 ms, beats 52.49%. Memory: 31.37 MB, beats 18.77%.

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        n = len(nums)
        isum, dp = 0, 0  # 加總，F(k)
        for i, num in enumerate(nums):
            isum += num
            dp += i * num
        ans = dp  # 答案
        for i in range(1, n):  # 更新 i = 1 ~ n-1
            dp = dp + isum - n * nums[n-i]
            ans = max(ans, dp)
        return ans

LeetCode 解題筆記：3345. Smallest Divisible Digit Product I

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


LeetCode 題目連結：3345. Smallest Divisible Digit Product I

解題想法

簡單題。題目給兩個整數 $n$、$t$，要找出大於、等於 $n$ 且數字乘積可以被 $t$ 整除的最小整數。基本上答案不會太大，只要用一個 while 迴圈，從 $n$ 開始往上檢查數字乘積是否可以被 $t$ 整除，如果可以整除就回傳目前 $n$ 的值，反之則將 $n$ 加 $1$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.36 MB, beats 32.93%.

class Solution:
    def smallestNumber(self, n: int, t: int) -> int:
        while True:
            x = n
            d = 1
            while x:
                d *= x % 10
                x //= 10
            if d % t == 0:
                return n
            n += 1
        return -1

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"