LeetCode 解題筆記：3524. Find X Value of Array I

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


LeetCode 題目連結：3524. Find X Value of Array I

解題想法

中等難度題，題目正整數陣列 $nums$、一個正整數 $k$，可以移 $nums$ 之中移除不重疊的前綴子陣列及後綴子陣列，使 $nums$ 乘下的元素積乘對 $k$ 取餘數，計算得到各種餘數有幾種方法數。題目下方有提示：

1. 用動態規畫解題。
2. 定義 $dp[i][r]$ 為以索引值 $i$ 為結尾的元素乘積，對 $k$ 取餘數為 $r$ 的方法數。
3. 將每一個索引值的 $dp[i][r]$ 加起來，計算答案 $ans[r]$。

基本上按照提示寫程式碼，應該就可以得到答案。在更新 $dp$ 陣列的過程中，每次相乘後都要對 $k$ 取餘數，可以避免數字過大。而且更新 $dp$ 時只需要用到前一個數字的狀態，可以用滾動陣列節省記憶體。

Python 程式碼

Runtime: 435 ms, beats 26.32%. Memory: 46.36 MB, beats 19.74%.

class Solution:
    def resultArray(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        # dp[i][j] 代表以索引值 i-1 結尾，其元素乘積除以 k 餘數為 j 的子陣列數量
        dp = [[0]*k for _ in range(n+1)]
        ans = [0]*k  # 答案
        for i in range(1, n+1):
            # nums[i-1] 為長度 1 的子陣列
            rem = nums[i-1] % k
            dp[i][rem] = 1
            # 內層迴圈，跑 j = 0 ~ k-1，將目前的數字接在前一個結尾的子陣列之後
            for j in range(k):
                if dp[i-1][j] > 0:  # 如果有前一個結尾對應的子陣列數量
                    new_rem = (j * rem) % k
                    dp[i][new_rem] += dp[i-1][j]
            # 將這一回産生的答案都加到 ans
            for j in range(k):
                ans[j] += dp[i][j]
        # 回傳答案
        return ans

LeetCode 解題筆記：3498. Reverse Degree of a String

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


LeetCode 題目連結：3498. Reverse Degree of a String

解題想法

簡單題，題目給一個字串 $s$，將 $s[i]$ 換算成 $26 - (s[i] - 'a')$，再乘以 $i+1$，將全部的值加起來並回傳，用一個 for 迴圈就解決了。

Python 程式碼

Runtime: 3 ms, beats 97.65%. Memory: 19.30 MB, beats 55.57%.

class Solution:
    def reverseDegree(self, s: str) -> int:
        ans = 0
        for i, c in enumerate(s, start=1):
            ans += (26 - ord(c) + ord('a')) * i
        return ans

Runtime: 3 ms, beats 97.65%. Memory: 19.32 MB, beats 19.13%.

class Solution:
    def reverseDegree(self, s: str) -> int:
        return sum((26 - ord(c) + ord('a')) * i for i, c in enumerate(s, start=1))

LeetCode 解題筆記：1401. Circle and Rectangle Overlapping

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


LeetCode 題目連結：1401. Circle and Rectangle Overlapping

解題想法

中等難度題，題目給一個圓的圓心坐標 $(xCenter, yCenter)$ 及半徑 $radius$，一個長方形的左下角頂點坐標 $(x1, y1)$，右上角頂點坐標 $(x2, y2)$，回傳這個圓形與長方形是否重疊，只要邊緣接觸到就當作重疊。這題的下方有提示，計算圓心與長方形最接近的點之間的距離，再判斷距離是否小於等於半徑，基本上按照這個提示寫程式就能過關。另外有一個狀況要記得考慮，圓心可能在長方形之中，這樣也是重疊，要回傳 True。

Python 程式碼

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

class Solution:
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        d = 0
        # 如果圓心在長方形內
        if x1 <= xCenter <= x2 and y1 <= yCenter <= y2:
            return True
        # 如果圓心在長方形左上角
        elif xCenter <= x1 and yCenter >= y2:
            d = (xCenter - x1)**2 + (yCenter - y2)**2
        # 如果圓心在長方形左下角
        elif xCenter <= x1 and yCenter <= y1:
            d = (xCenter - x1)**2 + (yCenter - y1)**2
        # 如果圓心在長方形左側
        elif xCenter <= x1 and y1 < yCenter < y2:
            d = (xCenter - x1)**2
        # 如果圓心在長方形右上角
        elif xCenter >= x2 and yCenter >= y2:
            d = (xCenter - x2)**2 + (yCenter - y2)**2
        # 如果圓心在長方形右下角
        elif xCenter >= x2 and yCenter <= y1:
            d = (xCenter - x2)**2 + (yCenter - y1)**2
        # 如果圓心在長方形右側
        elif xCenter >= x2:
            d = (xCenter - x2)**2
        # 如果圓心在長方形上方
        elif yCenter >= y2:
            d = (yCenter - y2)**2
        # 如果圓心在長方形下方
        elif yCenter <= y1:
            d = (yCenter - y1)**2
        return d <= radius**2

LeetCode 解題筆記：735. Asteroid Collision

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


LeetCode 題目連結：735. Asteroid Collision

解題想法

中等難度題，題目給一個陣列 $asteroids$，索引值代表小行星的位置，數值的絕對值代表小行星的大小，正值代表小行星向右移動，負值代表小行星向左移動，每個小行星的速度量值都相等。如果兩個小行星碰撞，會留下較大的小行星；如果兩者一樣大，兩者一起撞掉。題目要求最後留下來的小行星資料。

這題可以用堆疊解題。先建一個 list 或 vector $st$。用 for 迴圈依序讀取小行星的大小及移動方向 $a$，如果 st 是空的、st 最後一項是負的或者st 最後一項是正的且 a 是正的，不會碰撞，直接加入 a；如果發生碰撞，再用一個 while 迴圈，檢查 $a$ 與 $st$ 最後一項的關係，再決定是否移除 $st$ 的最後一項，以及是否要將 $a$ 加入 $st$。詳細的過程請看程式碼及註解。

Python 程式碼

Runtime: 3 ms, beats 94.41%. Memory: 20.38 MB, beats 33.14%.

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        st = []
        for a in asteroids:
            # 如果 st 是空的、st 最後一項是負的或者st 最後一項是正的且 a 是正的，不會碰撞，直接加入 a
            if not st or st[-1] < 0 or (st[-1] > 0 and a > 0):
                st.append(a)
            else:  # 發生碰撞
                add_new = True  # 是否加入 a
                # 如果 st 有資料、 st 最後一項是正的且 a 是負的，發生碰撞
                while st and st[-1] > 0 and a < 0:
                    # a 量值較大，st 最後一項被撞掉
                    if abs(a) > st[-1]:
                        st.pop()
                    # 一樣大，st 最後一項及 a 同時被撞掉
                    elif abs(a) == st[-1]:
                        st.pop()
                        add_new = False
                        break
                    # a 較小，a 被撞掉
                    else:
                        add_new = False
                        break
                # 加入 a
                if add_new: st.append(a)
        return st

LeetCode 解題筆記：1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

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


LeetCode 題目連結：1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

解題想法

中等難度題，題目給一個陣列 $arr$ 與一個整數 $target$，要找出 $2$ 個不重疊、加總等於 $target$ 的連續子陣列，回傳這兩個子陣列長度相加的最小值。題目下方有提示：

1. 建立一個陣列 $prefix$，$prefix[i]$ 代表在 $i$ 之前結束、加總等於 $target$ 的連續子陣列最短長度。再建立一個陣列 $suffix$，$suffix[i]$ 代表從 $i$ 開始、加總等於 $target$ 的連續子陣列最短長度。
2. 檢查 $i = 0$ 到 $i = n-1$，找出 $prefix[i] + suffix[i]$ 的最小值。
3. 如果在建立 $prefix, suffix$ 時遇到困難，可以先將所有的值都設定成無窮大，分別先找出加總等於 $target$ 的前綴、後綴連續子陣列長度，之後再轉換成最短長度。

基本上按照以上的提示寫程式碼就可以過關了。

Python 程式碼

Runtime: 260 ms, beats 29.61%. Memory: 31.07 MB, beats 83.24%.

class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        n = len(arr)  # 長度
        maxn = n + 1  # 長度加 1，答案不可能大於 n
        
        # 1. 用滑動視窗找 prefix
        prefix = [maxn] * n  # prefix[i] 代表於 i-1 結束，子陣列和等於 target 的長度
        rsum, left = 0, 0
        for right in range(n - 1):
            rsum += arr[right]
            while left < right and rsum > target:
                rsum -= arr[left]
                left += 1
            if rsum == target:
                length = right - left + 1
                prefix[right + 1] = min(prefix[right + 1], length)
        
        # 2. 再將 prefix[i] 改成從左往右找，於 i-1 結束、子陣列和等於 target 的最短長度
        pmin = maxn
        for i in range(1, n):
            if prefix[i] < pmin:
                pmin = prefix[i]
            elif prefix[i] > pmin:
                prefix[i] = pmin
        
        # 3. 用滑動視窗找 prefix
        suffix = [maxn] * n  # suffix[i] 代表於 i 結束，後綴子陣列和等於 target 的長度
        lsum, ri = 0, n-1
        for le in range(n-1, -1, -1):
            lsum += arr[le]
            while ri > le and lsum > target:
                lsum -= arr[ri]
                ri -= 1
            if lsum == target:
                length = ri - le + 1
                suffix[le] = min(suffix[le], length)
        
        # 4. 再將 suffix[i] 改成從右往左找，於 i 結束、後綴子陣列和等於 target 的最短長度
        smin = maxn
        for i in range(n-1, -1, -1):
            if suffix[i] < smin:
                smin = suffix[i]
            elif suffix[i] > smin:
                suffix[i] = smin

        # 5. 答案預設為 maxn * 2，從 i = 0 ~ n-1 找 prefix[i] + suffix[i] 的最小值
        ans = maxn * 2
        for i in range(n):
            if prefix[i] < maxn and suffix[i] < maxn:
                ans = min(ans, prefix[i] + suffix[i])
        # 如果 ans 小於預設值，回傳 ans；反之回傳 -1
        return ans if ans < maxn * 2 else -1

ZeroJudge 解題筆記：a007.判斷質數

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


ZeroJudge 題目連結：a007.判斷質數

解題想法

這題要判斷讀取到的整數 $x$ 是否為質數，且 $2 \leq x \leq 2147483647$，最大值為 int 的上限。由於測資為多筆輸入，且最多有 $200000$ 筆，需要想辦法加速才行。這題的提示是建表，出題者的意思是建一個 $46340$ 以內的質數表，因為 $\sqrt{2147483647} \approx 46340$，如果要判斷 $x$ 是否為質數，只要用小於 $\sqrt{x}$ 的質數試除，如果 $x$ 可以被某個質數整除，則 $x$ 不是質數；如果所有小於 $\sqrt{x}$ 的質數都無法整除 $x$，則 $x$ 不是質數。所以解題時先用埃拉托斯特尼篩法建 $46340$ 以內的質數表，再用 while 迴圈讀取 $x$ 直到 EOF 為止，取出質數表中小於 $\sqrt{x}$ 的質數試除即可得到答案。但是這題如果用 Python 解題，即使按這個個邏輯寫程式碼也會超時，需要用比較特別的判斷質數方法才能過關。

C++ 程式碼

解題時間約為 0.6 s，使用記憶體約為 3.8 MB。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    const int maxn = 46340;  // sqrt(2147483647)
    vector<bool> sieve (maxn + 1, true);
    sieve[0] = false;
    sieve[1] = false;
    for(int i = 2; i <= (int)sqrt(maxn); i++) {
        if (sieve[i]) {
            for(int j = i*i; j <= maxn; j += i) {
                sieve[j] = false;
            }
        }
    }
    vector<int> primes;
    for(int i = 0; i <= maxn; i++) {
        if (sieve[i]) {
            primes.push_back(i);
        }
    }
    
    int x;
    while(cin >> x) {
        bool is_prime = true;
        for(int p : primes) {
            if (p*p > x) break;
            if (x % p == 0) {
                is_prime = false;
                break;
            }
        }
        cout << (is_prime ? "質數\n" : "非質數\n");
    }
    return 0;
}

LeetCode 解題筆記：1621. Number of Sets of K Non-Overlapping Line Segments

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


LeetCode 題目連結：1621. Number of Sets of K Non-Overlapping Line Segments

解題想法

中等難度題，題目給兩個整數 $n$ 與 $k$，代表共有 $n$ 個端點，端點編號為 $0$ 到 $n - 1$，計算以這 $n$ 個端點畫出不重疊的 $k$ 條線段共有幾種方法，由於答案很大，回傳值為方法數對 $10^9 + 7$ 取餘數。這題可以用動態規畫解題，定義長度為 $n+1$ 的一維陣列 $dp$，$dp[j]$ 代表畫出 $n$ 條線段的方法數，初始值為 1，因為畫出 $j$ 條線段至少有 $1$ 種畫法；另外 $dp[0] = 0$，因為畫出 $0$ 條線段的方法數為 $0$。為了縮短更新 $dp$ 內容需要的時間，另外開一個長度為 $n+1$ 的陣列 $psum$，$psum[i] = dp[0] + dp[1] + \dots + dp[i]$。用兩層 for 迴圈更新 $dp$，外層 for 迴圈跑線段數量 $j = 1$ 到 $j = k$，每次先開兩個長度為 $n+1$ 的陣列 new_dp, new_psum，用來儲存新的 dp 及前綴和；內層的 for 迴圈跑端點 $i = 2$ 到 $i = n$，狀態轉移的方式為不使用這個端點的方法數 + 使用這個端點當作右端點的方法數，同時還要更新新的方法數對應的前綴和，每次更新時都要對 $10^9 + 7$ 取餘數，更新完畢之後將 dp, new_dp 及 psum, new_psum 的資料交換。最後的答案會在 $dp[n]$。

Python 程式碼

Runtime: 517 ms, beats 48.28%. Memory: 19.52 MB, beats 55.17%.

class Solution:
    def numberOfSets(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        dp = [1] * (n + 1)  # dp[j] 畫出 j 條線段的方法數
        dp[0] = 0  # 初始值，畫出 0 條，方法數 0
        psum = [i for i in range(n + 1)]  # dp[0] + ... + dp[i] 前綴和

        for j in range(1, k + 1):  # 畫 1 ~ k 條線段
            new_dp = [0] * (n + 1)  # 新的狀態
            new_psum = [0] * (n + 1)  # 新的前綴和
            for i in range(2, n + 1):  # 跑端點 2 ~ n
                # 狀態轉移，不使用這個端點 + 使用這個端點當作右端點的方法數
                new_dp[i] = (new_dp[i-1] + psum[i-1]) % MOD
                # 更新前綴和
                new_psum[i] = (new_psum[i-1] + new_dp[i]) % MOD
            # 交換資料
            dp = new_dp
            psum = new_psum
        return dp[n]

LeetCode 解題筆記：2472. Maximum Number of Non-overlapping Palindrome Substrings

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


LeetCode 題目連結：2472. Maximum Number of Non-overlapping Palindrome Substrings

解題想法

困難題，題目給一個字串 $s$ 與整數 $k$，要找出 $s$ 之中不重疊且長度至少為 $k$ 的迴文子字串數量。由於字串長度最長為 $1000$，需要先計算所有子字串是否為迴文字串，再用動態規畫找答案。假設 $s$ 的長度為 $n$，先建一個大小為 $n \times n$ 的二維陣列 is_pal，is_pal[i][j] 代表 $s[i...j]$ 是否為迴文字串。接下來再建一個長度為 $n+1$ 的一維陣列 $dp$，$dp[i]$ 代表以 $s[i-1]$ 為結尾時不重疊且長度至少為 $k$ 的迴文子字串數量，預設值皆為 $0$。更新狀態時先取 $dp[i] = dp[i-1]$，再跑起點 $j$ 從 $0$ 到 $i - k$，如果 $s[j ... i-1]$ 是迴文字串，取 $dp[i], dp[j] + 1$ 較大者更新 $dp[i]$。全部跑完之後答案在 $dp[n]$。

Python 程式碼

Runtime: 2230 ms, beats 25.77%. Memory: 50.73 MB, beats 14.43%.

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)
        # 1. 建表，列出 s[i : j+1] 是否為迴文字串
        is_pal = [[False] * n for _ in range(n)]
        for i in range(n-1, -1, -1):  # 由後往前掃
            is_pal[i][i] = True  # 長度 1，一定是迴文字串
            for j in range(i+1, n):  # 掃過 j = i + 1 ~ j = n - 1
                if s[i] == s[j]:
                    if j == i + 1 or is_pal[i+1][j-1]:  # 長度是 2 或內部也是迴文
                        is_pal[i][j] = True
        
        # 2. 一維 dp，計算 s[:i+1] 不重疊的迴文子字串數量
        dp = [0] * (n + 1)
        for i in range(1, n+1):
            # 不取 s[i-1] 為結尾的子字串
            dp[i] = dp[i-1]
            # 跑起點 j，長度至少為 k
            for j in range(i-k+1):
                if is_pal[j][i-1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return dp[n]

LeetCode 解題筆記：836. Rectangle Overlap

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


LeetCode 題目連結：836. Rectangle Overlap

解題想法

簡單題，題目給兩個長度為 $4$ 的陣列，代表長方形的頂點坐標，其中 $(x1, y1)$ 為左下方頂點坐標，$(x2, y2)$ 為右上方頂點坐標，回傳這兩個長方形是否重疊，如果只是頂點或邊互相接觸不算重疊。這題反過來寫比較簡單，列出 $4$ 種不重疊的狀況，只要 $4$ 種狀況其中一種成立就不會重疊，外面再加上 not，回傳反過來的狀態。假設兩個長方形的頂點分別為 $(x1, y1, x2, y2), (x3, y3, x4, y4)$，不重疊的狀況為：

1. $x1 \geq x4$，長方形 1 在長方形 2 的右側。
2. $y1 \geq y4$，長方形 1 在長方形 2 的上方。
3. $x2 \leq x3$，長方形 1 在長方形 2 的左側。
4. $y2 \leq y3$，長方形 1 在長方形 2 的下方。

Python 程式碼

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

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        x1, y1, x2, y2 = rec1
        x3, y3, x4, y4 = rec2
        return not (x2 <= x3 or x1 >= x4 or y1 >= y4 or y2 <= y3)

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 9.04 MB, beats 100.00%.

class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3];
        int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3];
        return !(x2 <= x3 || x1 >= x4 || y1 >= y4 || y2 <= y3);
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.60 MB, beats 54.43%.

bool isRectangleOverlap(int* rec1, int rec1Size, int* rec2, int rec2Size) {
    int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3];
    int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3];
    return !(x1 >= x4 || x2 <= x3 || y1 >= y4 || y2 <= y3);
}

ZeroJudge 解題筆記：g424.PF.抱ㄌㄌ

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


ZeroJudge 題目連結：g424.PF.抱ㄌㄌ

解題想法

出題者原來的敘述可能會引起一些問題，我稍微修改一下。假設一列石頭共有 $n$ 顆，長度為 $n$ 的陣列 $nums$ 代表這列石頭的分數，可以從左到右取依序拿走石頭，最多一次只能連續拿 $k$ 顆石頭，求最大總分為何？

這題雖然被分類在基礎題庫，但其實一點也不像基礎題。這題如果按照題目的要求很難寫程式，反過來思考會比較好寫。最多一次只能連續拿 $k$ 顆石頭，相當於在長度為 $k+1$ 的範圍內至少要捨棄 $1$ 個石頭，因此題目所求等於所有的石頭總分 - 捨棄的石頭最低總分，看出這點之後用動態規畫解題。為了便於結算最後一顆石頭的狀態，可以在 $nums$ 最後面再加一個 $0$。開一個長度為 $n+1$ 的陣列 $dp$，$dp[i]$ 代表在捨棄 $nums[i]$ 的狀況下，所有捨棄的石頭最低總分，有 $2$ 種狀況：

1. $i \leq k$，沒有更前面的石頭被捨棄，只要捨棄第 $i$ 顆石頭，$dp[i] = nums[i]$。
2. $i > k$，從第 $i-1-k$ 到 $i-1$ 顆石頭之中捨棄一顆，並且捨棄第 $i$ 顆石頭，$dp[i] = \min_{i-1-k \leq j \leq} dp[j] + nums[i]$。

如果在更新 $dp$ 時每次都要找 $dp[i-1-k]$ 到 $dp[i-1]$ 之間的最小值，這樣速度會太慢，可以利用滑動視窗及單調隊列加速。開一個雙向佇列 $que$，儲存寬度為 $k+1$ 的視窗範圍內 $dp$ 值最小的索引值，保持隊列為嚴格遞增，則視窗範圍內 $dp$ 最小值對應的索引值一定會在 $que$ 的最前面。更新 $que$ 時要依照以下的順序：

1. 移除 $que$ 前端已經出界的項目，也就是索引值小於 $i-1-k$ 的項目。
2. 更新 $dp$，如果 $i \leq k$ 則 $dp[i] = nums[i]$；反之，$dp[i] = nums[i] + dp[que[0]]$。
3. 移除 $que$ 後端大於、等於 $dp[i]$ 的項目。
4. $i$ 加入 $que$ 後端

Python 程式碼

解題時間約為 88 ms，使用記憶體約為 24.7 MB。

def solve():
    import sys
    from collections import deque
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield int(part)
    
    tokens = get_tokens()
    
    while True:
        try:
            n = next(tokens)
            k = next(tokens)
        except StopIteration:
            break
        
        nums = [next(tokens) for _ in range(n)] + [0]
        total = 0
        dp = [0] * (n+1)
        que = deque()
        for i in range(n+1):
            total += nums[i]
            # 移除前端出界的項目
            while que and que[0] < i-k-1:
                que.popleft()
            # 更新 dp[i]
            if i <= k:
                dp[i] = nums[i]
            else:
                dp[i] = nums[i] + dp[que[0]]
            # 移除後端較大的項目
            while que and dp[que[-1]] >= dp[i]:
                que.pop()
            # i 加入 que
            que.append(i)
        sys.stdout.write(f"{total - dp[-1]:d}\n")

if __name__ == "__main__":
    solve()