11 題 Python 解題筆記

from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]

        def rob_line(values: List[int]) -> int:
            two_back = 0
            one_back = 0
            for money in values:
                two_back, one_back = one_back, max(one_back, two_back + money)
            return one_back

        return max(rob_line(nums[:-1]), rob_line(nums[1:]))

Step 1: Point out the circular constraint

"This is similar to the regular House Robber problem, but the first and last houses are adjacent, so they cannot both be robbed."

Step 2: Split into two linear cases

"To remove the circular dependency, I split the problem into two normal linear robber problems: rob houses from index 0 to n - 2, or rob houses from index 1 to n - 1."

case 1: exclude the last house  -> nums[0:n-1]
case 2: exclude the first house -> nums[1:n]

Example:
nums = [2, 3, 2]

exclude last  -> [2, 3] -> 3
exclude first -> [3, 2] -> 3

answer = max(3, 3) = 3

Step 3: Reuse the linear DP helper

"For each linear case, I use the standard recurrence: at each house, either skip it and keep the previous best, or rob it and add its value to the best from two houses ago."

new_best = max(previous_best, two_back + current_money)

Step 4: Discuss edge cases

"If there is only one house, I return its value directly because the split would otherwise create an empty case."

Step 5: Complexity

"Time complexity is O(n) because we run two linear scans. Space complexity is O(1) if we avoid counting slicing and only keep two DP variables."

Possible follow-ups

• Why two cases? "Every valid answer must exclude either the first house or the last house, so these two cases cover all possibilities."
• Why not use a full DP array? "The recurrence only depends on the previous two states, so two variables are enough."

中文：面試時先說清楚環狀限制，再拆成兩個線性 House Robber 問題。

from collections import deque


class HitCounter:
    def __init__(self):
        self.hits = deque()
        self.total = 0

    def hit(self, timestamp: int) -> None:
        if self.hits and self.hits[-1][0] == timestamp:
            self.hits[-1][1] += 1
        else:
            self.hits.append([timestamp, 1])
        self.total += 1

    def getHits(self, timestamp: int) -> int:
        while self.hits and self.hits[0][0] <= timestamp - 300:
            _, count = self.hits.popleft()
            self.total -= count
        return self.total

Step 1: Frame it as a sliding time window

"The counter only needs hits in the last 300 seconds, so I maintain a sliding window of valid timestamp buckets."

Step 2: Explain the bucket optimization

"Instead of storing every hit individually, I group hits with the same timestamp into one bucket [timestamp, count]. This saves space when many hits happen in the same second."

Step 3: Walk through hit

"When a new hit arrives, if the last bucket has the same timestamp, I increment that bucket. Otherwise I append a new bucket. I also maintain a running total."

Step 4: Walk through getHits

"For a query at time t, I remove buckets from the front while their timestamp is <= t - 300, subtract their counts from total, and then return total."

Example:
hit(1)
hit(1)
hit(300)

getHits(300):
valid timestamps are > 0
bucket [1, 2] and bucket [300, 1] are valid
answer = 3

getHits(301):
valid timestamps are > 1
bucket [1, 2] expires
answer = 1

Step 5: Complexity

"hit is O(1). getHits is amortized efficient because each bucket is inserted once and removed once. Space is bounded by the number of active timestamp buckets."

Possible follow-ups

• Why use a deque? "Expired timestamps always leave from the oldest side, so deque gives O(1) pops from the front."
• Why remove <= t - 300? "The valid window is timestamps strictly greater than t - 300."

中文：重點是把題目說成 300 秒 sliding window，並用 timestamp bucket 壓縮空間。

from typing import List


class Solution:
    def ipToCIDR(self, ip: str, n: int) -> List[str]:
        start = self._to_int(ip)
        blocks = []

        while n > 0:
            max_size = start & -start
            if max_size == 0:
                max_size = 1 << 32

            while max_size > n:
                max_size >>= 1

            prefix = 32 - (max_size.bit_length() - 1)
            blocks.append(f"{self._to_ip(start)}/{prefix}")

            start += max_size
            n -= max_size

        return blocks

    def _to_int(self, ip: str) -> int:
        value = 0
        for part in ip.split("."):
            value = value * 256 + int(part)
        return value

    def _to_ip(self, value: int) -> str:
        return ".".join(str((value >> shift) & 255) for shift in (24, 16, 8, 0))

Step 1: Define the goal

"Given a starting IP and a count n, we need to cover exactly n consecutive IPs using the minimum number of CIDR blocks -- no more, no less."

Step 2: Explain the two CIDR constraints

"A CIDR block has two hard constraints. First, its size must be a power of two -- /30 means 4 IPs, /29 means 8 IPs, and so on. Second, the starting address must be aligned to its size, meaning the start must be a multiple of the block size."

size = 4 -> start must be 0, 4, 8, 12, ...
size = 8 -> start must be 0, 8, 16, 24, ...

192.168.1.4:
  4 / 4 = 1    valid for size 4
  4 / 8 = 0.5  invalid for size 8

Step 3: Explain the greedy strategy

"At each step, we want the largest valid block we can place at the current start. This is greedy -- taking the largest block now always leads to the fewest total blocks, because choosing a smaller block never helps us cover the remaining interval with fewer blocks later."

Step 4: Explain start & -start

"To find the largest valid block size efficiently, we use the bit trick start & -start. In two's complement, negating a number flips all bits and adds one, which preserves only the lowest set bit and zeros everything else. So start & -start gives the largest power-of-two that start is divisible by -- exactly the alignment constraint we need."

start = 192.168.1.4 = ...00000100
-start              = ...11111100
AND                 = ...00000100 = 4

largest aligned size = 4

Step 5: Explain shrinking by remaining count

"We also cannot exceed the remaining count n. So if the aligned block size is larger than n, we keep halving it until it fits."

start = 192.168.1.8, n = 2

start & -start = 8
8 > 2 -> shrink
4 > 2 -> shrink
2 <= 2 -> stop, use size 2

Step 6: Convert block size to CIDR prefix

"Once we have the block size, the CIDR prefix is 32 minus the exponent. Since the block size is always a power of two, bit_length() - 1 gives the exponent directly."

size = 4 = 2^2
bit_length() = 3 -> exponent = 2
prefix = 32 - 2 = 30 -> /30

Step 7: Walk through a complete example

"Let me walk through a concrete example. Start is 192.168.1.4, and n = 6."

Round 1:
  start & -start = 4, 4 <= 6 -> size = 4
  prefix = 30 -> "192.168.1.4/30"
  covers .4, .5, .6, .7
  start = 192.168.1.8, n = 2

Round 2:
  start & -start = 8, 8 > 2 -> shrink to 2
  prefix = 31 -> "192.168.1.8/31"
  covers .8, .9
  start = 192.168.1.10, n = 0

result = ["192.168.1.4/30", "192.168.1.8/31"]

Step 8: Discuss edge case

"One edge case is when start is 0. Since 0 & -0 is 0, we special-case it to 1 << 32, representing the entire IPv4 space."

Step 9: Complexity

"Time and space are both O(B), where B is the number of output blocks. Since IPv4 is only 32 bits, B is at most 32 -- practically constant."

中文：面試時先講 CIDR 的 size 與 alignment 限制，再用 start & -start 找最大對齊 block，必要時縮小到不超過剩餘數量。

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        base = ord("a")
        need = [0] * 26
        window = [0] * 26

        for i, ch in enumerate(s1):
            need[ord(ch) - base] += 1
            window[ord(s2[i]) - base] += 1

        matches = sum(1 for i in range(26) if need[i] == window[i])
        if matches == 26:
            return True

        left = 0
        for right in range(len(s1), len(s2)):
            add = ord(s2[right]) - base
            if window[add] == need[add]:
                matches -= 1
            window[add] += 1
            if window[add] == need[add]:
                matches += 1

            remove = ord(s2[left]) - base
            if window[remove] == need[remove]:
                matches -= 1
            window[remove] -= 1
            if window[remove] == need[remove]:
                matches += 1
            left += 1

            if matches == 26:
                return True

        return False

Step 1: Identify the fixed-size window

"A permutation of s1 must have exactly the same length as s1, so I only need to check fixed-size windows in s2."

Step 2: Compare character frequencies

"Order does not matter for a permutation, so each window is valid if its 26 lowercase letter counts match the counts of s1."

Step 3: Explain the matches optimization

"Instead of comparing all 26 counts after every slide, I keep a matches counter that tells how many letters currently have equal frequencies in both arrays."

Step 4: Slide the window

"For each step, I add the new right character, remove the old left character, and update matches before and after each count change. If matches == 26, the current window is a permutation."

Example:
s1 = "ab"
s2 = "eidbaooo"
window size = 2

"ei" -> not match
"id" -> not match
"db" -> not match
"ba" -> matches counts of "ab"

return True

Step 5: Complexity

"Time complexity is O(|s1| + |s2|) because each character enters and leaves the window once. Space complexity is O(1) because the arrays always have size 26."

Possible follow-ups

• Why not sort every window? "Sorting each window would be more expensive; frequency counts let us update in constant time."
• What if s1 is longer than s2? "Then no valid window can exist, so return false immediately."

中文：關鍵是固定窗口長度，並用字母頻率判斷是否為排列。

from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        two_back = 0
        one_back = 0

        for money in nums:
            two_back, one_back = one_back, max(one_back, two_back + money)

        return one_back

Step 1: Frame the problem

"This is a dynamic programming problem because the best answer up to the current house depends on previous choices."

Step 2: Explain the two choices

"At each house, I either skip it and keep the previous best, or rob it and add its money to the best from two houses ago."

skip current: dp[i - 1]
rob current:  dp[i - 2] + nums[i]

Step 3: Derive the recurrence

"So the recurrence is dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])."

Example:
nums = [2, 7, 9, 3, 1]

house 0: max(0, 0 + 2)  = 2
house 1: max(2, 0 + 7)  = 7
house 2: max(7, 2 + 9)  = 11
house 3: max(11, 7 + 3) = 11
house 4: max(11, 11 + 1) = 12

answer = 12

Step 4: Explain space optimization

"The recurrence only needs two previous states, so I keep two_back for dp[i - 2] and one_back for dp[i - 1]."

Step 5: Complexity

"Time complexity is O(n) because we scan the houses once. Space complexity is O(1) because we only keep two variables."

Possible follow-ups

• Why is this DP? "The optimal answer for the current prefix is built from optimal answers to smaller prefixes."
• How is this different from House Robber II? "House Robber II adds circular adjacency, so we split it into two linear cases."

中文：面試時重點是先說偷與不偷兩種選擇，再推出只需前兩個狀態。

from bisect import bisect_right
from collections import defaultdict


class TimeMap:
    def __init__(self):
        self.times = defaultdict(list)
        self.values = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.times[key].append(timestamp)
        self.values[key].append(value)

    def get(self, key: str, timestamp: int) -> str:
        times = self.times.get(key)
        if not times:
            return ""

        index = bisect_right(times, timestamp) - 1
        if index < 0:
            return ""
        return self.values[key][index]

Step 1: Define the data model

"For each key, I store two parallel arrays: one for timestamps and one for values. The timestamps are sorted because the problem guarantees increasing timestamps for each key."

Step 2: Explain set

"For set, I simply append the timestamp and value to the arrays for that key. This is O(1)."

Step 3: Explain get with binary search

"For get, I need the latest timestamp that is less than or equal to the query timestamp. Since timestamps are sorted, I use bisect_right to find the insertion position after all valid timestamps, then subtract one."

index = bisect_right(times, timestamp) - 1

Example:
set("foo", "bar", 1)
set("foo", "bar2", 4)

times  = [1, 4]
values = ["bar", "bar2"]

get("foo", 3):
bisect_right([1, 4], 3) -> 1
index = 1 - 1 = 0
answer = "bar"

Step 4: Discuss missing cases

"If the key does not exist, or if the insertion position is 0, then there is no valid value at or before that timestamp, so I return an empty string."

Step 5: Complexity

"set is O(1). get is O(log m), where m is the number of versions for that key. Space is O(total sets)."

Possible follow-ups

• Why binary search? "We need the predecessor timestamp in a sorted list."
• Why two arrays? "It keeps timestamp search simple and lets us retrieve the value by the same index."

中文：重點是每個 key 維護遞增 timestamps，查詢時用 binary search 找最後一個不超過目標時間的版本。

from collections import deque
from typing import List


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

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    queue.append((r, c))
                elif grid[r][c] == 1:
                    fresh += 1

        minutes = 0
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while queue and fresh > 0:
            for _ in range(len(queue)):
                r, c = queue.popleft()
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 2
                        fresh -= 1
                        queue.append((nr, nc))
            minutes += 1

        return minutes if fresh == 0 else -1

Step 1: Recognize multi-source BFS

"This is a multi-source BFS problem because all rotten oranges start spreading at the same time."

Step 2: Initialize the queue and fresh count

"I scan the grid once, push all initially rotten oranges into the queue, and count how many fresh oranges exist."

Step 3: Explain minute-by-minute expansion

"Each BFS level represents one minute. During that minute, every rotten orange in the current queue infects adjacent fresh oranges."

Example:
2 1 1
1 1 0
0 1 1

minute 0: rotten starts at (0,0)
minute 1: infect (0,1), (1,0)
minute 2: infect next adjacent fresh oranges
...
answer = number of BFS layers needed until fresh count becomes 0

Step 4: Track completion

"Whenever a fresh orange becomes rotten, I decrement the fresh count. If all fresh oranges are infected, I return the number of minutes; if the queue is exhausted but fresh remains, I return -1."

Step 5: Complexity

"Time complexity is O(mn) because each cell is processed at most once. Space complexity is O(mn) for the queue in the worst case."

Possible follow-ups

• Why BFS instead of DFS? "BFS naturally models simultaneous spreading by minutes."
• What if there are no fresh oranges? "The answer is 0 because nothing needs to rot."

中文：把每一層 BFS 對應成一分鐘，就能清楚解釋腐爛同時擴散的過程。

from collections import deque
from typing import List


class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
            return -1

        directions = [
            (-1, -1), (-1, 0), (-1, 1),
            (0, -1),           (0, 1),
            (1, -1),  (1, 0),  (1, 1),
        ]
        queue = deque([(0, 0, 1)])
        grid[0][0] = 1

        while queue:
            r, c, distance = queue.popleft()
            if r == n - 1 and c == n - 1:
                return distance

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    grid[nr][nc] = 1
                    queue.append((nr, nc, distance + 1))

        return -1

Step 1: Frame it as shortest path in an unweighted grid

"Every valid move has the same cost, so BFS is the right algorithm to find the shortest path."

Step 2: Handle blocked endpoints

"If either the start or the destination is blocked, there is no valid path, so I return -1 immediately."

Step 3: Explain BFS state

"Each queue entry stores (row, col, distance). From each cell, I explore all 8 possible directions."

Example:
grid = [
  [0, 1],
  [1, 0]
]

start = (0,0), distance = 1
move diagonally to (1,1), distance = 2

answer = 2

Step 4: Mark visited when enqueuing

"I mark a cell as visited as soon as it is added to the queue, so it will not be enqueued multiple times by different neighbors."

Step 5: Complexity

"Time complexity is O(n²) because each cell is visited at most once. Space complexity is O(n²) for the queue."

Possible follow-ups

• Why return when reaching the target? "BFS explores in increasing distance order, so the first time we reach the target is shortest."
• Can we avoid modifying the grid? "Yes, we can use a separate visited set, but modifying the grid saves extra bookkeeping."

中文：面試時強調 BFS 適合無權重最短路徑，第一次到終點就是最短距離。

from collections import deque


class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        target_x, target_y = abs(x), abs(y)
        moves = [
            (1, 2), (2, 1), (-1, 2), (-2, 1),
            (1, -2), (2, -1), (-1, -2), (-2, -1),
        ]

        queue = deque([(0, 0, 0)])
        seen = {(0, 0)}

        while queue:
            cur_x, cur_y, distance = queue.popleft()
            if cur_x == target_x and cur_y == target_y:
                return distance

            for dx, dy in moves:
                nx, ny = cur_x + dx, cur_y + dy
                if (
                    -2 <= nx <= target_x + 2
                    and -2 <= ny <= target_y + 2
                    and (nx, ny) not in seen
                ):
                    seen.add((nx, ny))
                    queue.append((nx, ny, distance + 1))

        return -1

Step 1: Use symmetry

"The knight moves symmetrically across both axes, so I can convert the target to (abs(x), abs(y)) and only reason about the first quadrant."

Step 2: Use BFS for minimum moves

"Each knight move has equal cost, so BFS gives the minimum number of moves. The state is the current coordinate and distance."

Example:
target = (2, 1)

start at (0, 0)
one knight move can reach (2, 1)

answer = 1

Step 3: Bound the search area

"Even though the board is infinite, shortest paths only need a small margin around the target. I allow coordinates from -2 to target + 2 to preserve near-origin detours and small overshoots."

Step 4: Track visited coordinates

"I keep a seen set so each coordinate is processed once. When BFS reaches the target, I return the distance immediately."

Step 5: Complexity

"Time and space are proportional to the bounded search rectangle, roughly O((|x| + 5)(|y| + 5))."

Possible follow-ups

• Why keep negative coordinates down to -2? "Some shortest paths near the origin briefly move into negative coordinates."
• Why allow target + 2? "A shortest path may overshoot by at most one knight step before coming back."

中文：重點是先用對稱性縮小問題，再用有界 BFS 找最短步數。

class TicTacToe:
    def __init__(self, n: int):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diagonal = 0
        self.anti_diagonal = 0

    def move(self, row: int, col: int, player: int) -> int:
        delta = 1 if player == 1 else -1

        self.rows[row] += delta
        self.cols[col] += delta

        if row == col:
            self.diagonal += delta
        if row + col == self.n - 1:
            self.anti_diagonal += delta

        if (
            abs(self.rows[row]) == self.n
            or abs(self.cols[col]) == self.n
            or abs(self.diagonal) == self.n
            or abs(self.anti_diagonal) == self.n
        ):
            return player

        return 0

Step 1: Avoid scanning the board

"A naive solution scans rows, columns, and diagonals after every move. Instead, I maintain counters so each move can be checked in O(1)."

Step 2: Encode players as signs

"I represent player 1 as +1 and player 2 as -1. If one player fills an entire row, column, or diagonal, the absolute counter value becomes n."

Step 3: Update only affected lines

"For each move, I update exactly one row and one column. If the cell is on the main diagonal or anti-diagonal, I update those counters too."

Example with n = 3:

player 1 moves at (0,0): rows[0] = 1, cols[0] = 1, diagonal = 1
player 1 moves at (1,1): rows[1] = 1, cols[1] = 1, diagonal = 2
player 1 moves at (2,2): rows[2] = 1, cols[2] = 1, diagonal = 3

abs(diagonal) == n, so player 1 wins

Step 4: Check for a winner

"After updating counters, if any affected counter has absolute value n, the current player wins; otherwise return 0."

Step 5: Complexity

"Each move is O(1) time because only fixed counters are updated. Space is O(n) for row and column counters."

Possible follow-ups

• Why does sign encoding work? "A winning line must contain only one player's marks, so the signed sum reaches n or -n."
• Do we need to store the whole board? "No, the problem assumes moves are valid, so counters are enough."

中文：面試時強調用正負分數維護 row、col、diagonal，讓每步都能 O(1) 判斷勝負。

from typing import List


class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        result = []
        i = 0

        while i < len(words):
            line_len = len(words[i])
            j = i + 1

            while j < len(words) and line_len + 1 + len(words[j]) <= maxWidth:
                line_len += 1 + len(words[j])
                j += 1

            line_words = words[i:j]
            words_len = sum(len(word) for word in line_words)
            gaps = len(line_words) - 1

            if j == len(words) or gaps == 0:
                line = " ".join(line_words)
                line += " " * (maxWidth - len(line))
            else:
                spaces = maxWidth - words_len
                base_spaces, extra = divmod(spaces, gaps)
                parts = []

                for k, word in enumerate(line_words[:-1]):
                    parts.append(word)
                    parts.append(" " * (base_spaces + (1 if k < extra else 0)))
                parts.append(line_words[-1])
                line = "".join(parts)

            result.append(line)
            i = j

        return result

Step 1: Split the problem into two parts

"This problem has two distinct parts: first, greedily pack as many words as possible into each line; second, distribute spaces according to the text justification rules."

Step 2: Explain greedy packing

"For each line, I keep adding words as long as the current line length plus one required space and the next word does not exceed maxWidth."

Example: greedy packing
maxWidth = 16
words = ["What", "must", "be", "acknowledgment"]

line_len = 4 ("What")
+ 1 + 4 = 9   ("must") <= 16
+ 1 + 2 = 12  ("be")   <= 16
+ 1 + 14 = 27 ("acknowledgment") > 16 stop

line_words = ["What", "must", "be"]

Step 3: Explain space distribution

"After deciding the words in the line, I compute how many spaces are needed, how many gaps exist between words, and then use divmod to distribute spaces evenly."

Example: even space distribution
words_len = 4 + 4 + 2 = 10
spaces = 16 - 10 = 6
gaps = 2

divmod(6, 2) -> base_spaces = 3, extra = 0

"What" + "   " + "must" + "   " + "be"

"When the remainder is not zero, the first extra gaps receive one additional space from left to right."

Example: uneven space distribution
words = ["Science", "is", "what"]
words_len = 7 + 2 + 4 = 13
spaces = 16 - 13 = 3
gaps = 2

divmod(3, 2) -> base_spaces = 1, extra = 1

"Science" + "  " + "is" + " " + "what"
             left-side gap gets one extra space

Step 4: Discuss edge cases

"There are two special cases: the last line and a line with only one word. Both should be left-justified by joining words with a single space and padding the remaining spaces on the right."

j == len(words) -> last line
gaps == 0       -> only one word, avoid divmod(spaces, 0)

Step 5: Complexity

"Time complexity is O(total characters) because each word is processed once and each output line is built once. Space complexity is O(maxWidth) extra space for building one line, excluding the output."

Possible follow-ups

• Why use divmod? "It gives both the base spaces per gap and the remainder in one call."
• Why do extra spaces go to the left? "The problem requires left gaps to receive more spaces when spaces cannot be evenly distributed."
• Why track line_len? "It keeps the fit check O(1) instead of recomputing the current line length repeatedly."

中文：面試時先拆成 greedy packing 與 space distribution，再用整除與不整除例子展示細節。