ZeroJudge 解題筆記：n129.p1. 鋪磁磚問題

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


ZeroJudge 題目連結：n129.p1. 鋪磁磚問題

解題想法

題目只給一個整數 $n$，代表地板的總面積為 $1 \times n$，有 3 種可以用的地板面積 $1 \times 1$、$1 \times 2$、$1 \times 3$，要回傳組成長度 $n$ 的所有方法數。這題考無限背包，開一個長度為 $n+1$ 的陣列 $dp$，$dp[i]$ 代表地板總長度為 $i$ 的方法數。但是題目要找的是排列方法數，外層 for 迴圈要跑地板總長度 $1$ 到 $n$，內層的 for 迴圈跑可以用的地板長度 $1、2、3$，最後答案在 $dp[n]$。

Python 程式碼

使用時間約為 13 ms，記憶體約為 9.6 MB，通過測試。

n = int(input())  # 地板 1*n
dp = [0] * (n+1)  # 組成地板長度 i 的方法數
dp[0] = 1  # 長度 0 方法數 1
for j in range(1, n+1):  # 這題是排列，要先跑長度
    for p in range(1, 4):  # 三種地板長度 1, 2, 3
        if j >= p: dp[j] += dp[j - p]
print(dp[n])

C++ 程式碼

使用時間約為 1 ms，記憶體約為 3.9 MB，通過測試。

#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int n; scanf("%d", &n);  // 地板 1*n
    vector<long long> dp (n+1, 0);  // 組成地板長度 i 的方法數
    dp[0] = 1;  // 長度 0 方法數 1
    for(int j = 1; j <= n; j++) {  // 這題是排列，要先跑長度
        for(int p = 1; p <= 3; p++) {  // 三種地板長度 1, 2, 3
            if (j >= p) dp[j] += dp[j - p];
        }
    }
    printf("%lld\n", dp[n]);
    return 0;
}

LeetCode 解題筆記：3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

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


LeetCode 題目連結：3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

解題想法

困難題。題目給一個原來的字串 $s$ 及目標字串 $target$，兩個字串長度皆為 $n$，要找到一個大於 $target$ 且字典序最小的迴文字串，如果沒有則回傳空字串。這題與昨天的題目 3720. Lexicographically Smallest Permutation Greater Than Target 很像，但是多了迴文的條件，難度高很多。主要分成以下 3 個步驟：

1. 先檢查 $s$ 是否能組成迴文字串
2. 準備前半段可用的字母並將相異字母排序
3. 用 DFS 遞迴及回溯找答案，但是要加上剪枝節省時間，剪枝條件有
   1. 如果 is_greater 等於 False，不能放比 $target[idx]$ 小的字母。
   2. 如果 new_is_greater 等於 True，用剩下的字母組成答案。

Python 程式碼

Runtime: 11 ms, beats 90.91%. Memory: 20.40 MB, beats 7.58%.

class Solution:
    def lexPalindromicPermutation(self, s: str, target: str) -> str:
        n = len(s)  # 長度
        cnt = Counter(s)  # 字母計數器

        # 1. 先檢查 s 是否能組成迴文字串
        odd_cnt = 0  # 有幾個字母的數量為奇數數量
        mid_char = ""  # 如果某個字母數量為奇數，只能放在中間
        for char, freq in cnt.items():
            if freq % 2 == 1:
                odd_cnt += 1
                mid_char = char
        if odd_cnt > 1:  # 不只一個字母數量是奇數，回傳空字串
            return ""

        # 2. 準備前半段可用的字母並將相異字母排序
        half_cnt = {char: freq // 2 for char, freq in cnt.items() if freq // 2 > 0}
        unique_chars = sorted(half_cnt.keys())
        ans = ""  # 答案
        m = n // 2  # 前半段長度

        # 3. 主要的解題過程
        def dfs(idx, is_greater, path):
            nonlocal ans
            if ans: return True

            # 遞迴出口，已經填滿前半段
            if idx == m:
                # 組合成整個字串 = 前半段 + 中間字母 + path 反序組成的後半段
                full = "".join(path) + mid_char + "".join(path[::-1])
                # 如果 full > target，找到答案
                if full > target:
                    ans = full
                    return True
                return False

            # 由小到大檢查可用的字母
            for char in unique_chars:
                # 跳過已經用完的字母
                if half_cnt[char] == 0: continue
                # 剪枝，如果 is_greater == False，不能放比 target[idx] 小的字母
                if not is_greater and char < target[idx]: continue
                # 更新 char 的數量、path 及狀態
                half_cnt[char] -= 1
                path.append(char)
                new_is_greater = is_greater or (char > target[idx])
                # 剪枝，如果 new_is_greater == True，用剩下的字母組成答案
                if new_is_greater:
                    # 找出剩下的字母
                    rem = []
                    for c in unique_chars:
                        rem.extend([c] * half_cnt[c])
                    # 組成完整的前半段字串
                    first = "".join(path) + "".join(rem)
                    # 組成完整的答案
                    ans = first + mid_char + first[::-1]
                    return True
                # 遞迴
                if dfs(idx + 1, new_is_greater, path): return True
                # 回溯
                path.pop()
                half_cnt[char] += 1
            # 預設回傳 False
            return False

        # 呼叫 dfs 找答案
        dfs(0, False, [])
        return ans

ZeroJudge 解題筆記：d870.NOIP2000 3.乘积最大

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


ZeroJudge 題目連結：d870.NOIP2000 3.乘积最大

解題想法

題目給字串長度 $n$、乘號數量 $k$、字串 $s$，要在 $s$ 之中加入 $k$ 個乘以，回傳乘積的最大值。這題需要用 DFS 找插入乘號的位置，並用字典或是 @lru_cache 記憶化節省時間。不過這題的字串最長為 40，乘積很大，如果用 C++ 解題要自己處理大數乘法，所以我只寫了 Python 版本。

Python 程式碼

使用時間約為 14 ms，記憶體約為 9.5 MB，通過測試。

def solve():
    import sys

    data = sys.stdin.read().split()
    n, k, s = int(data[0]), int(data[1]), data[2]

    # 記憶化 DFS
    memo = dict()
    
    def dfs(start, rem):
        # 遞迴出口，沒有乘號能加，將剩下的字串轉成整數再回傳
        if rem == 0:
            return int(s[start:])
        # 如果 memo 之中有 (start, rem)，直接回傳
        if (start, rem) in memo:
            return memo[start, rem]
        # 從 start + 1 到 n - rem 找加入乘號的位置
        imax = -1
        for i in range(start + 1, n - rem + 1):
            left_num = int(s[start : i])
            right_max = dfs(i, rem - 1)
            if right_max != -1:
                imax = max(imax, left_num * right_max)
        memo[start, rem] = imax
        return imax
    
    # 呼叫 dfs，代入起點 0，乘號的數量 k
    print(dfs(0, k))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3720. Lexicographically Smallest Permutation Greater Than Target

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


LeetCode 題目連結：3720. Lexicographically Smallest Permutation Greater Than Target

解題想法

中等難度題。題目給一個字串 $s$ 及目標字串 $target$，將 $s$ 重新排列成大於 $target$ 之中最小的字串。由於字串的長度最長為 300，如果用 next_permutation 測試所有的排列方式一定會超時，一定要用 dfs 並搭配剪枝才不會超時。整個題目最主要的解題過程在於 dfs 函式，代入的項目有：

1. 目前檢查的 $target$ 索引值 $idx$
2. 目前選取的字串 $path$ 是否已經大於 $target$ 的前綴 is_greater
3. 目前選取的字串 $path$
4. 已經選取的字母索引值 $used$

函式主要分成幾個部分：

1. 已經找到答案，直接回傳 true。
2. 遞迴出口，已經找到最後一位，如果 is_greater 為 true，設定答案 $ans$，回傳 true。
3. 由左到右放入字母，裡面再分成以下的步驟：
   1. 跳過已經選取的字母
   2. 剪枝，跳過重覆且不符合要求的字母。
   3. 剪枝，如果 is_greater == false，不能放入小於 target[idx] 的字母。
   4. 試著放入 ch，如果新的狀態 new_is_greater 為 true，加入剩下的字母就是答案；反之，遞迴，往下走，遞迴完之後再回溯。

Python 程式碼

Runtime: 55 ms, beats 5.26%. Memory: 20.04 MB, beats 11.84%.

class Solution:
    def lexGreaterPermutation(self, s: str, target: str) -> str:
        n = len(s)  # 長度
        chars = sorted(s)  # 字母先排序
        ans = ""  # 答案

        # DFS，idx 目前正在比較 target[idx]，is_greater 目前的字串是否大於 target 前綴
        # path 目前的字串，used 已選取字母的索引值
        def dfs(idx, is_greater, path, used):
            nonlocal ans  # 改成 nonlocal 才能修改外部變數
            if ans: return True  # 已經找到答案，提早結束
            # 遞迴出口，idx 等於 n
            if idx == n:
                if is_greater:  # 找到大於目標的字串
                    ans = "".join(path)
                    return True
                return False
            # 由左到右放入字母
            for i in range(n):
                # 跳過已經選取的字母
                if used[i]: continue
                # 剪枝，跳過重覆且不符合條件的字母
                if i > 0 and chars[i] == chars[i-1] and not used[i-1]: continue
                # 剪枝，如果目前的字串還沒有大於目標，不能放入比 target[idx] 小的字母
                ch = chars[i]
                if not is_greater and ch < target[idx]: continue
                # 試著加入 ch
                path.append(ch)
                used[i] = True
                new_is_greater = is_greater or (ch > target[idx])
                # 剪枝，如果 new_is_greater == True，只要放入剩下的字母就是答案
                if new_is_greater:
                    for j in range(n):
                        if not used[j]:
                            path.append(chars[j])
                    ans = "".join(path)
                    return True
                # 遞迴
                if dfs(idx + 1, new_is_greater, path, used):
                    return True
                # 回溯
                path.pop()
                used[i] = False
            # 預設回傳 False
            return False
        # 呼叫 DFS
        dfs(0, False, [], [False] * n)
        return ans

ZeroJudge 解題筆記：d904.換零錢

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


ZeroJudge 題目連結：d904.換零錢

解題想法

無限背包問題。硬幣的面額存入陣列 $coins$，不需要排序。假設總金額為 $c$，開一個長度為 $c + 1$ 的一維陣列 $dp$，$dp[i]$ 代表總金額為 $i$ 需要的硬幣最少數量。由於題目的金額上限為 $1000$、面額最小值為 $1$，所以硬幣數量的上限為 $1000$，所以建立 $dp$ 陣列時，可以指定長度為 $1001$，預設值皆為超過上限的 $100000$，不需要使用 INT_MAX 或是 float('inf')。

Python 程式碼

使用時間約為 13 ms，記憶體約為 9.6 MB，通過測試。

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        c = int(data[ptr])
        n = int(data[ptr + 1])
        ptr += 2
        coins = tuple(map(int, data[ptr : ptr + n]))
        ptr += n
        # 無限背包問題，dp[i] 代表總金額 i 的最少硬幣數量
        dp = [float('inf')] * (c+1)
        dp[0] = 0
        for coin in coins:
            for j in range(coin, c + 1):
                if dp[j - coin] != float('inf'):
                    dp[j] = min(dp[j], dp[j - coin] + 1)
        result.append(f"{dp[c]:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：2904. Shortest and Lexicographically Smallest Beautiful String

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


LeetCode 題目連結：2904. Shortest and Lexicographically Smallest Beautiful String

解題想法

中等難度題。題目給一個只有 01 的字串 $s$，要找出 $s$ 之中連續的子字串而且子字串中正好有 $k$ 個 $1$，回傳符合要求的最短子字串，如果有多個長度相同且符合規則的子字串，回傳之中字典序最小者。由於題目要找的是連續子字串，很適合用滑動視窗解題。先用一個 for 迴圈更新視窗右端點 $right$ 從 $0$ 到 $n-1$，先依照 $s[right]$ 更新 $1$ 的數量 $ones$；再用一個 while 迴圈，如果 $ones > k$ 或是 $ones = k$ 且 $s[left] = '0'$，更新 $ones$、再將 $left$ 向右移一格；跑完 while 迴圈之後，如果 $ones = k$，而且子字串長度較短或長度相等但子字串字典序較小就更新答案。由於用 C 語言處理字串很麻煩，我就不寫 C 語言版本了。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.32 MB, beats 30.63%.

class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        # 長度，目前範圍中有幾個1，視窗左端點
        n, ones, left = len(s), 0, 0
        ans = "1" * (n+1)  # 答案，預設為超出上限的字串
        # 滑動視窗，移動右端點
        for right in range(n):
            # 更新範圍內 1 的數量
            if s[right] == '1': ones += 1
            # ones 大於 k 或 ones 等於 k 且 s[left] 是 0
            while ones > k or (ones == k and s[left] == '0'):
                if s[left] == '1': ones -= 1  # 更新範圍內 1 的數量
                left += 1  # 向右移1格
            # 如果 1 的數量等於 k，更新答案
            if ones == k:
                sub = s[left : right + 1]  # 子字串
                length = right - left + 1  # 子字串長度
                # 如果子字串長度較短或長度相等但子字串字典序較小，更新答案
                if length < len(ans) or (length == len(ans) and sub < ans): 
                    ans = sub
        return ans if ans != "1" * (n+1) else ""

LeetCode 解題筆記：3718. Smallest Missing Multiple of K

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


LeetCode 題目連結：3718. Smallest Missing Multiple of K

解題想法

簡單題。題目給一個陣列 $nums$ 及一個整數 $k$，要找出不在 $nums$ 之中 $k$ 的倍數最小值。這題可以用集合或是字典記錄 $nums$ 之中的數字；由於測資的範圍不大，也可以用一個長度為 10001 的陣列，將 $nums$ 之中的數字標記為 True。如果用 Python 解題，用 set 及 dict 速度最快；如果用 C 或 C++ 解題，用陣列速度最快。因為答案在 1 到 100 之間，設定一個變數 i，從 1 開始往上線性搜尋就好。

Python 程式碼

set. Runtime: 0 ms, beats 100.00%. Memory: 19.30 MB, beats 18.61%.

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        num_set = set(nums)
        i = 1
        while i*k in num_set: i += 1
        return i*k

dict. Runtime: 0 ms, beats 100.00%. Memory: 19.24 MB, beats 53.35%.

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        num_map = {num: True for num in nums}
        i = 1
        while i*k in num_map: i += 1
        return i*k

list. Runtime: 3 ms, beats 20.84%. Memory: 19.17 MB, beats 88.59%.

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        state = [False] * 10001
        for num in nums: state[num] = True
        i = 1
        while state[i*k]: i += 1
        return i*k

LeetCode 解題筆記：1872. Stone Game VIII

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


LeetCode 題目連結：1872. Stone Game VIII

解題想法

困難題。題目給一個陣列 $stones$ 代表一列石頭由左到右的分數，Alice 與 Bob 兩人輪流從左邊拿走 $x$ 個石頭，且 $x > 1$，可以獲得拿走的石頭的總分，然後將一個等於總分的石頭放在最左邊，只剩下一個石頭時遊戲結束，固定由 Alice 先行動。假設 Alice 要使分差最大，Bob 要使分差最小，回傳遊戲結束時的分差。

由於每次行動時會拿走前 $x$ 顆石頭，再將一顆等於總分的石頭放在最左邊，因此下一個人行動時拿到的石頭會包含上一次取走的 $x$ 顆石頭的總分。計算分差時會用到前 $x$ 顆石頭的總分，可以先建立前綴和陣列 $psum$。這題要用動態規畫解題，理論上比較適合由最後的狀態往回推。假設 $dp[i]$ 代表處理 $stones[i]$ 時的最大分差，邊界條件為最後一次行動時會拿走所有的石頭，也就是 $i = n-1$ 時 $dp[i] = psum[n-1]$。更新狀態時有兩種可能性：

1. 拿走 $stones[i]$，最大分差為 $psum[i] - dp[i+1]$
2. 不拿 $stones[i]$，最大分差為 $dp[i+1]$

更新時最這兩者之中較大者。由於更新時只需要用到 $dp[i+1]$ 的值，可以不需要建立完整的陣列，只要用一個變數 $dp$ 記錄最大分差，用 $dp = max(psum[i] - dp, dp)$ 更新就好。

另一個寫法是由 $i = 0$ 開始處理，並用記憶化及遞迴往下找 $i + 1$ 的狀態，直到 $i = n-1$ 時結束遞迴。如果在 Python 用這個寫法，必須引入 sys 函式庫，並用 sys.setrecursionlimit(200000) 調整遞迴深度，否則會遇到遞迴深度過深的問題。

Python 程式碼

方法1。Runtime: 674 ms, beats 65.09%. Memory: 32.25 MB, beats 98.22%.

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        # 建立前綴和陣列
        n = len(stones)
        psum = stones[:]
        for i in range(1, n):
            psum[i] += psum[i-1]
        """
         動態規畫，dp[i] 代表選擇索引值 i 的最大分差，由最後的狀態往前推
         狀況1，選擇拿 psum[i]，下一個狀態的 dp[i+1]，目前最大分差為 psum[i] - dp[i+1]
         狀況2，不拿 psum[i]，目前最大分差為 dp[i+1]
        """
        dp = psum[-1]  # 邊界條件，最後一次要全部拿走
        for i in range(n-2, 0, -1):  # 只跑 i = n-2 ~ 1，因為一次至少拿 2 個石頭
            dp = max(psum[i] - dp, dp)
        return dp

方法2。Runtime: 770 ms, beats 14.20%. Memory: 83.57 MB, beats 11.24%.

import sys
sys.setrecursionlimit(200000)  # 調整遞迴深度

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        # 建立前綴和陣列
        n = len(stones)
        psum = stones[:]
        for i in range(1, n):
            psum[i] += psum[i-1]

        # 記憶化及遞迴
        memo = [None] * n

        def dfs(i):  # 目前選擇索引值 i
            # 遞迴出口，最後一次只能全拿
            if i == n-1:
                return psum[-1]
            # 如果 memo 之中有已經算過的值，直接回傳
            if memo[i] is not None:
                return memo[i]
            # 狀態轉移
            skip = dfs(i+1)  # 不拿 psum[i]
            take = psum[i] - skip  # 拿 psum[i]
            memo[i] = max(take, skip)  # 選擇較大者
            return memo[i]

        # 呼叫 dfs，代入 i = 1，因為至少要拿 2 顆石頭
        return dfs(1)

LeetCode 解題筆記：1927. Sum Game

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


LeetCode 題目連結：1927. Sum Game

解題想法

中等難度題。題目給一個字串 $num$，其中只包含數字 0 ~ 9 及 ?，Alice 和 Bob 兩個人輪流行動，由 Alice 先行動，每次行動時可以將一個問𢛶山改成 0 ~ 9 之中的一個數字。如果最後 $num$ 的左半邊加總等於右半邊的加總則 Bob 獲勝，回傳 False；反之則 Alice 獲勝，回傳 True。這題困難的地方在於分析勝敗條件，程式碼反而很簡單。

如果 Bob 要獲勝，第一個條件是左、右兩側的問號數量必須相同，如果數量不同，Alice 會多行動一次，一次可以讓兩側的加總不相等。第二個條件是兩側的問號數量差乘以 9 必須等於兩側總和差乘以 2。先考慮兩側都有問號的狀況，如果 Alice 將左側一個問號改成數字 $x$，Bob 可以將右側的一個問號也改成數字 $x$，兩者的效果就會抵消。再考慮同側問號的狀況，因為 Alice 會盡量讓兩側加總差異越大越好，假設改成 $x$，Bob 為了讓兩側加總相等，會將同側另一個問號改成 $9 - x$。假設右側問號比左側問號多 $\Delta q$ 個，則多出來的問號產生的數字加總必須等於左側數字加總減去右側數字加總 $$ \frac{\Delta q}{2} \times 9 = lsum - rsum \Rightarrow \Delta q \times 9 = (lsum - rsum) \times 2 $$

Python 程式碼

Runtime: 59 ms, beats 50.00%. Memory: 19.68 MB, beats 98.82%.

class Solution:
    def sumGame(self, num: str) -> bool:
        # 1. 計算左、右兩側數字加總、問號數量
        n = len(num)  # 長度
        lsum, rsum = 0, 0  # 左側數字加總，右側數字加總
        lque, rque = 0, 0  # 左側問號數量，右側問號數量
        for i in range(n//2):
            if num[i] == '?':
                lque += 1
            else:
                lsum += int(num[i])
        for i in range(n//2, n):
            if num[i] == '?':
                rque += 1
            else:
                rsum += int(num[i])
        # 2. 問號數量如果是奇數，Alice 多行動一次，Alice 必勝
        if (lque + rque) % 2 == 1: return True
        # 3. dq = rque - lque，同側每一對問號可以產生數字總和 9
        # 必須抵消 lsum - rsum，Bob 才會獲勝
        return (rque - lque) * 9 != (lsum - rsum) * 2

LeetCode 解題筆記：3622. Check Divisibility by Digit Sum and Product

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


LeetCode 題目連結：3622. Check Divisibility by Digit Sum and Product

解題想法

簡單題。題目給一個整數 $n$，假設 $n$ 的每個數字相加為 $dsum$，每個數字相乘為 $prod$，回傳 $n$ 是否可以被 $dsum + prod$ 整除。建立變數 $x = n$、$dsum = 0$、$prod = 1$，用一個 while 迴圈取出 $x$ 的每個數字，計算 $dsum$ 及 $prod$，最後回傳 $n % (dsum + prod) == 0$。也可以將 $n$ 轉成字串 $s$，再依序由 $s$ 讀取每個位數的字元，計算 $prod$ 及 $dsum$，速度也很快。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.34 MB, beats 24.05%.

class Solution:
    def checkDivisibility(self, n: int) -> bool:
        x, prod, dsum = n, 1, 0
        while x:
            d = x % 10
            x //= 10
            prod *= d
            dsum += d
        return n % (prod + dsum) == 0

Runtime: 0 ms, beats 100.00%. Memory: 19.32 MB, beats 24.05%.

class Solution:
    def checkDivisibility(self, n: int) -> bool:
        s = str(n)
        prod, dsum = 1, 0
        for c in s:
            d = int(c)
            prod *= d
            dsum += d
        return n % (prod + dsum) == 0