LeetCode 解題筆記：3619. Count Islands With Total Value Divisible by K

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


LeetCode 題目連結：3619. Count Islands With Total Value Divisible by K

解題想法

中等難度題。題目給一個二維陣列 $grid$，其中正整數代表陸地，0 代表海洋，地圖邊緣視為海洋。陸地可以與右、下、左、上相鄰的陸地相連，如果周圍被海洋環繞一圈，這片相連的陸地是一座島嶼。計算 $grid$ 之中有幾座島嶼的數值加總可以被 $k$ 整除。

這題是標準的 BFS。用雙層 for 迴圈掃過 $grid$ 每一格，如果遇到正整，從這格開始 BFS 計算加總 $val$，計算的過程中同時對 $k$ 取餘數。將走過的陸地都標示為 0，直接修改 $grid$ 的內容即可，節省記憶體。BFS 結束之後，如果 $val$ 等於 0，答案 $ans$ 加 1。

Python 程式碼

Runtime: 270 ms, beats 90.00%. Memory: 30.06 MB, beats 93.79%.

class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        m, n, ans = len(grid), len(grid[0]), 0  # 地圖 m*n，答案
        # 掃過每一格，如果這格不等於 0，BFS 走完相連的格子
        for i in range(m):
            for j in range(n):
                if grid[i][j] != 0:
                    val = grid[i][j] % k
                    que = deque([(i, j)])
                    grid[i][j] = 0
                    while que:
                        r, c = que.popleft()
                        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                            nr, nc = r + dr, c + dc
                            if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != 0:
                                val = (val + grid[nr][nc]) % k
                                grid[nr][nc] = 0
                                que.append((nr, nc))
                    
                    if val == 0: ans += 1  # 符合條件，答案加 1

        return ans

ZeroJudge 解題筆記：p923.湯圓 (Tangyuan)

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


ZeroJudge 題目連結：p923.湯圓 (Tangyuan)

題目 pdf 檔連結：湯圓 (Tangyuan)

解題想法

每組測資第一列為一個整數 $n$，代表共有 $n$ 個人；接下來 $n$ 列每列有 $2$ 個數字 $x, y$，分別代表這個人想吃的芝麻和花生湯圓數量。如果湯圓一盒 $10$ 顆，兩種口味的湯圓至少要各買幾盒？各會剩下幾顆？這題可以用兩個變數 $sesame, peanut$，分別代表芝麻、花生湯圓的數量。用一個 for 迴圈讀取每個人要吃的數量並更新 $sesame, peanut$。盒數為數量對 $10$ 取整數除法，如果有餘數再加 $1$ 盒。剩下的數量可以用 $盒數 \times 10 - 要吃的數量$。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 讀取測資
        n = int(data[ptr])
        ptr += 1
        sesame, peanut = 0, 0  # 芝麻、花生湯圓數量
        for _ in range(n):
            x = int(data[ptr])
            y = int(data[ptr + 1])
            ptr += 2
            sesame += x
            peanut += y
        
        rem1 = sesame % 10
        num1 = sesame // 10 + (rem1 > 0)
        rem2 = peanut % 10
        num2 = peanut // 10 + (rem2 > 0)
        result.append(f"{num1:d} {10 * num1 - sesame:d}\n{num2:d} {10 * num2 - peanut:d}\n")
    
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：p922.選舉 (Election)

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


LeetCode 題目連結：3619. Count Islands With Total Value Divisible by K

解題想法

中等難度題。題目給一個二維陣列 $grid$，其中正整數代表陸地，0 代表海洋，地圖邊緣視為海洋。陸地可以與右、下、左、上相鄰的陸地相連，如果周圍被海洋環繞一圈，這片相連的陸地是一座島嶼。計算 $grid$ 之中有幾座島嶼的數值加總可以被 $k$ 整除。

這題是標準的 BFS。用雙層 for 迴圈掃過 $grid$ 每一格，如果遇到正整，從這格開始 BFS 計算加總 $val$，計算的過程中同時對 $k$ 取餘數。將走過的陸地都標示為 0，直接修改 $grid$ 的內容即可，節省記憶體。BFS 結束之後，如果 $val$ 等於 0，答案 $ans$ 加 1。

Python 程式碼

Runtime: 270 ms, beats 90.00%. Memory: 30.06 MB, beats 93.79%.

class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        m, n, ans = len(grid), len(grid[0]), 0  # 地圖 m*n，答案
        # 掃過每一格，如果這格不等於 0，BFS 走完相連的格子
        for i in range(m):
            for j in range(n):
                if grid[i][j] != 0:
                    val = grid[i][j] % k
                    que = deque([(i, j)])
                    grid[i][j] = 0
                    while que:
                        r, c = que.popleft()
                        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                            nr, nc = r + dr, c + dc
                            if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != 0:
                                val = (val + grid[nr][nc]) % k
                                grid[nr][nc] = 0
                                que.append((nr, nc))
                    
                    if val == 0: ans += 1  # 符合條件，答案加 1

        return ans

LeetCode 解題筆記：1254. Number of Closed Islands

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


LeetCode 題目連結：1254. Number of Closed Islands

解題想法

中等難度題。題目給一個二維陣列 $grid$，其中 0 代表陸地，1 代表海洋。陸地可以與右、下、左、上相鄰的陸地相連，如果周圍被海洋環繞一圈，這片相連的陸地是一座島嶼。計算 $grid$ 之中有幾座島嶼。

這題是標準的 BFS。用雙層 for 迴圈掃過 $grid$ 每一格，如果遇到 0，可能是島嶼，用 is_island 標記是否為島嶼，預設為 True。接下來從這格開始 BFS，將走過的陸地都標示為 2，直接修改 $grid$ 的內容即可，節省記憶體。如果走的過程中出界，不是島嶼，is_land 改成 False。BFS 結束之後，如果 is_land 為 True，答案 $cnt + 1$。

Python 程式碼

Runtime: 12 ms, beats 87.91%. Memory: 19.76 MB, beats 75.00%.

from collections import deque

class Solution:
    def closedIsland(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])   # 地圖尺寸 m*n     
        cnt = 0  # 島嶼數量

        # 掃過 grid 每一格，遇到 0 用 BFS 走完相連的 0，走過的格子標記成 2
        # 如果過程中會出界，不是島嶼
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    is_island = True
                    que = deque([(i, j)])
                    grid[i][j] = 2
                    while que:
                        r, c = que.popleft()
                        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                            nr, nc = r + dr, c + dc
                            if nr < 0 or nr >= m or nc < 0 or nc >= n:
                                is_island = False
                            elif grid[nr][nc] == 0:
                                que.append((nr, nc))
                                grid[nr][nc] = 2
                    if is_island: cnt += 1
        return cnt

LeetCode 解題筆記：2409. Count Days Spent Together

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


LeetCode 題目連結：2409. Count Days Spent Together

解題想法

簡單題。題目給 4 個長度皆為 5 的字串，格式為 MM-DD，MM 代表月，DD 代表日。4 個字串分別是代表 Alice 抵達的日期 arriveAlice，Alice 離開的日期 leaveAlice，Bob 抵達的日期 arriveBob，Bob 離開的日期 leaveBob。計算 Alice 與 Bob 一起待在羅馬的天數。假設是平年，2 月只有 28 天。

由於日期格式很困定，可以用 Python 的字串切片或是 C++ 的 substr，將字串中的月、日分開，轉成整數。如果用 C 語言比較麻煩，我是用索引值取出字元再減去 '0' 換成對應的整數，每個位數都要分開算。在計算天數時，我將日期全部轉成由1月1日開始的累計天數。為了計算月份對應的天數，我開一個長度為 13 的陣列 $month = (0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365)$，記錄經過完整的月份時共經過幾天。答案為兩個人離開日期最小值 - 兩個人離開日期最大值，如果答案是負的則回傳 0。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.29 MB, beats 79.30%.

class Solution:
    def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
        month = (0, 31, 59, 90, 120, 151, 181,
                 212, 243, 273, 304, 334, 365)
        arriveAliceDays = month[int(arriveAlice[:2]) - 1] + int(arriveAlice[3:])
        leaveAliceDays = month[int(leaveAlice[:2]) - 1] + int(leaveAlice[3:])
        arriveBobDays = month[int(arriveBob[:2]) - 1] + int(arriveBob[3:])
        leaveBobDays = month[int(leaveBob[:2]) - 1] + int(leaveBob[3:])
        ans = min(leaveAliceDays, leaveBobDays) - max(arriveAliceDays, arriveBobDays) + 1
        return ans if ans > 0 else 0

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.05 MB, beats 38.18%.

class Solution {
public:
    int countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {
        int month[13] = 
            {0, 31, 59, 90, 120, 151, 181,
             212, 243, 273, 304, 334, 365};
        int arriveAliceDays = month[stoi(arriveAlice.substr(0, 2)) - 1] + stoi(arriveAlice.substr(3));
        int leaveAliceDays = month[stoi(leaveAlice.substr(0, 2)) - 1] + stoi(leaveAlice.substr(3));
        int arriveBobDays = month[stoi(arriveBob.substr(0, 2)) - 1] + stoi(arriveBob.substr(3));
        int leaveBobDays = month[stoi(leaveBob.substr(0, 2)) - 1] + stoi(leaveBob.substr(3));
        int ans = min(leaveAliceDays, leaveBobDays) - max(arriveAliceDays, arriveBobDays) + 1;
        return (ans > 0 ? ans : 0);
    }
};

ZeroJudge 解題筆記：p921.紅包 (Red Envelope)

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


ZeroJudge 題目連結：p921.紅包 (Red Envelope)

題目 pdf 檔連結：紅包 (Red Envelope)

解題想法

每組測資第一列為一個整數 $n$，代表共有 $n$ 個紅包；接下來 $n$ 列每列有 $3$ 個數字，分別代表 100、500 和 1000 元的鈔票數量；計算這 $n$ 個紅包的總金額。這題可以用 $3$ 個變數或是一個長度 $3$ 的陣列記錄 $3$ 種鈔票的數量，最後再印出數量乘以面額的加總。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        cnt = [0, 0, 0]# 100, 500, 1000 總張數
        for _ in range(n):
            a, b, c = map(int, data[ptr : ptr + 3])  # 100, 500, 1000 張數
            ptr += 3
            cnt[0] += a
            cnt[1] += b
            cnt[2] += c
        result.append(f"{cnt[0] * 100 + cnt[1] * 500 + cnt[2] * 1000:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：p920.塗鴉連線 (Doodle)

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


ZeroJudge 題目連結：p920.塗鴉連線 (Doodle)

題目 pdf 檔連結：塗鴉連線 (Doodle)

解題想法

每組測資第一列為兩個整數 $m$、$n$，代表地圖尺寸為 $m \times n$，接下來 $m$ 列每列有 $n$ 個數字，$1$ 代表這格有塗黑，$0$ 代表這格沒有塗黑。起點為左上角 $(0, 0)$，終點為右下角 $(m-1, n-1)$，這兩格都是 $1$，而且只與另一格 $1$ 相鄰；起點、終點路徑上其它的 $1$ 則會與另外 $2$ 格 $1$ 相鄰。計算從起點到終點移動的格子數量。

我習慣用 BFS 處理這類型走格子的題目，但是這題並不需要用到 BFS，因為起點、終點路徑上其它的 $1$ 則會與另外 $2$ 格 $1$ 相鄰，假設已經走過的格子被標記為 $0$，用四方位檢查找出與這格相鄰的 $1$ 時只會找到 $1$ 格，只要找到這格就可以再往下走。

Python 程式碼

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

def solve():
    import sys
    from collections import deque

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 讀取測資
        m = int(data[ptr])
        n = int(data[ptr + 1])
        ptr += 2
        grid = []
        for _ in range(m):
            row = list(map(int, data[ptr : ptr + n]))
            ptr += n
            grid.append(row)
        
        # 用 BFS 找步數
        que = deque([(0, 0, 1)])  # 起點 (0, 0)，步數 1
        grid[0][0] = 0  # 改成 0，標記為已走過
        while que:
            r, c, s = que.popleft()
            if r == m - 1 and c == n - 1:  # 走到終點
                result.append(f"{s:d}\n")
                break
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                    grid[nr][nc] = 0
                    que.append((nr, nc, s + 1))
    # 一次輸出所有答案
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3644. Maximum K to Sort a Permutation

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


LeetCode 題目連結：3644. Maximum K to Sort a Permutation

解題想法

中等難度題。題目給一個長度為 $n ~(1 \leq n \leq 10^5)$ 、數字不重複的整數陣列 $nums ~(0 \leq nums[i] \leq n-1)$。如果 $nums[i] ~\text{&}~ nums[j] = k, i \leq j$，可以交換 $nums[i], nums[j]$，交換次數不限。如果可以用這樣的交換方式使 $nums$ 變為由小到大排序，則最大的 $k$ 值為何？

這題考位元運算，困難之處在於如何找到並證明答案。先將答案 $ans$ 設定為所有位元都是 $1$ 的數字，例如 $2^30 - 1$ 或 $-1$。用一個 for 迴圈掃過 $nums$，如果 $nums[i] \neq i$，代表這個數字需要被交換，更新 $ans ~\text{&}= i$，同時設定排序狀態 is_sorted 為 False。檢查完所有的數字之後，如果 is_sorted 為 True 回傳 $0$，反之回傳 $ans$。

因為位元運算 & 的特性，將 $nums$ 之中任意兩個數字取 & 只會越取越小，答案一定小於 $n$。如果將 $ans$ 與所有需要歸位的數字取 & 之後，$ans$ 的值一定等於 $nums$ 之中的某一個數字，先假設這個數字為 $m$。如果要讓另外兩個數字 $a, b$ 歸位，可以先交換 $a, m$，再交換 $b, m$，最後交換 $a, m$，就可以 $a, b$ 的位置互換，$m$ 最後又回到原來的位置。重複以上的過程就能讓所有的數字歸位。

Python 程式碼

Runtime: 31 ms, beats 63.74%. Memory: 31.90 MB, beats 73.63%.

class Solution:
    def sortPermutation(self, nums: List[int]) -> int:
        is_sorted = True  # 是否已排序
        ans = (1 << 30) - 1  # 答案，先預設成所有位元都是 1 的數字
        for i, num in enumerate(nums):  # 掃過每一個數字
            if i != num:  # 不在正確位置的數字
                is_sorted = False
                ans &= i
        return 0 if is_sorted else ans

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 152.81 MB, beats 21.90%.

class Solution {
public:
    int sortPermutation(vector<int>& nums) {
        bool is_sorted = true;  // 是否已排序
        int ans = (1 << 30) - 1, n = (int)nums.size();  // 答案，先預設成所有位元都是 1 的數字；長度
        for(int i = 0; i < n; i++) {  // 掃過每一個數字
            if (i != nums[i]) {  // 不在正確位置的數字
                is_sorted = false;
                ans &= i;
            }
        }
        return (is_sorted ? 0 : ans);
    }
};

LeetCode 解題筆記：823. Binary Trees With Factors

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


LeetCode 題目連結：823. Binary Trees With Factors

解題想法

中等難度題。題目給一個長度為 $n ~(1 \leq n \leq 1000)$ 、數字不重複的整數陣列 $arr ~(2 \leq arr[i] \leq 10^9)$，用這些整數組成二元樹，且除了葉節點之外，其它節點的值必須等於其子節點值的乘積，計算共有幾種排列方式。由於答案很大，將排列方式對 $10^9 + 7$ 取餘數。

這題考動態規畫。先將 $arr$ 由小到大排序，因為計算特定乘積的排列方式數量時，需要用到較小乘積的排列方式數量。接下來用字典 $dp$ 記錄乘積 $v$ 當作根節點有幾種二元樹排列方式，由於更新數值時需要將兩個因數對應的值相乘，可能會超出 int 的上限，用 long 儲存會比較安全。用一個 for 迴圈跑 $arr[0]$ ~ $arr[n-1]$，先設定 $dp[arr[i]] = 1$，代表只有根節點時方法數為 $1$；再用一個 for 迴圈跑 $arr[0]$ 到 $arr[i-1]$，如果 $arr[j]$ 是 $arr[i]$ 的因數，則 $dp[arr[i]]$ 的方法數要再加上兩個因數的方法數乘積，同時對 $10^9 + 7$ 取餘數。每次計算完 $dp[arr[i]]$ 時立刻更新答案 $ans$。這個寫法的效率不算很好，但是比較容易理解。

Python 程式碼

Runtime: 229 ms, beats 16.59%. Memory: 20.68 MB, beats 5.68%.

class Solution:
    def numFactoredBinaryTrees(self, arr: list[int]) -> int:
        mod = 10**9 + 7
        n = len(arr)  # 長度
        arr.sort()  # 由小到大排序
        ans = 0  # 答案
        dp = defaultdict(int)  # 數字 v 當作根節點有幾種二元樹組合

        for i in range(n):  # 跑 arr[0] ~ arr[n-1]
            dp[arr[i]] = 1  # 以 arr[i] 當作根節點且樹只有根節點，1 種組合
            for j in range(i):  # 找出 arr[i] 的因數
                if arr[i] % arr[j] == 0:  # arr[j] 是因數
                    dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[arr[i] // arr[j]]) % mod  # 加上兩個因數組合數的乘積
            ans = (ans + dp[arr[i]]) % mod  # 更新答案
        return ans

ZeroJudge 解題筆記：p919.社團 (Club)

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


ZeroJudge 題目連結：p919.社團 (Club)

解題想法

每組測資第一列為兩個整數 $n$、$m$，分別代表有 $n$ 個人、$m$ 個社團。接下來 $m$ 列，每列一個字串，代表社團的名稱。最後 $n$ 列，每列有 $3$ 個用空格分隔的字串，代表這個人選擇的 $3$ 個社團名稱，社團名稱可能重複，如果重複只會算 $1$ 個人次。題目要統計每個社團各有幾個人填入選社志願。答案要輸出 $m$ 列，按照測資給的社團名稱輸出，每列為社團名稱、人數，中間用空格分隔。

這個題目很適合用字典計數，可以用 Python 的 dict 或是 defaultdict 以及 C++ 的 map 或是 unordered_map 處理。不過用 C++ 解題時，需要再另外開一個 vector 記錄社團名稱順序，用來組合輸出的答案。

由於這題原來只放了無法開啟的題目 pdf 雲端硬碟連結，我一開始無法確定每個人可選的社團數量，所有我有寫另一種可選社團數量不固定的版本，一樣可以 AC，但是寫起來比較複雜。

Python 程式碼

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

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # n 個人
        m = int(data[ptr + 1])  # m 個社團
        ptr += 2
        
        # 用字典儲存各社團人數，先設定 key 值
        cnt = dict()
        for _ in range(m):
            s = data[ptr]
            ptr += 1
            cnt[s] = 0

        # 讀取 n 個人選擇的社團
        for _ in range(n):
            clubs = set(data[ptr : ptr + 3])  # 去除重複的項目
            ptr += 3
            for club in clubs:
                cnt[club] += 1

        # 組合答案
        for k, v in cnt.items():
            result.append(f"{k} {v:d}\n")
    
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()