LeetCode 解題筆記：2213. Longest Substring of One Repeating Character

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


LeetCode 題目連結：2213. Longest Substring of One Repeating Character

解題想法

困難題。題目給一個字串 $s$，長度為 $k$ 的字串 $queryCharacters$，長度為 $k$ 的整數陣列 $queryIndices$，第 $i$ 次查詢時會將 $s[queryIndices[i]]$ 改成 $queryCharacters[i]$，找出修改後的字串 $s$ 之中最長連續相同字母的子字串長度。由於這題 $s$ 最長為 $10^5$，查詢次數最多也是 $10^5$，如果每次修改 $s$ 之後都要從頭再找一次答案，這樣一定會超時。可以用線段樹 (segment tree) 解題，我一開始寫出來的 C++ 版本速度不快，將程式碼丟給 Gemini 詢問如何改寫程式碼才能加速，發現問題出在指標及配置記憶體花費太多時間，修改後速度快很多。

定義節點 Node class 或 struct，其中儲存了

• pre_len 從左端點開始的連續相同字元長度
• suf_len 從右端點開始的連續相同字元長度
• max_len 區間內最大連續長度
• total_len 區間總長度
• left_char 區間左端點的字元
• right_char 區間右端點的字元

定義自訂線段樹 class，初始化時設定字串 $s$，字串長度 $n$，樹的內容 $tree$，資料格式為 Node，長度為 $4n$。類別中再定義以下的函式

• _build 內部函式，建立樹的內容。
• _merge 內部函式，合併節點。
• _update 內部函式，單點更新。
• update 外部函式，用來呼叫 _update。
• query_max 外部函式，回傳根節點的最大連續長度。

Python 程式碼

Runtime: 4167 ms, beats 16.40%. Memory: 85.56 MB, beats 31.15%.

class Node:
    # 自訂節點類別
    def __init__(self, pre_len=0, suf_len=0, max_len=0, left_char='', right_char='', total_len=0):
        self.pre_len = pre_len  # 從左端點開始的連續相同字元長度
        self.suf_len = suf_len  # 從右端點開始的連續相同字元長度
        self.max_len = max_len  # 區間內最大連續長度
        self.left_char = left_char  # 區間左端點的字元
        self.right_char = right_char  # 區間右端點的字元
        self.total_len = total_len  # 區間總長度

class SegmentTree:
    # 自訂線段樹類別
    def __init__(self, s):
        self.n = len(s)  # 長度
        self.s = s  # 字串
        self.tree = [Node() for _ in range(4 * self.n)]  # 樹的內容
        # 呼叫內部函式 _build 建立樹，根節點索引值 1，左端點 0，右端點 n-1
        self._build(1, 0, self.n - 1)

    def _build(self, idx, start, end):
        # 內部函式，索引值 idx，左端點 start，右端點 end
        # 遞迴出口，左、右端點重合，建立新的節點
        if start == end:
            self.tree[idx] = Node(1, 1, 1, self.s[start], self.s[start], 1)
            return
        # 一般狀況，用遞迴建立左、右子節點
        mid = (start + end) // 2  # 中點
        self._build(2 * idx, start, mid)  # 遞迴，建立左子節點
        self._build(2 * idx + 1, mid + 1, end)  # 遞迴，建立右子節點
        self.tree[idx] = self._merge(self.tree[2 * idx], self.tree[2 * idx + 1])  # 合併左、右子節點成為父節點
    
    def _merge(self, left, right):
        # 內部函式，合併左、右子節點
        res = Node()  # 最後要回傳的節點
        res.total_len = left.total_len + right.total_len  # 更新線長度
        res.left_char = left.left_char  # 左端點字元
        res.right_char = right.right_char  # 右端點字元
        res.pre_len = left.pre_len  # 左端前綴長度
        res.suf_len = right.suf_len  # 右端後綴長度
        res.max_len = max(left.max_len, right.max_len)  # 更新最大長度
        # 如果左右交界處字元相同，進行跨區合併
        if left.right_char == right.left_char:
            cross_len = left.suf_len + right.pre_len
            res.max_len = max(res.max_len, cross_len)
            # 如果左子節點是同一個字元，更新前綴長度
            if left.pre_len == left.total_len:
                res.pre_len = left.total_len + right.pre_len
            # 如果右子節點是同一個字元，更新後綴長度
            if right.suf_len == right.total_len:
                res.suf_len = right.total_len + left.suf_len
        return res  # 回傳 res

    def _update(self, idx, start, end, target, new_char):
        # 內部函式，單點更新，目前處理節點索引值 idx，左端點 left，右端點 right，目標索引值 target，新的字元 new_char
        # 遞迴出口，左、右端點重合，更新 self.tree[idx]
        if start == end:
            self.tree[idx] = Node(1, 1, 1, new_char, new_char, 1)
            return
        # 一般狀況，遞迴，找到 target 之後再往上層更新父節點
        mid = (start + end) // 2  # 中點
        if target <= mid:  # 目標在左側
            self._update(2 * idx, start, mid, target, new_char)
        else:  # 目標在右側
            self._update(2 * idx + 1, mid + 1, end, target, new_char)
        self.tree[idx] = self._merge(self.tree[2 * idx], self.tree[2 * idx + 1])  # 合併
    
    def update(self, target, new_char):
        # 外部函式，呼叫 self._update
        self._update(1, 0, self.n - 1, target, new_char)
    
    def query_max(self):
        # 回傳根節點的最大連續重複長度
        return self.tree[1].max_len

class Solution:
    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:
        # 初始化線段樹物件
        tree = SegmentTree(s)
        ans = []
        # 處理更新及查詢
        for new_char, target in zip(queryCharacters, queryIndices):
            # 單點更新
            tree.update(target, new_char)
            # 查詢目前整體的最長連續重複字元長度
            ans.append(tree.query_max())
        return ans

LeetCode 解題筆記：2958. Length of Longest Subarray With at Most K Frequency

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


LeetCode 題目連結：2958. Length of Longest Subarray With at Most K Frequency

解題想法

中等難度題。題目給一個整數陣列 $nums$ 及一個整數 $k$，要找出 $nums$ 之中的最長連續子陣列，且子陣列之中每個數字出現的次數小於等於 $k$。這題很適合用滑動視窗 (sliding window) 解題。

1. $nums$ 的長度為 $n$，視窗左端點 $left$ 起始值為 $0$，答案 $ans$ 預設為 $0$，用字典 $cnt$ 記錄視窗範圍內的數字數量。
2. 用一層 for 迴圈跑視窗右端點 $right = 0$ 到 $right = n-1$，$cnt[nums[right]] += 1$。
3. 再用一層 while 迴圈，如果 $left < right$ 且 $cnt[nums[right]] > k$ 繼續執行，移除左端點的數字 $cnt[nums[left]] -= 1$，左端點向右移 1 格 $left += 1$。
4. 跑完 while 迴圈時，$nums[right]$ 到 $nums[left]$ 之間的數字數量都小於等於 $k$，視窗長度為 $right - left + 1$，這可能是新的答案，更新 $ans$。

Python 程式碼

用 defaultdict 比較方便。Runtime: 262 ms, beats 44.51%. Memory: 35.44 MB, beats 15.77%.

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        n = len(nums)  # 長度
        left = 0  # 視窗左邊界
        ans = 0  # 答案
        cnt = defaultdict(int)  # 視窗範圍內數字計數器
        for right in range(n):  # 視窗右邊界依序為 0 ~ n-1
            cnt[nums[right]] += 1  # 右邊界數字數量加 1
            # 如果左邊界小於右邊界，右邊界數字數量大於 k
            while left < right and cnt[nums[right]] > k:
                cnt[nums[left]] -= 1  # 左邊界數字數量減 1
                left += 1  # 左邊界向右移 1 格
            ans = max(ans, right - left + 1)  # 更新答案
        return ans

用預設的 dict，更新 $nums[right]$ 的數量時需要先檢查 $nums[right]$ 是否在 $cnt$ 之中，比較麻煩一點。Runtime: 262 ms, beats 44.51%. Memory: 35.20 MB, beats 94.91%.

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        n = len(nums)  # 長度
        left = 0  # 視窗左邊界
        ans = 0  # 答案
        cnt = dict()  # 視窗範圍內數字計數器
        for right in range(n):  # 視窗右邊界依序為 0 ~ n-1
            # 右邊界數字數量加 1
            if nums[right] not in cnt:
                cnt[nums[right]] = 1
            else:
                cnt[nums[right]] += 1
            # 如果左邊界小於右邊界，右邊界數字數量大於 k
            while left < right and cnt[nums[right]] > k:
                cnt[nums[left]] -= 1  # 左邊界數字數量減 1
                left += 1  # 左邊界向右移 1 格
            ans = max(ans, right - left + 1)  # 更新答案
        return ans

LeetCode 解題筆記：2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

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


LeetCode 題目連結：2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

解題想法

簡單題。我一直覺得我沒有弄清楚題目的意思，但是不小心就過關了，以下是我對題目的解釋。題目給一個索引值為 0 開頭的陣列 $nums$。如果 $nums[0]$ 到 $nums[i]$ 符合條件 $nums[j] = nums[j-1] + 1, ~ 1 \leq j \leq i$，則 $nums[0]$ 到 $nums[i]$ 為連續的 (sequential)。其中的特例為 $nums[0]$，只有 $nums[0]$ 也符合連續的條件。題目要回傳一個最小的整數 $x$，且 $x$ 大於、等於最長連續前綴 (longest sequential prefix)。我的想法是先從 $i = 0$ 開始找最長連續前綴加總 $psum$，接下來將 $nums$ 轉成集合 $num\_set$，用一個 while 迴圈檢查 $psum$ 是否在 $num\_set$ 之中，如果條件成立就將 $psum$ 加 $1$，用線性搜尋的方式找答案。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.22 MB, beats 51.82%.

class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        n, psum = len(nums), nums[0]
        for i in range(1, n):
            if nums[i] == nums[i-1] + 1:
                psum += nums[i]
            else:
                break
        
        num_set = set(nums)
        while psum in num_set:
            psum += 1
        return psum

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