필사 모드: 算法与数据结构完全精通：从复杂度分析到 AI/ML 算法

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

T(n) = aT(n/b) + f(n)

# Red-Black Tree 旋转 - 左旋(Left Rotation)概念
#
#     x                y
#    / \    →         / \
#   a   y            x   c
#      / \          / \
#     b   c        a   b
#
def left_rotate(tree, x):
    y = x.right          # y 是 x 的右子节点
    x.right = y.left     # 把 y 的左子树接到 x 的右边
    if y.left != tree.NIL:
        y.left.parent = x
    y.parent = x.parent  # 把 x 的父节点接给 y
    if x.parent == tree.NIL:
        tree.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x           # 把 x 接为 y 的左子节点
    x.parent = y

import heapq

# 用最小堆实现 Dijkstra
def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    # 以 (距离, 节点) 的形式存入堆
    heap = [(0, start)]
    visited = set()

    while heap:
        dist, node = heapq.heappop(heap)
        if node in visited:
            continue
        visited.add(node)

        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))

    return distances

# 使用示例
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}
print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}

def floyd_warshall(n, edges):
    INF = float('inf')
    # dist[i][j] = i 到 j 的最短距离
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w

    for k in range(n):          # 中转节点
        for i in range(n):      # 起点
            for j in range(n):  # 终点
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

from collections import deque

def topological_sort(n, edges):
    indegree = [0] * n
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(n) if indegree[i] == 0])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return result if len(result) == n else []  # 存在环时返回空数组

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    # dp[i][j] = s1[:i] 与 s2[:j] 的 LCS 长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # 2D 表可视化示例(s1="ABCD", s2="ACBD")：
    #     ""  A  C  B  D
    #  ""  0  0  0  0  0
    #  A   0  1  1  1  1
    #  B   0  1  1  2  2
    #  C   0  1  2  2  2
    #  D   0  1  2  2  3  ← LCS 长度 = 3("ABD" 或 "ACD")
    return dp[m][n]

def knapsack(weights, values, capacity):
    n = len(weights)
    # dp[i][w] = 考虑到第 i 个物品、容量为 w 时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # 不选第 i 个物品
            dp[i][w] = dp[i-1][w]
            # 选第 i 个物品
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][capacity]

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.build(arr, 0, 0, self.n - 1)

    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self.build(arr, 2*node+1, start, mid)
            self.build(arr, 2*node+2, mid+1, end)
            self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]

    def query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0  # 超出范围
        if l <= start and end <= r:
            return self.tree[node]  # 完全包含
        mid = (start + end) // 2
        left = self.query(2*node+1, start, mid, l, r)
        right = self.query(2*node+2, mid+1, end, l, r)
        return left + right

    def update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
        else:
            mid = (start + end) // 2
            if idx <= mid:
                self.update(2*node+1, start, mid, idx, val)
            else:
                self.update(2*node+2, mid+1, end, idx, val)
            self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)  # 加上 LSB(最低有效位)

    def query(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)  # 减去 LSB(最低有效位)
        return total

    def range_query(self, l, r):
        return self.query(r) - self.query(l - 1)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        # 路径压缩(Path Compression)
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # 已属于同一集合
        # 按秩合并(Union by Rank)
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True
# 路径压缩 + 按秩合并 → 实际上 O(α(n)) ≈ O(1)(反阿克曼函数)

def kmp_search(text, pattern):
    def build_lps(pattern):
        lps = [0] * len(pattern)
        length, i = 0, 1
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            elif length:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
        return lps

    lps = build_lps(pattern)
    i = j = 0
    results = []
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1; j += 1
        if j == len(pattern):
            results.append(i - j)
            j = lps[j - 1]
        elif i < len(text) and text[i] != pattern[j]:
            j = lps[j - 1] if j else (i := i + 1) and 0
    return results

class KDNode:
    def __init__(self, point, left=None, right=None):
        self.point = point
        self.left = left
        self.right = right

def build_kd_tree(points, depth=0):
    if not points:
        return None
    k = len(points[0])
    axis = depth % k
    sorted_points = sorted(points, key=lambda p: p[axis])
    mid = len(sorted_points) // 2
    return KDNode(
        point=sorted_points[mid],
        left=build_kd_tree(sorted_points[:mid], depth + 1),
        right=build_kd_tree(sorted_points[mid+1:], depth + 1)
    )

def nearest_neighbor(root, query, depth=0, best=None):
    if root is None:
        return best
    k = len(query)
    axis = depth % k

    dist = sum((q - p) ** 2 for q, p in zip(query, root.point)) ** 0.5
    if best is None or dist < best[0]:
        best = (dist, root.point)

    # 比较查询点与分割超平面
    diff = query[axis] - root.point[axis]
    close, away = (root.left, root.right) if diff <= 0 else (root.right, root.left)

    best = nearest_neighbor(close, query, depth + 1, best)
    # 判断是否需要搜索另一侧子树
    if abs(diff) < best[0]:
        best = nearest_neighbor(away, query, depth + 1, best)
    return best

beam width k=2，每个 token 保留前 2 个：
第 1 步：[A(0.6), B(0.4)]
第 2 步：[AA(0.36), AB(0.24), BA(0.28), BB(0.16)] → 保留前 2：[AA, BA]
第 3 步：[AAX, AAY, BAX, BAY] → 继续保留前 2...

f(n) = g(n) + h(n)
g(n) = 从起点到当前节点的实际成本
h(n) = 从当前节点到目标的估计成本(可采纳启发式)

# 在有序数组中找出和为 target 的两个数
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return (left, right)
        elif current < target:
            left += 1
        else:
            right -= 1
    return None
# 时间 O(n)，空间 O(1)

# 长度为 k 的子数组的最大和
def max_subarray_sum(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum
# 时间 O(n)，空间 O(1)

# N-Queens 问题
def solve_n_queens(n):
    results = []
    board = [-1] * n

    def is_valid(row, col):
        for r in range(row):
            if board[r] == col:
                return False
            if abs(board[r] - col) == abs(r - row):
                return False
        return True

    def backtrack(row):
        if row == n:
            results.append(board[:])
            return
        for col in range(n):
            if is_valid(row, col):
                board[row] = col
                backtrack(row + 1)
                board[row] = -1  # 回溯

    backtrack(0)
    return results