例题 1：Pow(x, n)

题目描述：实现 pow(x, n)，即 x 的 n 次方。n 可为负数；-2³¹ ≤ n ≤ 2³¹-1。

def my_pow(x: float, n: int) -> float:
    """快速幂：n 为负时用 1/x 和 -n；迭代写法避免递归栈。"""
    if n < 0:
        x, n = 1.0 / x, -n
    res = 1.0
    base = x
    while n:
        if n & 1:
            res *= base
        base *= base
        n >>= 1
    return res

讲解：n 的二进制每一位对应 base 的幂，从低到高若该位为 1 则乘入 res；每次 base 自乘得到 x^(2^k)。时间 O(log n)，空间 O(1)。

例题 2：多数元素（分治）

题目描述：数组 nums 中存在出现次数超过 ⌊n/2⌋ 的元素（多数元），找出它。假设总存在。

思路：分治：若左右两半的多数元相同则其为全局多数元；若不同则分别统计两半的多数元在全局中的出现次数，取较多者。也可用 Boyer-Moore 投票 O(n) 空间 O(1)。

from typing import List


def majority_element(nums: List[int]) -> int:
    """分治：区间 [l, r) 的多数元，若左右多数元相同则返回；否则比较两者在区间内的出现次数。"""

    def count_in_range(val: int, l: int, r: int) -> int:
        c = 0
        for i in range(l, r):
            if nums[i] == val:
                c += 1
        return c

    def majority(l: int, r: int) -> int:
        if r - l == 1:
            return nums[l]
        mid = (l + r) // 2
        left_maj = majority(l, mid)
        right_maj = majority(mid, r)
        if left_maj == right_maj:
            return left_maj
        return left_maj if count_in_range(left_maj, l, r) > count_in_range(right_maj, l, r) else right_maj

    return majority(0, len(nums))

讲解：子区间多数元若相同必为全局多数元；若不同则两候选在区间内各数一遍，多的为多数元。T(n)=2T(n/2)+O(n)，时间 O(n log n)。

例题 3：合并 K 个升序链表（分治合并）

题目描述：k 个升序链表，合并成一个升序链表。分治：两两合并，再对合并结果继续两两合并，直到剩一个。

from typing import List, Optional


class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None) -> None:
        self.val = val
        self.next = next


def merge_two(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    """合并两个有序链表。"""
    dummy = ListNode(0)
    p = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            p.next = l1
            l1 = l1.next
        else:
            p.next = l2
            l2 = l2.next
        p = p.next
    p.next = l1 or l2
    return dummy.next


def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    """分治：合并 lists[l..r-1]。若 l==r 返回 None，l+1==r 返回 lists[l]；否则 mid 分两半递归合并再 merge_two。"""
    def merge_range(l: int, r: int) -> Optional[ListNode]:
        if l >= r:
            return None
        if l + 1 == r:
            return lists[l]
        mid = (l + r) // 2
        return merge_two(merge_range(l, mid), merge_range(mid, r))
    return merge_range(0, len(lists))

讲解：每轮将前 half 与后 half 两两合并，结果写回前 half，轮数 O(log k)，每轮总合并代价 O(N)（N 为总节点数），总时间 O(N log k)。

例题 4：不同的二叉搜索树 II（递归构造）

题目描述：给定整数 n，生成所有由 1..n 为节点组成的、结构不同的二叉搜索树。

思路：枚举根 k（1..n），左子树由 [1,k-1] 生成的所有 BST，右子树由 [k+1,n] 生成的所有 BST，组合成以 k 为根的所有 BST。

from typing import List, Optional


class TreeNode:
    def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None) -> None:
        self.val = val
        self.left = left
        self.right = right


def generate_trees(n: int) -> List[Optional[TreeNode]]:
    """返回 [1..n] 构成的所有不同 BST。若 start>end 返回 [None]。"""

    def build(start: int, end: int) -> List[Optional[TreeNode]]:
        if start > end:
            return [None]
        res: List[Optional[TreeNode]] = []
        for k in range(start, end + 1):
            lefts = build(start, k - 1)
            rights = build(k + 1, end)
            for L in lefts:
                for R in rights:
                    root = TreeNode(k)
                    root.left = L
                    root.right = R
                    res.append(root)
        return res

    return build(1, n) if n else []

讲解：递归构造 [start, end] 的所有 BST：枚举根 k，左子树列表与右子树列表笛卡尔积得到以 k 为根的所有树。时间与生成的树数量相关，空间 O(递归深度)。