LeetCode 解題筆記：695. Max Area of Island

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


LeetCode 題目連結：695. Max Area of Island

解題想法

中等難度題。題目給一個 $m \times n$ 的二維陣列 $grid$，其中只有代表陸地的 $1$ 以及代表水域的 $0$，並且假設 $grid$ 四周都是 $0$。陸地可以往右、下、左、上等四個方向連接。要找出 $grid$ 之中面積最大的島嶼，也就是由最多的 $1$ 組成的連通區塊。連通區塊的題目，用 BFS 或 DFS 都可以解，由於我是以 Python 為主要的解題語言，我比較習慣用 BFS，如果用 DFS 經常會遇到遞迴深度過深的問題。這題我兩個方法都有寫，如果用 Python 解題 BFS 跑比較快，如果用 C++ 解題 DFS 跑比較快。

Python 程式碼

BFS. Runtime: 11 ms, beats 96.45%. Memory: 19.38 MB, beats 94.88%.

from collections import deque

class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        m, n, imax = len(grid), len(grid[0]), 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    continue
                grid[i][j] = 0
                area = 1
                que = deque([(i, j)])
                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] == 1:
                            grid[nr][nc] = 0
                            area += 1
                            que.append((nr, nc))
                imax = max(imax, area)
        return imax

DFS. Runtime: 17 ms, beats 67.40%. Memory: 20.39 MB, beats 64.21%.

class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        m, n, imax = len(grid), len(grid[0]), 0
        area = 0
        
        # 自訂 dfs 函式，找連通區塊面積同時將走過的格子標記為 0
        def dfs(r, c):
            nonlocal area
            area += 1
            grid[r][c] = 0
            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:
                    dfs(nr, nc)
        
        # 掃過每一格，跳過 0，遇到 1 呼叫 dfs
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    continue
                # area 歸零之後再呼叫 dfs 找連通區塊面積
                area = 0
                dfs(i, j)
                imax = max(imax, area)
        return imax

ZeroJudge 解題筆記：o626.檔案順序 (Files)

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


ZeroJudge 題目連結：o626.檔案順序 (Files)

題目 pdf 檔連結：檔案順序 (Files)

解題想法

這題是TOI練習賽202409潛力組第1題，這題跟同組題目的第2題〈o627.校外教學分組 (Trip)〉都很難，第3題〈o628.天秤 (Libra)〉比較簡單。題目是多組測資。每組測資第1列為2個整數 $n (1 \leq n \leq 2 \times 10^5)$、$k (1 \leq k \leq 2 \times 10^5)$，分別代表有 $n$ 個檔案、$k$ 次操作。接下來 $n$ 列，每列有 4 個整數，分別代表檔案的名稱、修改時間、類型、大小。最後一列有 $k$ 個 1 到 4 的數字，分別代表用檔案的名稱、修改時間、類型、大小作為排序依據。如果有多個檔案這個屬性的值相同，則這幾個檔案保持前一次排序後的順序，也就是用 stable sort。

如果前一次操作與這次操作用的屬性不同，則這次操作為升序排序 （ascending order)，也就是由小到大排序；如果重複點同樣的屬性第二次，會改成降序排序 （descending order)，也就是由大到小排序。這點在解題時特別重要，因為 $n, k$ 的數值極大，如果真的模擬每一次的排序過程絕對會超時。但由於這個操作上的特性，我們可以用一個串列 $ops$ 記錄操作的索引值 $idx$ 以及目前為升序 (1) 或降序 (-1) 排列，如果連續使用相同的屬性排序，只要更新升序或降序即可；如果用不同屬性排序，於 $ops$ 最後面接上 $[idx, 1]$。

另一個要利用的特性是操作過程中如果先用了某個屬性排序，再用另一個屬性排序，之後再回來用前面用過的屬性排序，只有最後面這次的排序有效。例如先用名稱，再用修改時間，之後再回來用名稱排序，則第一次排序的效果會被後面同樣用名稱排序的效果蓋掉。因此，我們可以倒序讀取 $ops$，取出用這 4 個屬性排序的索引值及升序、降序，資料存入串列 sort_key。將 sort_key 組成 tuple，只排序一次，將排序後的檔案依序輸出。

不過這題的記憶體限制極小，只有 64 MB，我用 Python 解題最多只能通過 50% 的測資就遇到 MemoryError，目前看排行還沒有人用 Python 過關。用 C++ 則是 0.2 s、9.4 MB 過關。

Python 程式碼

只能通過 40% 的測資。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        k = int(data[ptr + 1])
        ptr += 2
        files = []  # (name, time, type, size)
        for _ in range(n):
            file = tuple(map(int, data[ptr : ptr + 4]))
            ptr += 4
            files.append(file)
        
        operations = []  # idx of operation
        state = [0] * 5  # 1 ascending, -1 descending, 0 none
        for _ in range(k):
            idx = int(data[ptr])
            ptr += 1
            operations.append(idx)
            if state[idx] == 0:
                state[idx] = 1
            else:
                state[idx] *= -1
        
        sort_key = []  # (idx, 1 or -1)
        used = [False] * 5
        for idx in operations[::-1]:
            if not used[idx]:
                used[idx] = True
                sort_key.append((idx, state[idx]))
        
        def mykey(file):
            return tuple(file[idx - 1] * val for idx, val in sort_key)
        
        files.sort(key = mykey)
        
        for file in files:
            res = " ".join(map(str, file)) + "\n"
            result.append(res)
        
    # 輸出答案
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：h192.黏包、分包

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


ZeroJudge 題目連結：h192.黏包、分包

解題想法

基礎題庫裡面新出現的字串處理題。每組測資是多行輸入，要先將所有的測資接成一個很長的字串 $s$。假設 $s$ 長度為 $n$，用一個 while 迴圈從 $i = 0$ 開始依序讀取字元，分成以下 2 種狀況：

1. 如果 $s[i]$ 不是 :，代表目前讀到的是代表長度的數字，將 $s[i]$ 暫存到字串 $u$。
2. 如果 $s[i]$ 是 :，將 $u$ 轉成整數 $d$，結算長度為 $d$ 的子字串，可以用 Python 的字串切片或是 C++ 的 substr，從 $s[i+1]$ 開始取子字串，組合成題目規定的輸出格式，輸出完畢後重置字串 $u$ 並將 $i += d$。

每次執行完 while 迴圈記得要 $i += 1$，否則會變成無窮迴圈。

Python 程式碼

解題時間約為 12 ms，使用記憶體約為 9.6 B。

def solve():
    import sys
    
    result = []
    # 讀取多行測資，全部接成一行
    s = "".join(sys.stdin.read().split())
    
    # 依序讀取字元暫存至字串 u，讀到 : 輸出長度 u 的子字串
    i, n = 0, len(s)
    u = ""
    while i < n:
        if s[i] == ':':
            d = int(u)
            result.append(f"{u}:{s[i+1 : i+d+1]}\n")
            i += d
            u = ""
        else:
            u += s[i]
        i += 1
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：2913. Subarrays Distinct Element Sum of Squares I

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


LeetCode 題目連結：2913. Subarrays Distinct Element Sum of Squares I

解題想法

簡單題。題目給一個長度 $n = 1$ 到 $100$ 的陣列 $nums$，且 $1 \leq nums[i] \leq 100$，要計算一個連續區間的子陣列之中獨特數字的數量，將數量平方加到答案 $ans$ 之中。回傳所有子陣列的獨特數字數量平方加總。

由於陣列長度不大，直接用兩層 for 迴圈跑過所有的子陣列速度很快。可以用集合記錄子陣列中的獨特數字，也可以用一個長度為 $101$ 的陣列記錄範圍內 $0$ 到 $100$ 各個數字的數量。由於 Python 的集合運算速度很快，用集合寫很方便。但如果用 C++ 解題，即使用 unordered_set 計數速度也有點慢，用陣列計數會比較快。

Python 程式碼

Runtime: 19 ms, beats 82.77%. Memory: 19.32 MB, beats 27.38%.

class Solution:
    def sumCounts(self, nums: List[int]) -> int:
        n, ans = len(nums), 0 # 長度，答案
        # 以 i 為終點，找 j = i-1 ~ 0 範圍內獨特數字的數量並更新答案
        for i in range(n):
            distinct = {nums[i]}  # 用集合存數字
            ans += 1  # 答案加 1，集合內只有 nums[i]
            for j in range(i-1, -1, -1):
                distinct.add(nums[j])  # 加入 nums[j]
                ans += len(distinct)**2
        return ans

Runtime: 21 ms, beats 62.15%. Memory: 19.07 MB, beats 98.15%.

class Solution:
    def sumCounts(self, nums: List[int]) -> int:
        n, ans = len(nums), 0 # 長度，答案
        # 以 i 為終點，找 j = i-1 ~ 0 範圍內獨特數字的數量並更新答案
        for i in range(n):
            distinct = [0] * 101  # 範圍內 1 ~ 100 各數字的數量
            distinct[nums[i]] = 1  # nums[i] 數量為 1
            curr = 1  # 範圍內獨特數字的數量
            ans += 1  # 答案加 1，集合內只有 nums[i]
            for j in range(i-1, -1, -1):
                distinct[nums[j]] += 1  # nums[j] 數量加 1
                if distinct[nums[j]] == 1: curr += 1
                ans += curr * curr
        return ans

LeetCode 解題筆記：3723. Maximize Sum of Squares of Digits

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


LeetCode 題目連結：3723. Maximize Sum of Squares of Digits

解題想法

中等難度題。題目給兩個整數 $num, sum$，代表共有 $num$ 個數字，所有數字加總等於 $sum$。對於符合這兩個條件的數字，其分數為每個位數平方的加總，找出分數最高的數字並以字串格式回傳，如果無解則回傳空字串。這題下方的提示基本上已經講清楚解法，原則上盡量選用數字 9，最後再加上剩下的數字或 0，如果最後找到的答案位數大於 $num$ 無解。

Python 程式碼

用 for 迴圈依序填入數字，速度很慢。Runtime: 2761 ms, beats 5.51%. Memory: 21.24 MB, beats 59.06%.

class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        ans = ""  # 答案，字串格式
        rem = sum  # 位數加總
        # 每個位數都由 9 開始往下找，共執行 num 次
        for _ in range(num):
            for d in range(9, -1, -1):
                if rem >= d:
                    ans += str(d)
                    rem -= d
                    break
        return ans if rem == 0 else ""

計算需要填入的數字 9 數量以及餘數，速度快很多。Runtime: 4 ms, beats 74.02%. Memory: 20.87 MB, beats 90.55%.

class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        # 答案，字串格式，左側盡量用 9，如果 sum % 9 > 0，右側補上餘數
        ans = "9" * (sum // 9) + (str(sum % 9) if sum % 9 > 0 else "")
        # 長度不夠，補 0
        if len(ans) < num: ans += "0" * (num - len(ans))
        # 長度超過 num，無解
        return ans if len(ans) == num else ""

ZeroJudge 解題筆記：p929.像素圖 (Pixel)

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


ZeroJudge 題目連結：p929.像素圖 (Pixel)

題目 pdf 檔連結：像素圖 (Pixel)

解題想法

題目是多筆測資。每筆測資第一列是 4 個整數 $n, m, p, q$，分別代表圖的尺寸為 $n \times m$，列擴長為 $p$ 倍，欄擴張為 $q$ 倍。接下來 $n$ 列每列有 $m$ 個 0 或 1，輸出擴張後的圖。先用兩層 for 迴圈依序讀取每一個數字，將擴張後長度變為 $m \times q$ 的一列內容先填好，再將擴張後的列重複印出 $p$ 次，這樣寫起來比較簡單。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n, m, p, q = map(int, data[ptr : ptr + 4])
        ptr += 4
        for i in range(n):
            row = [0] * (m*q)
            for j in range(m):
                v = int(data[ptr])
                ptr += 1
                #for k in range(q):
                #    row[j*q + k] = v
                row[j*q : (j+1)*q] = [v]*q  # 用串列切片填入資料
            res = " ".join(map(str, row)) + "\n"
            for _ in range(p):
                result.append(res)
    
    # 輸出答案
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：p928.雷射探測 (Laser)

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


ZeroJudge 題目連結：p928.雷射探測 (Laser)

題目 pdf 檔連結：雷射探測 (Laser)

解題想法

題目是多筆測資。每筆測資第一列是兩個整數 $n, m$，代表地圖的尺寸為 $n \times m$。接下來共有 $n$ 列，每列皆為長度 $m$ 的字串，其中 . 代表空格，R 代表右斜鏡，L 代表左斜鏡，# 代表牆壁。雷射從地圖左上角 (0, 0) 的位置出發，方向向右。題目中有說明雷射光碰到右斜鏡、左斜鏡時方向變化的方式。要計算雷射光經過的格子數量，如果同一格經過不只一次，也只算一格。

這題需要判斷雷射光前進到下一格時，是否碰到反射鏡、牆壁或是出界，但是我不想要檢查邊界值，我在地圖的周圍加上一圈 #，只要碰到這個是 # 就停下來。我定義方向右、下、左、上分別對應 0, 1, 2, 3，用兩個陣列 slash、backslash 記錄右斜鏡、左斜鏡對應的方向變化方式。並用一個二維陣列 visited，記錄每個格子的走訪狀態。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 1. 讀取測資
        n = int(data[ptr])  # 地圖 n*m
        m = int(data[ptr + 1])
        ptr += 2
        grid = [["#"] * (m + 2) for _ in range(n + 2)]  # 地圖周圍加一圈 #
        for i in range(1, n + 1):  # 讀取地圖
            row = ["#"] + list(data[ptr]) + ["#"]
            grid[i] = row
            ptr += 1
        
        # 2. 從左上角出發找答案
        slash = (3, 2, 1, 0)  # 右斜鏡方向變化方式，右0、下1、左2、上3
        backslash = (1, 0, 3, 2)  # 左斜鏡方向變化方式，右0、下1、左2、上3
        dr, dc = (0, 1, 0, -1), (1, 0, -1, 0)  # 右、下、左、上位移量
        curr = 0  # 目前的方向，初始值向右
        ans = 0  # 經過的格子數
        r, c = 1, 1  # 目前的位置，加了一圈 #，起點改成 (1, 1)
        visited = [[False] * (m + 2) for _ in range(n + 2)]  # 走訪狀態
        while True:
            if not visited[r][c]:  # 還沒有走過的格子，答案加 1
                ans += 1
            visited[r][c] = True
            r += dr[curr]
            c += dc[curr]
            if grid[r][c] == '#':  # 遇到牆，停止
                break
            elif grid[r][c] == 'R':  # 右斜鏡
                curr = slash[curr]
            elif grid[r][c] == 'L':  # 左斜鏡
                curr = backslash[curr]

        result.append(f"{ans}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3727. Maximum Alternating Sum of Squares

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


LeetCode 題目連結：3727. Maximum Alternating Sum of Squares

解題想法

中等難度題，但其實寫起來很簡單。題目給一個長度為 $n$ 的整數陣列 $nums$，經過適當的排列之後，要找出 $score = nums[0]^2 - nums[1]^2 + nums[2]^2 - nums[3]^3 + \dots$ 的最大值。我的寫法是先將 $nums$ 所有的項目都改成平方，由小到大排序，答案 $ans$ 加上 $nums[n//2]$ 到 $nums[n-1]$，減去索引值 $nums[0]$ 到 $nums[n//2 - 1]$。不需要考慮 $n$ 的奇偶性，因為計算整數除法時，如果 $n$ 是奇數 $n//2$ 會自動捨去小數，將 $nums[n//2]$ 留給後半段要加到 $ans$ 的部分。

Python 程式碼

Runtime: 178 ms, beats 61.54%. Memory: 32.61 MB, beats 73.63%.

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        # 先將每一項都平方，由小到大排序，減去 nums[:n//2]，加上 nums[n//2:]
        nums = sorted(num**2 for num in nums)
        n = len(nums)  # 長度
        return sum(nums[n//2:]) - sum(nums[:n//2])

C++ 程式碼

Runtime: 66 ms, beats 37.15%. Memory: 176.10 MB, beats 70.59%.

class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums) {
        // 先將每一項都平方，由小到大排序，減去 nums[:n//2]，加上 nums[n//2:]
        int n = (int)nums.size();  // 長度
        for(int i = 0; i < n; i++) {
            nums[i] *= nums[i];
        }
        sort(nums.begin(), nums.end());
        return accumulate(nums.begin() + n/2, nums.end(), 0LL) - accumulate(nums.begin(), nums.begin() + n/2, 0LL);
    }
};

ZeroJudge 解題筆記：p927.調香師 (Perfumer)

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


ZeroJudge 題目連結：p927.調香師 (Perfumer)

題目 pdf 檔連結：調香師 (Perfumer)

解題想法

題目是多筆測資。每筆測資第一列是一個整數 $n$，代表有 $n$ 種香調。接下來共有 $2 n$ 列，每 $2$ 列一組，分別為香調名稱及這個香調的精油數量。下一列是一個整數 $k$，代表共使用 $k$ 種精油。接下來 $k$ 列，每列為使用的精油名稱及體積。要找出使用體積最多的香調名稱

這題需要記錄各種香調使用的體積，以及精油對應的香調名稱，用 Python dict 或是 C++ map, unordered_map 記錄資料會比較方便。需要特別注意，題目規定如有多個香調使用量同樣最多，答案是在測資中較早出現的香調，如果用 C++ 解題，要另外開一個 vector 記錄香調名稱出現的順序，否則會吃 NA。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # 精油香調數量
        ptr += 1
        cnt = dict()  # 各種香調使用體積
        name = dict()  # 精油對應的香調
        for _ in range(n):
            fragrance = data[ptr]  # 香調名稱
            m = int(data[ptr + 1])  # 這個香調的精油數量
            ptr += 2
            cnt[fragrance] = 0  # 設定 cnt 的 key 值
            for __ in range(m):  # 讀取 m 種精油名稱
                s = data[ptr]
                ptr += 1
                name[s] = fragrance
        
        k = int(data[ptr])  # 使用 k 種精油
        ptr += 1
        for _ in range(k):  # 讀取 k 種精油名稱及使用體積
            s = data[ptr]
            v = int(data[ptr + 1])
            ptr += 2
            cnt[name[s]] += v
        
        ans = ""  # 使用體積最多的香調
        imax = 0  # 最大體積
        for s, v in cnt.items():
            if v > imax:
                ans = s
                imax = v
        result.append(f"{ans}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：2897. Apply Operations on Array to Maximize Sum of Squares

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


LeetCode 題目連結：2897. Apply Operations on Array to Maximize Sum of Squares

解題想法

困難題。題目給一個整數陣列 $nums$，每次操作可以取任意兩個不同的索引值 $i, j$，同時將 $nums[i]$ 改成 nums[i] & nums[j]，$nums[j]$ 改成 nums[i] | nums[j]，操作次數不限。從 $nums$ 之中取 $k$ 個數字，求這 $k$ 個數字平方和最大值。

這題底下的提示1提到，這個操作過程只是移動 1，例如 1000 = 1111101000₂, 500 = 111110100₂，共有 $12$ 個 $1$，操作後 1000 & 500 = 111100000₂，1000 | 500 = 1111111100₂ 還是 $12$ 個 $1$。提示2有說可以用貪心法找最大平方和，這是基於提示1，由於 $1$ 的總數固定，盡量將 $1$ 集中到前 $k$ 個大的數字，可以使平方和最大化。由這兩個提示開始寫程式碼即可。

Python 程式碼

Runtime: 1409 ms, beats 44.68%. Memory: 31.96 MB, beats 76.60%.

class Solution:
    def maxSum(self, nums, k) -> int:
        # 1. 統計每個位數有幾個 1，因為 nums[i] <= 10**9 < 2**31，長度開 32 就夠用
        cnt = [0] * 32  # 0 ~ 31 位各有幾個 1
        for num in nums:
            for i in range(32):
                if (num >> i) & 1:
                    cnt[i] += 1

        # 2. 用貪心法重組出 k 個最大的數字，過程中同時取餘數
        ans = 0
        mod = 10**9 + 7
        for _ in range(k):
            val = 0
            for i in range(32):
                if cnt[i] > 0:
                    val |= (1 << i)
                    cnt[i] -= 1
            ans = (ans + val * val % mod) % mod

        return ans