21 題 Python 解題筆記

題目整理

給一個 startUrl 與 HtmlParser.getUrls(url) API，從起始頁開始爬取所有可達 URL，但只能保留與 startUrl 相同 hostname 的頁面。

解法說明

先解析出起始 hostname，然後用 BFS/DFS 掃描。每次從 queue 取 URL，呼叫 parser 拿到下一層 URL；若 hostname 相同且未看過，就加入 visited 與 queue。visited 同時避免重複爬取與 cycle。

from collections import deque
from typing import List
from urllib.parse import urlparse


class Solution:
    def crawl(self, startUrl: str, htmlParser: "HtmlParser") -> List[str]:
        host = urlparse(startUrl).netloc
        queue = deque([startUrl])
        seen = {startUrl}

        while queue:
            url = queue.popleft()
            for next_url in htmlParser.getUrls(url):
                if urlparse(next_url).netloc == host and next_url not in seen:
                    seen.add(next_url)
                    queue.append(next_url)

        return list(seen)

題目整理

設計一組 encode(strs) 與 decode(s)，能把字串陣列轉成單一字串並還原。字串內容可能包含任何字元，所以不能單純用固定 delimiter 分隔。

解法說明

使用「長度 + 分隔符 + 內容」格式，例如 5#hello。decode 時先讀到 # 取得長度，再切出固定長度內容；因為長度明確，內容即使包含 # 也不會混淆。

from typing import List


class Codec:
    def encode(self, strs: List[str]) -> str:
        parts = []
        for text in strs:
            parts.append(f"{len(text)}#{text}")
        return "".join(parts)

    def decode(self, s: str) -> List[str]:
        result = []
        i = 0

        while i < len(s):
            j = i
            while s[j] != "#":
                j += 1
            length = int(s[i:j])
            start = j + 1
            result.append(s[start:start + length])
            i = start + length

        return result

題目整理

設計簡化版 Excel，支援 set(row, col, val)、get(row, col) 與 sum(row, col, numbers)。numbers 可包含單一 cell 或 range，例如 A1、A1:B2；sum cell 要能隨引用 cell 的值更新。

解法說明

每個 cell 要嘛存直接值，要嘛存公式。公式用 Counter 記錄引用 cell 與出現次數；get 遇到公式就遞迴求每個引用 cell 的值。set 會清掉該 cell 的公式，代表它改回固定值。

from collections import Counter
from typing import List, Tuple


class Excel:
    def __init__(self, height: int, width: str):
        self.values = {}
        self.formulas = {}

    def set(self, row: int, column: str, val: int) -> None:
        cell = (row, column)
        self.values[cell] = val
        self.formulas.pop(cell, None)

    def get(self, row: int, column: str) -> int:
        cell = (row, column)
        if cell not in self.formulas:
            return self.values.get(cell, 0)

        total = 0
        for ref, count in self.formulas[cell].items():
            total += self.get(ref[0], ref[1]) * count
        return total

    def sum(self, row: int, column: str, numbers: List[str]) -> int:
        cell = (row, column)
        self.formulas[cell] = self._parse(numbers)
        self.values.pop(cell, None)
        return self.get(row, column)

    def _parse(self, numbers: List[str]) -> Counter:
        refs = Counter()
        for token in numbers:
            if ":" not in token:
                refs[self._cell(token)] += 1
                continue

            start, end = token.split(":")
            r1, c1 = self._cell(start)
            r2, c2 = self._cell(end)
            for row in range(r1, r2 + 1):
                for code in range(ord(c1), ord(c2) + 1):
                    refs[(row, chr(code))] += 1
        return refs

    def _cell(self, name: str) -> Tuple[int, str]:
        return int(name[1:]), name[0]

題目整理

給一張 image matrix、起點 (sr, sc) 與新顏色 color，將起點所在的連通區域全部換成新顏色；連通只看上下左右，且只能走原本顏色相同的格子。

解法說明

先記住起點原色。若原色已等於新色，直接回傳避免無限遞迴。否則 DFS/BFS 往四方向擴展，遇到同原色格子就改色並繼續。

from typing import List


class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original = image[sr][sc]
        if original == color:
            return image

        rows, cols = len(image), len(image[0])

        def dfs(r: int, c: int) -> None:
            if r < 0 or r == rows or c < 0 or c == cols or image[r][c] != original:
                return
            image[r][c] = color
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        dfs(sr, sc)
        return image

另一種解法：BFS / Queue

BFS 版本用 queue 逐層擴展連通區域。關鍵是「入隊時就改色」，這樣同一個格子不會被不同鄰居重複加入 queue。

from collections import deque
from typing import List


class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original = image[sr][sc]
        if original == color:
            return image

        rows, cols = len(image), len(image[0])
        queue = deque([(sr, sc)])
        image[sr][sc] = color  # Recolor on enqueue to avoid duplicate visits.

        while queue:
            r, c = queue.popleft()

            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original:
                    image[nr][nc] = color
                    queue.append((nr, nc))

        return image

題目整理

給一個非負整數 grid，從左上角走到右下角，每次只能往右或往下，請回傳路徑上數字總和的最小值。

解法說明

對每個格子，最佳路徑只可能從上方或左方來，因此 dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])。可以直接把 grid 原地改成到該格的最小成本。

from typing import List


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])

        for r in range(rows):
            for c in range(cols):
                if r == 0 and c == 0:
                    continue
                if r == 0:
                    grid[r][c] += grid[r][c - 1]
                elif c == 0:
                    grid[r][c] += grid[r - 1][c]
                else:
                    grid[r][c] += min(grid[r - 1][c], grid[r][c - 1])

        return grid[-1][-1]

另一種解法：1-D Array DP / Memoization

Why is 1-D enough? A 2D DP only ever looks at the current row and the row directly above, so a single 1D array suffices -- before updating dp[c], it still holds the value from the previous row (upper cell), and dp[c-1] already holds the updated value from the current row (left cell).
中文：每格只需要上方和左方的值，dp[c] 更新前天然保留上一行的結果，dp[c-1] 則已是同行左方的結果，一維陣列剛好同時滿足兩者。

from typing import List


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        dp = grid[0][:]  # Copy the first row.

        # Initialize the first row; each cell can only come from the left.
        for c in range(1, cols):
            dp[c] += dp[c - 1]

        for r in range(1, rows):
            dp[0] += grid[r][0]  # The first column can only come from above.
            for c in range(1, cols):
                # dp[c] is the upper cell; dp[c - 1] is the updated left cell.
                dp[c] = grid[r][c] + min(dp[c], dp[c - 1])

        return dp[-1]

題目整理

給一個字元陣列 chars，將連續相同字元壓縮成字元加次數；若次數為 1 不寫數字。必須原地修改並回傳壓縮後長度。

解法說明

用 read 找每個連續 group 的結尾，用 write 寫入 group 字元與 count 的每一位數字。因為壓縮結果不會比原資料更晚需要讀取的部分長，所以可以安全原地寫。

from typing import List


class Solution:
    def compress(self, chars: List[str]) -> int:
        write = 0
        read = 0

        while read < len(chars):
            char = chars[read]
            start = read
            while read < len(chars) and chars[read] == char:
                read += 1

            chars[write] = char
            write += 1

            count = read - start
            if count > 1:
                for digit in str(count):
                    chars[write] = digit
                    write += 1

        return write

題目整理

給 k 個已排序 linked lists，將它們合併成一條排序後的 linked list 並回傳 head。

解法說明

維護一個 min-heap，初始放入每條 list 的 head。每次 pop 最小節點接到答案後面，再把該節點的 next 放入 heap。Python heap 若 value 相同會比較節點物件，所以加一個遞增序號當 tie-breaker。

from heapq import heappop, heappush
from typing import List, Optional


class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        order = 0

        for node in lists:
            if node:
                heappush(heap, (node.val, order, node))
                order += 1

        dummy = ListNode(0)
        tail = dummy

        while heap:
            _, _, node = heappop(heap)
            tail.next = node
            tail = tail.next

            if node.next:
                heappush(heap, (node.next.val, order, node.next))
                order += 1

        return dummy.next

題目整理

每個 account 格式為 [name, email1, email2, ...]。如果兩個 account 共享任一 email，代表同一個人，請合併所有 emails 並排序；輸出格式為 [name, sorted emails...]。

解法說明

把 email 視為節點，同一 account 內所有 email union 起來。最後對每個 email 找 root 並分組，使用 root 對應的 name，輸出每組排序後的 emails。

What is Disjoint Set Union (DSU)? Disjoint Set Union (DSU) tracks which nodes belong to the same group. find returns a node's root (group ID), and union merges two groups by connecting one root to the other.
中文：DSU 追蹤哪些節點屬於同一組，find 回傳節點的 root（組別 ID），union 把兩個 root 相連，將兩組合併成一組。

from collections import defaultdict
from typing import List


class DSU:
    def __init__(self):
        self.parent = {}

    def find(self, x: str) -> str:
        if x not in self.parent:
            self.parent[x] = x
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a: str, b: str) -> None:
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            self.parent[root_b] = root_a


class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        dsu = DSU()
        email_to_name = {}

        for account in accounts:
            name = account[0]
            first = account[1]
            for email in account[1:]:
                email_to_name[email] = name
                dsu.union(first, email)

        groups = defaultdict(list)
        for email in email_to_name:
            groups[dsu.find(email)].append(email)

        result = []
        for root, emails in groups.items():
            result.append([email_to_name[root]] + sorted(emails))
        return result

題目整理

設計 WordDistance，初始化時給一串 words；多次查詢 shortest(word1, word2)，回傳兩個單字在原陣列中任意出現位置的最小距離。

解法說明

初始化時把每個 word 的所有 index 存成遞增 list。查詢兩個 words 時，用雙指針在線性時間掃兩個 sorted lists，每次更新距離並移動 index 較小的指針。

from collections import defaultdict
from typing import List


class WordDistance:
    def __init__(self, wordsDict: List[str]):
        self.positions = defaultdict(list)
        for index, word in enumerate(wordsDict):
            self.positions[word].append(index)

    def shortest(self, word1: str, word2: str) -> int:
        a = self.positions[word1]
        b = self.positions[word2]
        i = j = 0
        best = float("inf")

        while i < len(a) and j < len(b):
            best = min(best, abs(a[i] - b[j]))
            if a[i] < b[j]:
                i += 1
            else:
                j += 1

        return best

題目整理

給一個整數陣列，除了某個元素只出現一次，其餘元素都出現兩次。請用線性時間與常數額外空間找出只出現一次的元素。

解法說明

XOR 有三個關鍵性質：a ^ a = 0、a ^ 0 = a、交換律/結合律。因此所有成對數字會互相抵消，最後剩下 single number。

from typing import List


class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        answer = 0
        for num in nums:
            answer ^= num
        return answer

題目整理

設計 NumArray，初始化後多次查詢 sumRange(left, right)，回傳閉區間 [left, right] 的元素總和。陣列不會被更新。

解法說明

建立 prefix，其中 prefix[i] 是前 i 個元素總和，並讓 prefix[0] = 0。區間和就是 prefix[right + 1] - prefix[left]。

from typing import List


class NumArray:
    def __init__(self, nums: List[int]):
        self.prefix = [0]
        for num in nums:
            self.prefix.append(self.prefix[-1] + num)

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix[right + 1] - self.prefix[left]

題目整理

給字串 s 與 t，找出 s 中最短的 substring，使它包含 t 中每個字元及其所需次數；若不存在回傳空字串。

解法說明

用 sliding window。右指針加入字元並更新窗口計數，當某字元達到需求時增加 formed。當 formed == required，代表窗口有效，此時移動左指針盡量縮短並更新答案。

from collections import Counter, defaultdict


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s:
            return ""

        need = Counter(t)
        window = defaultdict(int)
        required = len(need)
        formed = 0
        left = 0
        best_len = float("inf")
        best_start = 0

        for right, char in enumerate(s):
            window[char] += 1
            if char in need and window[char] == need[char]:
                formed += 1

            while formed == required:
                if right - left + 1 < best_len:
                    best_len = right - left + 1
                    best_start = left

                left_char = s[left]
                window[left_char] -= 1
                if left_char in need and window[left_char] < need[left_char]:
                    formed -= 1
                left += 1

        if best_len == float("inf"):
            return ""
        return s[best_start:best_start + best_len]

題目整理

給一條 linked list，每個節點除了 next，還有可能指向任意節點或 null 的 random。請 deep copy 整條 list，回傳新 head。

解法說明

先走一遍原 list，為每個舊節點建立新節點並存入 old_to_new。第二遍再設定每個新節點的 next 與 random，都透過 map 找到對應的新節點。

class Solution:
    def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
        if not head:
            return None

        old_to_new = {}
        node = head
        while node:
            old_to_new[node] = Node(node.val)
            node = node.next

        node = head
        while node:
            clone = old_to_new[node]
            clone.next = old_to_new.get(node.next)
            clone.random = old_to_new.get(node.random)
            node = node.next

        return old_to_new[head]

題目整理

有 numCourses 門課，prerequisites 中 [a, b] 表示要先修 b 才能修 a。請回傳一個可行修課順序；若因 cycle 無法完成所有課，回傳空陣列。

解法說明

這是 topological sort。建立 graph b -> a 與每門課的 indegree。先把 indegree 為 0 的課放入 queue；每取出一門課，就降低後續課的 indegree。若最後輸出數量等於課數，順序有效；否則有 cycle。

What is Kahn's Algorithm? Kahn's Algorithm finds a topological order by repeatedly removing nodes with indegree 0, reducing neighbors' indegrees, and adding newly freed nodes to the queue. If all nodes are removed, the graph is acyclic; otherwise a cycle exists.
中文：反覆取出 indegree 為 0 的節點加入結果，並降低鄰居的 indegree，若最終所有節點都被取出代表無 cycle，否則有 cycle。

from collections import deque
from typing import List


class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses

        for course, prereq in prerequisites:
            graph[prereq].append(course)
            indegree[course] += 1

        queue = deque([course for course in range(numCourses) if indegree[course] == 0])
        order = []

        while queue:
            course = queue.popleft()
            order.append(course)

            for next_course in graph[course]:
                indegree[next_course] -= 1
                if indegree[next_course] == 0:
                    queue.append(next_course)

        return order if len(order) == numCourses else []

題目整理

給一組 folder paths，若某 path 是另一個已存在 folder 的子資料夾，就要移除。請回傳移除所有 sub-folders 後的頂層 folders。

解法說明

字典序排序後，parent folder 會排在它的 subfolders 前面。只要維護目前保留的最後一個 parent，若新 path 以 parent + "/" 開頭，就代表它是 subfolder，跳過；否則保留並更新 parent。

from typing import List


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        result = []

        for path in folder:
            if result and path.startswith(result[-1] + "/"):
                continue
            result.append(path)

        return result

題目整理

設計記憶體檔案系統，支援 ls(path)、mkdir(path)、addContentToFile(filePath, content)、readContentFromFile(filePath)。目錄列表需依字典序回傳；若 ls 指到檔案，回傳該檔名。

解法說明

用 Trie 表示路徑。每個節點有 children 與 content；content 為 None 表示目錄，否則表示檔案。走路徑時依 / 分段，mkdir 與寫檔需要自動建立不存在的節點。

from typing import List


class Node:
    def __init__(self):
        self.children = {}
        self.content = None


class FileSystem:
    def __init__(self):
        self.root = Node()

    def ls(self, path: str) -> List[str]:
        node = self._walk(path)
        if node.content is not None:
            return [path.split("/")[-1]]
        return sorted(node.children.keys())

    def mkdir(self, path: str) -> None:
        self._walk(path, create=True)

    def addContentToFile(self, filePath: str, content: str) -> None:
        node = self._walk(filePath, create=True)
        if node.content is None:
            node.content = ""
        node.content += content

    def readContentFromFile(self, filePath: str) -> str:
        return self._walk(filePath).content

    def _walk(self, path: str, create: bool = False) -> Node:
        node = self.root
        if path == "/":
            return node

        for part in path.split("/")[1:]:
            if create and part not in node.children:
                node.children[part] = Node()
            node = node.children[part]
        return node

題目整理

給兩條已排序 linked lists，合併成一條排序後的 linked list，並回傳新 head。

解法說明

用 dummy head 簡化串接。兩個指針分別指向兩條 list 的目前節點，每次接上較小者並前進；其中一條耗盡後，直接接上另一條剩餘部分。

from typing import Optional


class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        tail = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next

        tail.next = list1 or list2
        return dummy.next

題目整理

設計 stack，支援 push、pop、top、getMin，且每個操作都要 O(1)。

解法說明

stack 每個元素不只存 value，也存「push 完這個元素後的目前最小值」。因此 getMin 只要看 stack top 的第二欄，不需要額外掃描。

class MinStack:
    def __init__(self):
        self.stack = []

    def push(self, val: int) -> None:
        current_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, current_min))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]

題目整理

給一串任務字元 tasks 與冷卻時間 n，同一種任務兩次執行之間至少間隔 n 個時間單位。每個時間單位可執行一個任務或 idle，請回傳完成全部任務的最短時間。

解法說明

最高頻任務決定最少需要多少冷卻框架。若最高頻為 f，先形成 f - 1 個區塊，每塊長度 n + 1，最後再放所有同最高頻的任務。答案是這個框架長度與任務總數的最大值，因為其他任務可能足夠填滿 idle。

from collections import Counter
from typing import List


class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = Counter(tasks)
        max_freq = max(counts.values())
        max_count = sum(1 for count in counts.values() if count == max_freq)

        frame = (max_freq - 1) * (n + 1) + max_count
        return max(len(tasks), frame)

題目整理

實作簡化 regex matching：. 可匹配任一單字元，* 表示前一個元素可出現零次或多次。必須判斷整個字串 s 是否能被 pattern p 完整匹配。

解法說明

定義 dp(i, j) 表示 s[i:] 是否能被 p[j:] 匹配。若下一個 pattern 字元是 *，有兩種選擇：跳過這組 x*，或在目前字元匹配時消耗一個 s[i] 並留在同一個 pattern 位置。

from functools import lru_cache


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @lru_cache(None)
        def dp(i: int, j: int) -> bool:
            if j == len(p):
                return i == len(s)

            first_match = i < len(s) and (p[j] == s[i] or p[j] == ".")

            if j + 1 < len(p) and p[j + 1] == "*":
                return dp(i, j + 2) or (first_match and dp(i + 1, j))

            return first_match and dp(i + 1, j + 1)

        return dp(0, 0)

題目整理

給一個 Unix-style absolute path，將它簡化成 canonical path。多個 slash 視為一個，. 代表目前目錄，.. 代表上一層；結果必須以單一 / 開頭且不能以 slash 結尾（root 除外）。

解法說明

以 / 切分 path，空字串與 . 忽略；遇到 .. 就 pop stack（若 stack 非空）；其他名稱 push。最後用 "/" + "/".join(stack) 組回 canonical path。

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []

        for part in path.split("/"):
            if part == "" or part == ".":
                continue
            if part == "..":
                if stack:
                    stack.pop()
            else:
                stack.append(part)

        return "/" + "/".join(stack)