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()

LeetCode 解題筆記：835. Image Overlap

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


LeetCode 題目連結：835. Image Overlap

解題想法

中等難度題，題目給兩個大小皆為 $n \times n$ 的二維陣列 $img1, img2$，陣列之中只有 $0$ 或　$1$，可以將 $img1$ 往上、下、左、右平移，刪除出界的部分，將兩個陣列重疊，計算兩個陣列中有幾個 $1$ 重疊，回傳最大的數量。

可以先用兩層 for 迴圈掃過 $img1, img2$，將陣列中 $1$ 的位置分別存到陣列 $pos1, pos2$ 之中。再開一個字典，以坐標平移量 $dr, dc$ 為 key，計算各種位移量下重疊的 $1$ 有幾個，同時更新答案 $ans$。

Python 程式碼

Runtime: 259 ms, beats 48.41%. Memory: 19.95 MB, beats 14.29%.

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        # 記錄影像 1、2 之中 1 的位置
        n = len(img1)
        pos1, pos2 = [], []
        for r in range(n):
            for c in range(n):
                if img1[r][c] == 1:
                    pos1.append((r, c))
                if img2[r][c] == 1:
                    pos2.append((r, c))
        # 計算所有平移量 (dr, dc) 影像中 1 重疊的數量
        ans = 0  # 答案，預設為 0
        cnt = defaultdict(int)  # (dr, dc): ones
        for r1, c1 in pos1:
            for r2, c2 in pos2:
                dr, dc = r1 - r2, c1 - c2
                cnt[dr, dc] += 1
                if cnt[dr, dc] > ans:
                    ans = cnt[dr, dc]
        return ans

ZeroJudge 解題筆記：e417.乘法~乘法~加法~

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


ZeroJudge 題目連結：e417.乘法~乘法~加法~

解題想法

題目是多筆測資。每組測資有 $2$ 列，第 $1$ 列給一個整數 $n$，第 $2$ 列給 $n$ 個整數 $x_1, x_2, x_3, \dots, x_n$，題目要求 $x_1 x_2 + x_1 x_3 + x_1 x_4 \dots + x_{n-2} x_n + x_{n-1} x_n$，保設答案可以用 unsigned long long 格式儲存。這一題如果用迴圈硬算會超時，需要利用一個數學性質，假設要計算的數字為 $a, b, c, d$，則 $$ \begin{align*} (a + b + c + d)^2 &= a^2 + ab + ac + ad + b^2 + ba + bc + bd +\\ &+ c^2 + ca + cb + cd + d^2 + da + db + dc\\ &= a^2 + b^2 + c^2 + d^2 + 2(ab + ac + ad + bc + bd + cd)\\ \end{align*} $$ $$ ab + ac + ad + bc + bd + cd = \frac{(a + b + c + d)^2 - (a^2 + b^2 + c^2 + d^2)}{2} $$ 雖然題目給的記憶體很大，但是用 Python 解題時，不能用 sys.stdin.read().split() 一次讀取並分割所有的測資，這樣會超出記憶體上限。要改用生成器，一次轉換一個數字。

Python 程式碼

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

def solve():
    import sys
    
    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)
        except StopIteration:
            break
        
        square = 0  # 平方項的和
        total = 0  # 數字加總
        for _ in range(n):
            x = next(tokens)
            square += x*x
            total += x
        ans = (total * total - square) // 2
        sys.stdout.write(f"{ans:d}\n")

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：r580.10432 - Polygon Inside A Circle

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


ZeroJudge 題目連結：r580.10432 - Polygon Inside A Circle

解題想法

題目有多筆測資。每一列有 2 個數字，分別代表半徑 $r$，於圓內畫出正 $n$ 邊形，題目要回傳這個正 $n$ 邊形的面積。這題考數學，可以將正 $n$ 邊形以圓心為頂點，分割成 $n$ 個等腰三角形，等長的兩個邊之間的夾角為 $\theta = 2 \pi / n$，三角形面積為 $$ a = \frac{1}{2} r^2 \sin \theta $$ 因此正 $n$ 邊形面積為 $area = a \times n$。

Python 程式碼

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

def solve():
    import sys, math
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield float(part)

    tokens = get_tokens()

    while True:
        try:
            r = next(tokens)
            n = next(tokens)
        except StopIteration:
            break
        
        theta = 2.0 * math.pi / n
        area = 0.5 * r * r * math.sin(theta) * n
        sys.stdout.write(f"{area:.3f}\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：729. My Calendar I

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


LeetCode 題目連結：729. My Calendar I

解題想法

中等難度題，題目給一個 class 部分的程式碼，及一個包含行程開始、結束時間的串列，要求我們完成 class 之中的函式 book，於函式中先檢查這個行程是否與原有行程時間重複，如果重複回傳 False；如果不重複，更新資料並回傳 True。

由於這題的測資不多，可以用一層 for 迴圈逐一檢查新的時間 $startTime$ 及 $endTime$ 是否與原有行程重疊。如果想要再更快速一點，可以用字典儲存每一個排入的行程開始時刻及對應的結束時刻，再用另一個陣列 $starts$ 儲存行程開始時間，並用二分搜尋法找新的時間 $startTime$ 於 $starts$ 之中插入的索引值，檢查 $startTime$ 及 $endTime$ 是否與前、後的行程重疊。

Python 程式碼

Runtime: 179 ms, beats 50.25%. Memory: 20.30 MB, beats 24.38%.

class MyCalendar:
    def __init__(self):
        self.intervals = []  # (start, end)

    def book(self, startTime: int, endTime: int) -> bool:
        # 逐一檢查時間時否重疊
        for s, e in self.intervals:
            if startTime < e and endTime > s:
                return False
        self.intervals.append((startTime, endTime))
        return True


# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(startTime,endTime)

Runtime: 19 ms, beats 98.17%. Memory: 20.17 MB, beats 58.06%.

from bisect import bisect_right

class MyCalendar:
    def __init__(self):
        self.intervals = dict()  # start: end
        self.starts = []

    def book(self, startTime: int, endTime: int) -> bool:
        # 用二分搜尋法找 starts 之中插入 startTime 的右側位置
        idx = bisect_left(self.starts, startTime)
        # 前面有別的行程，檢查時間是否重疊
        if idx > 0:
            prev_end = self.intervals[self.starts[idx - 1]]
            if startTime < prev_end:
                return False
        # 後面有別的行程，檢查時間是否重疊
        if idx < len(self.starts):
            next_start = self.starts[idx]
            if endTime > next_start:
                return False
        # 於 starts 之中插入新資料並保持排序
        self.intervals[startTime] = endTime
        self.starts.insert(idx, startTime)
        return True


# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(startTime,endTime)

LeetCode 解題筆記：3483. Unique 3-Digit Even Numbers

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


LeetCode 題目連結：3483. Unique 3-Digit Even Numbers

解題想法

簡單題，題目給一個包含正整數或零的陣列 $digits$，從 $digits$ 之中取出 $3$ 個數字組合成沒有前導零 $3$ 位數的偶數，回傳這樣的數總共有幾種組合。這是我一開始的寫法是用三層 for 迴圈從 $digits$ 之中取數字，最外層的 for 迴圈跑第一位 $x$，如果取出的數字為 $0$ 就跳過；第二層的 for 迴圈跑第二位 $y$，這個位數沒有限制；最內層的 for 迴圈跑第三位 $z$，這個位數只能是偶數。將 $100 x + 10 y + z$ 存入集合 $ans$ 之中，答案為 $ans$ 的長度。因為題目只有 $3$ 位數，這個寫法的速度還算快。

另一個寫法是用三層 for 迴圈枚舉所有的 $3$ 位數偶數，計算這個偶數需要的數字數量，如果 $digits$ 之中可以提併足夠的數字，就將答案 $ans$ 數量加 1。

Python 程式碼

使用集合。Runtime: 15 ms, beats 69.45%. Memory: 19.21 MB, beats 72.53%.

class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        n = len(digits)
        ans = set()
        for i in range(n):
            x = digits[i]
            if x == 0: continue
            for j in range(n):
                if i == j: continue
                y = digits[j]
                for k in range(n):
                    if k == i or k == j: continue
                    z = digits[k]
                    if z % 2 == 0:
                        ans.add(x*100 + y*10 + z)
        return len(ans)

字典計數。Runtime: 412 ms, beats 7.47%. Memory: 19.28 MB, beats 72.53%.

class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        cnt = Counter(digits)  # 各種數字的數量
        ans = 0  # 答案
        # 枚舉所有不含前導 0、3 位數的偶數
        for i in range(1, 10):  # 1 ~ 9
            for j in range(10):  # 0 ~ 9
                for k in range(0, 10, 2):  # 2, 4, 6, 8
                    need = Counter([i, j, k])  # 需要的數字數量
                    # digits 之中有足夠的數字，答案加 1
                    if need[i] <= cnt[i] and need[j] <= cnt[j] and need[k] <= cnt[k]:
                        ans += 1
        return ans

ZeroJudge 解題筆記：r581.10489 - Boxes of Chocolates

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


ZeroJudge 題目連結：r581.10489 - Boxes of Chocolates

解題想法

每筆測資第 $1$ 列只有一個整數 $T$，代表接下來有 $T$ 組測資。第 $2$ 列有兩個整數 $n, b$，分別代表朋友人數、收到的禮物盒數量。接下來 $b$ 列，每列開頭有 $1$ 個數字代表這列的後方有幾個數字，第 $1$ 到倒數第 $2$ 個數字為每一層盒子的數量，最後一個數字為最內層盒子內的巧克力數量。先計算拿到的巧克力總數 $total$，輸出 $total$ 除以 $n$ 的餘數。為了計算每一個盒子內的巧克力數量，可以先設定變數 $t = 1$，接下來依序讀取每層的盒子數量及最內層盒子內的巧克力數量，將 $t$ 乘上這些數字就是這個盒子內的巧克力總數。最後再將所有盒子的巧克力數量相加，對 $n$ 取餘數就是答案。

用 C 或 C++ 解題要很小心，計算盒子內巧克力數量時，每次相加或相乘都要對 $n$ 取餘數，否則數值會超出 int 的上限。

Python 程式碼

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

T = int(input())
for _ in range(T):
    n, b = map(int, input().split())
    total = 0
    for __ in range(b):
        parts = list(map(int, input().split()))
        m = parts[0]
        t = 1
        for i in range(1, m + 1):
            t *= parts[i]
        total += t
    print(total % n)