從 AI / ML 工作主題
找到下一題練習

題目整理

回傳陣列中出現次數最多的 k 個不同數字，結果順序不限。

nums=[4,4,1,1,1,9], k=2 → [1,4]

解法說明

先計數，再依頻率分桶，由高到低收集 k 個元素。

n 為輸入元素數。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

回傳頻率最高的 k 個字，先按頻率降序，再按字典序升序。

words=["ml","ai","ml","ai","data"], k=2 → ["ai","ml"]

解法說明

用 (-frequency, word) 排序；平手規則是本題與 Elements 的主要差異。

C 為所有輸入字元數，u 為不同單字數，L 為最長單字長度；字串比較最壞 O(L)。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

回傳離原點最近的 k 個二維點，順序不限。

points=[[3,0],[1,1],[-1,0]], k=2 → [[-1,0],[1,1]]

解法說明

維持最多 k 個點的 max-heap；平方距離即可比較遠近。

n 為點數。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

每輸入一個字元，輸出最多三個符合當前 prefix、字典序最小的商品名。

products=["car","cat","cup"], searchWord="ca" → [["car","cat","cup"],["car","cat"]]

解法說明

排序後，對各 prefix 用 lower_bound 找起點，只檢查接下來最多三個商品。

n 為商品數，L 為最長商品名，m 為查詢長度；計入 Python 排序空間與 prefix 字串，結果僅存字串參照。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

把 k 條已排序 linked lists 合成一條排序串列。

lists=[[1,4],[2,3],[0,5]] → [0,1,2,3,4,5]

解法說明

Heap 只保存每條串列尚未輸出的最小節點；取出後補入該串列下一個。

N 為總節點數，k 為串列數；額外空間不含輸出。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

把字母種類與次數完全相同的單字分為同組。

["tea","eat","tan"] → [["tea","eat"],["tan"]]

解法說明

小寫英文可用 26 維頻率 tuple 當 key，避免反覆比較字串。

C 為總字元數，n 為單字數；字母表固定 26，輸出持有原字串參照。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

設計字串清單與單一字串之間可無損往返的 encode / decode。

["a#b",""] → "3#a#b0#" → ["a#b",""]

解法說明

為每段寫入長度前綴；decode 讀完長度後，精確消耗該長度的內容。

C 為總字元數，n 為字串數；包含輸出與空字串的記錄成本。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

判斷字串能否完全拆成字典中的單字，字典中的字可重複使用。

s="aiml", dict=["ai","ml"] → true

解法說明

dp[i] 表示前 i 個字元可切分；從可達位置嘗試匹配字典單字。

n 為字串長度，d 為字典大小，L 為最長單字；以逐詞 startswith 版本為準，不含輸入。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

用插入、刪除、替換，把 word1 變成 word2，回傳最少操作數。

word1="cat", word2="cut" → 1

解法說明

每個 prefix pair 的最佳答案只依賴插入、刪除、替換的較短 prefix；相同字元不需付費。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        previous = list(range(len(word2) + 1))
        for i, ch1 in enumerate(word1, 1):
            current = [i]
            for j, ch2 in enumerate(word2, 1):
                if ch1 == ch2:
                    current.append(previous[j - 1])
                else:
                    current.append(1 + min(
                        previous[j],      # Delete from word1.
                        current[j - 1],   # Insert into word1.
                        previous[j - 1],  # Replace.
                    ))
            previous = current
        return previous[-1]

m、n 為兩字串長度；只保留上一列與目前列。

Interview Explanation Flow

"cat" → "cut": replace a with u → 1
"" → "abc": insert a, b, c → 3

題目整理

依出現次數由多至少重排全部字元；同頻率的字元順序不限。

s="tree" → "eetr"（"eert" 也合法）

解法說明

先計數，再按頻率排序不同字元，按次數重複寫回。

n 為字串長度，u 為不同字元數；計入輸出與暫存字串。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

給先修依賴，輸出可完成全部課程的順序；有 cycle 則回傳空清單。

numCourses=3, prerequisites=[[1,0],[2,1]] → [0,1,2]

解法說明

Kahn：只執行入度為 0 的節點，完成後解除後續依賴；輸出不足代表 cycle。

V 為課程數，E 為依賴數。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

有非負邊權的有向圖，從 k 發送訊號，回傳所有節點收到的最短所需時間；有人不可達則 -1。

times=[[1,2,2],[2,3,1],[1,3,5]], n=3, k=1 → 3

解法說明

Dijkstra 每次確認最小暫定距離；答案是所有最短距離的最大值。

from heapq import heappop, heappush


class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        graph = [[] for _ in range(n + 1)]
        for source, target, weight in times:
            graph[source].append((target, weight))

        distance = [float("inf")] * (n + 1)
        distance[k] = 0
        heap = [(0, k)]
        while heap:
            cost, node = heappop(heap)
            if cost != distance[node]:
                continue  # Ignore a superseded candidate.
            for neighbor, weight in graph[node]:
                candidate = cost + weight
                if candidate < distance[neighbor]:
                    distance[neighbor] = candidate
                    heappush(heap, (candidate, neighbor))

        answer = max(distance[1:])
        return -1 if answer == float("inf") else answer

以允許 heap 保留過期候選的實作為準。

Interview Explanation Flow

1 → 2 costs 2; 2 → 3 costs 1; 1 → 3 costs 5
After node 1: distances = [0,2,5]
After node 2: distances = [0,2,3]
Return max = 3; the heap's old (5,3) entry is ignored.

題目整理

從不同正整數中選數，可重複使用，列出總和等於 target 的不同組合；順序不產生新組合。

candidates=[2,3], target=6 → [[2,2,2],[3,3]]

解法說明

固定候選 index 的非遞減順序來避免排列重複；剩餘總和不足就剪枝。

class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        result = []
        path = []

        def search(start: int, remaining: int) -> None:
            if remaining == 0:
                result.append(path.copy())
                return
            for index in range(start, len(candidates)):
                value = candidates[index]
                if value > remaining:
                    break
                path.append(value)
                search(index, remaining - value)
                path.pop()  # Undo this choice before exploring another.

        search(0, target)
        return result

c 為候選數，D=⌊target/min(candidates)⌋，R 為結果數；包含輸出，排除輸出為 O(D)。

Interview Explanation Flow

[2,3], target=6
choose 2 → 2 → 2: remaining 0 → save [2,2,2]
undo choices; choose 3 → 3 → save [3,3]
No [3,2,...] branch: indices never move backward.

題目整理

每次回傳一個 index，使機率等於該位置權重除以總權重。

w=[1,3] → index 0 機率 1/4，index 1 機率 3/4（單次結果不固定）

解法說明

把權重變成累積區間；均勻抽取票號，再二分找到所屬區間。

n 為權重數；這是有放回抽樣。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

設計集合，支援插入、刪除與等機率隨機取值，平均每個操作 O(1)。

insert(8) → true; insert(5) → true; remove(8) → true; getRandom() → 5

解法說明

陣列提供隨機索引，map 記錄位置；刪除時以最後一個元素補洞並更新索引。

from random import choice


class RandomizedSet:
    def __init__(self):
        self.values = []
        self.positions = {}

    def insert(self, val: int) -> bool:
        if val in self.positions:
            return False
        self.positions[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.positions:
            return False
        index = self.positions[val]
        last = self.values[-1]
        self.values[index] = last
        self.positions[last] = index
        self.values.pop()
        del self.positions[val]
        return True

    def getRandom(self) -> int:
        return choice(self.values)

n 為目前集合大小；getRandom 僅在非空集合呼叫。

Interview Explanation Flow

values=[8,5,9], positions={8:0,5:1,9:2}
remove(5): put 9 in slot 1, update positions[9], pop last
values=[8,9], positions={8:0,9:1}

題目整理

從非負數列中選取互不相鄰的元素，求最大總和。

nums=[2,7,9,3,1] → 12（2+9+1）

解法說明

每一步比較跳過目前值，或取目前值加上前兩格最佳值。

n 為元素數。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

從非負 grid 左上到右下，每次向右或向下，回傳沿途最小總和。

grid=[[1,3],[2,1]] → 4

解法說明

目前格子的最小成本 = 自身成本 + min(上方最佳, 左方最佳)。

r、c 為列、欄數；選擇不修改輸入的一維 DP 版本。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

初始化不可變陣列後，多次查詢閉區間 [left,right] 的元素總和。

nums=[2,4,6]; sumRange(1,2) → 10

解法說明

prefix[i] 代表前 i 項總和，用 prefix[right+1] - prefix[left] 回答查詢。

n 為元素數。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

支援新增數值與查詢目前全部數值的中位數。

addNum(2), addNum(8) → median 5；再 addNum(3) → median 3

解法說明

兩個 heap 分別保留較小半與較大半，維持順序與大小平衡。

n 為已加入數量；與近似 quantile sketch 不同。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

固定長度 k 的窗口依序向右滑動，回傳每個窗口的最大值。

nums=[1,3,-1,2], k=2 → [3,3,2]

解法說明

Deque 存 index 並保持對應值遞減；更晚且更大的元素會淘汰較早的小值。

from collections import deque


class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        candidates = deque()
        answer = []
        for right, value in enumerate(nums):
            while candidates and candidates[0] <= right - k:
                candidates.popleft()
            while candidates and nums[candidates[-1]] <= value:
                candidates.pop()
            candidates.append(right)
            if right >= k - 1:
                answer.append(nums[candidates[0]])
        return answer

n 為陣列長度；每個 index 最多進出 deque 一次。

Interview Explanation Flow

nums=[1,3,-1,2], k=2
r=0: deque values [1]
r=1: 3 removes 1 → [3] → output 3
r=2: [3,-1] → output 3
r=3: expire 3; 2 removes -1 → [2] → output 2

題目整理

支援 get / put；容量滿時淘汰最久未使用項目，各操作平均 O(1)。

capacity=2; put(1,10), put(2,20), get(1), put(3,30) → key 2 被淘汰

解法說明

Hash map 找 node，doubly linked list 維持新舊次序；讀寫後都移到最新端。

需維護 map 與串列一致性；更新舊 key 不應增加項目數。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

保存 key 的多個時間版本，查詢不晚於給定時間的最新值，沒有則回傳空字串。

set("x","old",2), set("x","new",5); get("x",4) → "old"

解法說明

每個 key 的版本按時間 append；二分找最後一個 timestamp ≤ query 的版本。

v 為該 key 的版本數，N 為總寫入數；前提是寫入時間遞增。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

同字母任務之間需至少隔 n 個時間單位，任務各花一單位，求含 idle 的最短完成時間。

tasks=["A","A","B"], n=2 → 4（A,B,idle,A）

解法說明

最高頻率 f 決定 (f-1)(n+1)+t 的框架，t 是同最高頻種類數；與任務總數取 max。

T 為任務數；題目字母種類固定 26。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

由起點把四方向連通、與起點原色相同的區域全部改色。

image=[[1,1],[1,0]], sr=0, sc=0, color=2 → [[2,2],[2,0]]

解法說明

BFS 入隊時改色當作 visited；原色等於新色時直接結束。

r、c 為影像尺寸；BFS queue 最壞可佔相同量級。

繼續閱讀 Python 解法與既有繁中說明 →

題目整理

在字元 '1' / '0' 的網格中，計算四方向相連的陸地群數。

grid=[["1","0"],["0","1"]] → 2

解法說明

掃到未訪問陸地就建立一座島，再用 BFS 標記整個連通塊。

from collections import deque


class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        rows, cols = len(grid), len(grid[0])
        seen = set()
        count = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != "1" or (r, c) in seen:
                    continue
                count += 1
                seen.add((r, c))
                queue = deque([(r, c)])
                while queue:
                    x, y = queue.popleft()
                    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        nx, ny = x + dx, y + dy
                        if (0 <= nx < rows and 0 <= ny < cols
                                and grid[nx][ny] == "1"
                                and (nx, ny) not in seen):
                            seen.add((nx, ny))
                            queue.append((nx, ny))
        return count

r、c 為網格尺寸；這份解法以 seen 保存訪問記錄，保留輸入。

Interview Explanation Flow

grid=[["1","0"],["0","1"]]
Start at (0,0): island 1, no adjacent land
Start at (1,1): island 2 → return 2

題目整理

將 n×n 矩陣原地順時針旋轉 90 度。

matrix=[[1,2],[3,4]] → [[3,1],[4,2]]

解法說明

先轉置，再反轉每列；對應 (r,c) → (c,n-1-r)。

class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)
        for r in range(n):
            for c in range(r + 1, n):
                matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
        for row in matrix:
            row.reverse()

n 為正方形邊長；使用交換，不建立新矩陣。

Interview Explanation Flow

[[1,2],[3,4]]
transpose → [[1,3],[2,4]]
reverse rows → [[3,1],[4,2]]

題目整理

判斷只含 ()[]{} 的字串，括號類型與巢狀配對順序是否正確。

"([])" → true；"([)]" → false

解法說明

Stack 記錄尚未關閉的左括號；每個右括號必須匹配最後開啟的括號。

class Solution:
    def isValid(self, s: str) -> bool:
        matching = {")": "(", "]": "[", "}": "{"}
        stack = []
        for char in s:
            if char in matching:
                if not stack or stack.pop() != matching[char]:
                    return False
            else:
                stack.append(char)
        return not stack

n 為字串長度。

Interview Explanation Flow

"([])": push (, push [, match ], match ) → true
"([)]": ) does not match the top [ → false

題目整理

判斷字串是否整段符合 pattern：'.' 代表任一字元，'*' 使前一元素重複零次以上。

s="aab", p="c*a*b" → true

解法說明

Memoized DP(i,j)：遇 x* 可跳過該組，或匹配一個字元後繼續留在同組。

m、n 為字串與 pattern 長度；需記憶化避免重複子問題。

繼續閱讀 Python 解法與既有繁中說明 →