LeetCode 分类题型手册：十大高频题型的识别信号、解题模板与代表题

def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    """对撞指针：有序数组两数之和
    不变式：若解存在，必在 [left, right] 区间内
    时间 O(n)，空间 O(1)
    """
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1  # 和太小，左端右移
        else:
            right -= 1  # 和太大，右端左移
    return []

#include <vector>
using namespace std;

// 对撞指针 C++ 实现
vector<int> twoSumSorted(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int s = nums[left] + nums[right];
        if (s == target) return {left, right};
        else if (s < target) left++;
        else right--;
    }
    return {};
}

def remove_duplicates(nums: list[int]) -> int:
    """快慢指针：有序数组原地去重
    时间 O(n)，空间 O(1)
    """
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

print(two_sum_sorted([2, 7, 11, 15], 9))
print(two_sum_sorted([2, 3, 4], 6))

[0, 1]
[0, 2]

def is_palindrome(s: str) -> bool:
    """LC-125 验证回文串，忽略大小写与非字母数字字符"""
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left, right = left + 1, right - 1
    return True

print(is_palindrome("A man, a plan, a canal: Panama"))
print(is_palindrome("race a car"))

True
False

def find_anagrams(s: str, t: str) -> list[int]:
    """滑动窗口模板（LC-438 找所有字母异位词）
    valid 记录计数恰好满足 need 的字符种类数
    时间 O(n)，空间 O(k)，k 为字符集大小
    """
    from collections import Counter
    need, window, valid = Counter(t), Counter(), 0
    left, result = 0, []
    for right, ch in enumerate(s):
        window[ch] += 1
        if ch in need and window[ch] == need[ch]:
            valid += 1
        while valid == len(need):
            if right - left + 1 == len(t):
                result.append(left)
            out = s[left]
            if out in need and window[out] == need[out]:
                valid -= 1
            window[out] -= 1
            left += 1
    return result

#include <string>
#include <unordered_map>
#include <climits>
using namespace std;

// 最小覆盖子串 LC-76
string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    int left = 0, valid = 0, start = 0, minLen = INT_MAX;
    for (int right = 0; right < s.size(); right++) {
        char c = s[right];
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }
        while (valid == need.size()) {
            if (right - left + 1 < minLen) {
                start = left;
                minLen = right - left + 1;
            }
            char d = s[left];
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
            left++;
        }
    }
    return minLen == INT_MAX ? "" : s.substr(start, minLen);
}

def length_of_longest_substring(s: str) -> int:
    """LC-3：window 集合维护无重复窗口"""
    window = set()
    left = ans = 0
    for right, ch in enumerate(s):
        while ch in window:
            window.remove(s[left])
            left += 1
        window.add(ch)
        ans = max(ans, right - left + 1)
    return ans

print(length_of_longest_substring("abcabcbb"))
print(length_of_longest_substring("bbbbb"))
print(length_of_longest_substring("pwwkew"))

3
1
3

print(find_anagrams("cbaebabacd", "abc"))
print(find_anagrams("abab", "ab"))

[0, 6]
[0, 1, 2]

while len(window) == len(need):  # 错误
    ...

def binary_search(nums: list[int], target: int) -> int:
    """模板一：精确匹配（闭区间 [left, right]）"""
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2  # 防溢出写法
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def find_left_bound(nums: list[int], target: int) -> int:
    """模板二：左边界（第一个 >= target 的位置，左闭右开）"""
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

def find_right_bound(nums: list[int], target: int) -> int:
    """模板三：右边界（最后一个 <= target 的位置）"""
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left - 1

def search_rotated(nums: list[int], target: int) -> int:
    """旋转排序数组搜索，时间 O(log n)"""
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:  # 左半段有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # 右半段有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

print(binary_search([-1, 0, 3, 5, 9, 12], 9))
print(binary_search([-1, 0, 3, 5, 9, 12], 2))
print(find_left_bound([5, 7, 7, 8, 8, 10], 8))
print(find_right_bound([5, 7, 7, 8, 8, 10], 8))

4
-1
3
4

print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))

4
-1

class PrefixSum:
    """前缀和：构造 O(n)，区间和查询 O(1)"""

    def __init__(self, nums: list[int]):
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix[i + 1] = self.prefix[i] + nums[i]

    def range_sum(self, left: int, right: int) -> int:
        """返回 nums[left..right] 的和"""
        return self.prefix[right + 1] - self.prefix[left]

class DifferenceArray:
    """差分数组：区间修改 O(1)，还原 O(n)"""

    def __init__(self, nums: list[int]):
        self.diff = [0] * len(nums)
        self.diff[0] = nums[0]
        for i in range(1, len(nums)):
            self.diff[i] = nums[i] - nums[i - 1]

    def range_add(self, left: int, right: int, val: int) -> None:
        self.diff[left] += val
        if right + 1 < len(self.diff):
            self.diff[right + 1] -= val

    def get_result(self) -> list[int]:
        result = [self.diff[0]]
        for i in range(1, len(self.diff)):
            result.append(result[-1] + self.diff[i])
        return result

def subarray_sum(nums: list[int], k: int) -> int:
    """LC-560：前缀和之差等于 k 的配对计数
    时间 O(n)，空间 O(n)
    """
    from collections import defaultdict
    count = defaultdict(int)
    count[0] = 1  # 空前缀
    ans = s = 0
    for x in nums:
        s += x
        ans += count[s - k]
        count[s] += 1
    return ans

ps = PrefixSum([-2, 0, 3, -5, 2, -1])
print(ps.range_sum(0, 2))
print(ps.range_sum(2, 5))
print(ps.range_sum(0, 5))

1
-1
-3

print(subarray_sum([1, 1, 1], 2))
print(subarray_sum([1, 2, 3], 3))

2
2

def next_greater_element(nums: list[int]) -> list[int]:
    """单调栈：每个元素的下一个更大元素（无则 -1）
    不变式：栈内索引对应的值从栈底到栈顶单调递减
    时间 O(n)，空间 O(n)
    """
    n = len(nums)
    result = [-1] * n
    stack = []  # 存索引
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    return result

#include <vector>
#include <stack>
using namespace std;

// 每日温度 LC-739：返回等待天数
vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> result(n, 0);
    stack<int> stk;  // 存索引
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && temperatures[stk.top()] < temperatures[i]) {
            result[stk.top()] = i - stk.top();
            stk.pop();
        }
        stk.push(i);
    }
    return result;
}

def is_valid(s: str) -> bool:
    """LC-20 有效的括号：右括号必须匹配最近的左括号"""
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

print(is_valid("()[]{}"))
print(is_valid("(]"))
print(is_valid("([)]"))

True
False
False

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    result = [0] * n
    stack = []
    for i, t in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))

[1, 1, 4, 2, 1, 1, 0, 0]

def two_sum(nums: list[int], target: int) -> list[int]:
    """LC-1 两数之和：一次遍历 + 哈希表
    时间 O(n)，空间 O(n)
    """
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

def is_anagram(s: str, t: str) -> bool:
    """LC-242 有效的字母异位词：计数后比较"""
    from collections import Counter
    return Counter(s) == Counter(t)

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))
print(two_sum([3, 3], 6))

[0, 1]
[1, 2]
[0, 1]

print(is_anagram("anagram", "nagaram"))
print(is_anagram("rat", "car"))

True
False

class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None):
        self.val = val
        self.next = next

def reverse_list(head: ListNode | None) -> ListNode | None:
    """LC-206 反转链表（迭代）
    时间 O(n)，空间 O(1)；链表题优先迭代，见本章陷阱
    """
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    return prev

def has_cycle(head: ListNode | None) -> bool:
    """LC-141 环检测：Floyd 判圈
    不变式：若有环，快指针必然追上慢指针
    时间 O(n)，空间 O(1)
    """
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

def build_linked(values: list[int], pos: int = -1) -> ListNode | None:
    """按 values 建链表；pos >= 0 时尾节点指向第 pos 个节点（成环）"""
    nodes = [ListNode(v) for v in values]
    for a, b in zip(nodes, nodes[1:]):
        a.next = b
    if nodes and pos >= 0:
        nodes[-1].next = nodes[pos]
    return nodes[0] if nodes else None

def to_list(head: ListNode | None) -> list[int]:
    vals = []
    while head:
        vals.append(head.val)
        head = head.next
    return vals

head = build_linked([1, 2, 3, 4, 5])
print(to_list(reverse_list(head)))

[5, 4, 3, 2, 1]

print(has_cycle(build_linked([3, 2, 0, -4], pos=1)))
print(has_cycle(build_linked([1, 2])))

True
False

def reverse_list_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_list_recursive(head.next)  # 深度 > 1000 时 RecursionError
    head.next.next = head
    head.next = None
    return new_head

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root: TreeNode | None) -> int:
    """LC-104 最大深度：后序递归骨架
    时间 O(n)，空间 O(h)，h 为树高
    """
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def invert_tree(root: TreeNode | None) -> TreeNode | None:
    """LC-226 翻转二叉树：交换每个节点的左右子树"""
    if not root:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

def level_order(root: TreeNode | None) -> list[list[int]]:
    """LC-102 层序遍历：按层分组
    时间 O(n)，空间 O(n)
    """
    from collections import deque
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(max_depth(root))

3

root = TreeNode(4,
                TreeNode(2, TreeNode(1), TreeNode(3)),
                TreeNode(7, TreeNode(6), TreeNode(9)))
print(level_order(invert_tree(root)))

[[4], [7, 2], [9, 6, 3, 1]]

from collections import deque

def bfs_shortest_path(graph: dict, start: int, end: int) -> int:
    """无权图最短路；不可达返回 -1
    时间 O(V + E)，空间 O(V)
    """
    if start == end:
        return 0
    visited = {start}
    queue = deque([(start, 0)])
    while queue:
        node, dist = queue.popleft()
        for neighbor in graph[node]:
            if neighbor == end:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)  # 入队时立即标记
                queue.append((neighbor, dist + 1))
    return -1

def topological_sort(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    """拓扑排序：每次入队 0 入度节点，处理时邻居入度减一
    时间 O(V + E)，空间 O(V + E)；存在环时返回 []
    """
    from collections import deque, defaultdict
    in_degree = [0] * num_courses
    graph = defaultdict(list)
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return result if len(result) == num_courses else []

def num_islands(grid: list[list[str]]) -> int:
    """LC-200 岛屿数量：遍历到 '1' 即计数并把整座岛沉为 '0'
    时间 O(mn)，空间 O(mn) 最坏递归深度
    """
    rows, cols = len(grid), len(grid[0])

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

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                dfs(r, c)
    return count

grid = [["1", "1", "0", "0", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "1", "0", "0"],
        ["0", "0", "0", "1", "1"]]
print(num_islands(grid))

3

print(topological_sort(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))
print(topological_sort(2, [[1, 0], [0, 1]]))

[0, 1, 2, 3]
[]

while queue:
    node = queue.popleft()
    result.append(node)
    for neighbor in graph[node]:
        queue.append(neighbor)  # 错误：有环时死循环

def climb_stairs(n: int) -> int:
    """状态：dp[i] = 爬到第 i 阶的方法数
    转移：dp[i] = dp[i-1] + dp[i-2]；初始：dp[0] = dp[1] = 1
    时间 O(n)，空间 O(1)（滚动变量）
    """
    if n <= 2:
        return n
    prev, curr = 1, 2
    for _ in range(3, n + 1):
        prev, curr = curr, prev + curr
    return curr

def rob_brute(nums):
    # 1. 暴力递归 O(2^n) - TLE
    def dfs(i):
        if i >= len(nums):
            return 0
        return max(dfs(i + 1), dfs(i + 2) + nums[i])
    return dfs(0)

def rob_memo(nums):
    # 2. 记忆化 O(n) - AC
    from functools import lru_cache
    @lru_cache(None)
    def dfs(i):
        if i >= len(nums):
            return 0
        return max(dfs(i + 1), dfs(i + 2) + nums[i])
    return dfs(0)

def rob_optimal(nums):
    # 3/4. 迭代 DP O(n)，再压缩为滚动变量 O(1) 空间 - 最优解
    prev, curr = 0, 0
    for num in nums:
        prev, curr = curr, max(curr, prev + num)
    return curr

def longest_common_subsequence(text1: str, text2: str) -> int:
    """状态：dp[i][j] = text1[:i] 与 text2[:j] 的 LCS 长度
    时间 O(mn)，空间 O(mn)，可压缩为 O(min(m, n))
    """
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

def edit_distance(word1: str, word2: str) -> int:
    """LC-72 Hard：word1[:i] 转为 word2[:j] 的最少操作数
    转移：相同则继承对角线；否则 1 + min(删除, 插入, 替换)
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i  # 边界：删光前 i 个字符
    for j in range(n + 1):
        dp[0][j] = j  # 边界：插入 j 个字符
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 编辑距离 C++ 实现
int editDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i-1] == word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
            }
        }
    }
    return dp[m][n];
}

print(climb_stairs(3))
print(climb_stairs(5))

3
8

print(longest_common_subsequence("abcde", "ace"))
print(longest_common_subsequence("abc", "def"))
print(edit_distance("horse", "ros"))

3
0
3

def permute(nums: list[int]) -> list[list[int]]:
    """全排列通用模板：做选择 -> 递归 -> 撤销选择
    时间 O(n * n!)，空间 O(n)
    """
    result = []

    def backtrack(path: list[int]):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for choice in nums:
            if choice in path:  # 剪枝：已使用
                continue
            path.append(choice)
            backtrack(path)
            path.pop()

    backtrack([])
    return result

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    """LC-39 组合总和：start 参数避免重复组合，i 可重复使用"""
    result = []

    def backtrack(start: int, path: list[int], remaining: int):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                continue  # 剪枝（需候选有序时更有效）
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # i 而非 i+1：可重复
            path.pop()

    backtrack(0, [], target)
    return result

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    """LC-90 子集 II：排序后同层去重"""
    nums.sort()
    result = []

    def backtrack(start: int, path: list[int]):
        result.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue  # 同层去重
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

print(permute([1, 2, 3]))

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

print(combination_sum([2, 3, 6, 7], 7))
print(subsets_with_dup([1, 2, 2]))

[[2, 2, 3], [7]]
[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

def count_bits(n: int) -> list[int]:
    """LC-338 比特位计数：n & (n-1) 去掉最低位 1
    时间 O(n)
    """
    result = [0] * (n + 1)
    for i in range(1, n + 1):
        result[i] = result[i & (i - 1)] + 1
    return result

print(count_bits(5))

[0, 1, 1, 2, 1, 2]

class DLinkedNode:
    """双向链表节点"""
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    """LRU 缓存：哈希表 + 双向链表，get/put 均摊 O(1)"""

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> DLinkedNode
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_node(self, node: DLinkedNode) -> None:
        """在头部之后插入（表示最近使用）"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node: DLinkedNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _move_to_head(self, node: DLinkedNode) -> None:
        self._remove_node(node)
        self._add_node(node)

    def _pop_tail(self) -> DLinkedNode:
        node = self.tail.prev
        self._remove_node(node)
        return node

    def get(self, key: int) -> int:
        node = self.cache.get(key)
        if not node:
            return -1
        self._move_to_head(node)  # 访问即移至头部
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.cache.get(key)
        if node:
            node.value = value
            self._move_to_head(node)
        else:
            if len(self.cache) >= self.capacity:
                tail = self._pop_tail()  # 淘汰最久未使用
                del self.cache[tail.key]
            new_node = DLinkedNode(key, value)
            self.cache[key] = new_node
            self._add_node(new_node)

class UnionFind:
    """并查集：路径压缩 + 按秩合并
    find/union 均摊 O(alpha(n)) 约等于 O(1)，基于 Tarjan 1975 分析
    """

    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # 连通分量数

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

    def union(self, x: int, y: int) -> bool:
        """按秩合并；返回是否成功合并（原本不同集合）"""
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.count -= 1
        return True

def find_redundant_connection(edges: list[list[int]]) -> list[int]:
    """LC-684 冗余连接：第一条连接同集合的边即冗余
    应用：K8s 网络策略循环依赖检测。时间 O(E alpha(V))
    """
    uf = UnionFind(len(edges) + 1)
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]
    return []

print(find_redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4]]))

[1, 4]

from collections import deque

def sliding_window_max(nums: list[int], k: int) -> list[int]:
    """LC-239 滑动窗口最大值：单调队列存索引，对应值单调递减
    时间 O(n)，空间 O(k)
    """
    queue = deque()  # 存索引
    result = []
    for i, x in enumerate(nums):
        while queue and nums[queue[-1]] <= x:
            queue.pop()  # 维护单调递减
        queue.append(i)
        if queue[0] <= i - k:  # 移除窗口外元素
            queue.popleft()
        if i >= k - 1:
            result.append(nums[queue[0]])
    return result

print(sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))

[3, 3, 5, 5, 6, 7]

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    """Trie 字典树：插入/查找 O(L)，L 为词长"""

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

class SensitiveWordFilter:
    """敏感词过滤器：Trie 前缀剪枝替代逐词暴力匹配"""

    def __init__(self, words: list[str]):
        self.trie = Trie()
        for word in words:
            self.trie.insert(word.lower())

    def filter(self, text: str, replace_char: str = "*") -> str:
        text_lower = text.lower()
        result = list(text)
        n = len(text_lower)
        for i in range(n):
            node = self.trie.root
            j = i
            while j < n and text_lower[j] in node.children:
                node = node.children[text_lower[j]]
                j += 1
                if node.is_end:
                    for k in range(i, j):
                        result[k] = replace_char
        return "".join(result)

filter = SensitiveWordFilter(["spam", "abuse", "violence"])
print(filter.filter("This is SPAM content with abuse words"))

This is **** content with ***** words

from collections import deque

def right_side_view(root) -> list[int]:
    """LC-199 右侧视图：层序遍历取每层最后一个节点。时间 O(n)"""
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return result

root = TreeNode(1, TreeNode(2, None, TreeNode(5)), TreeNode(3))
print(right_side_view(root))

[1, 3, 5]

import random

def find_kth_largest(nums: list[int], k: int) -> int:
    """QuickSelect：随机 pivot，平均 O(n)，最坏 O(n^2)"""
    target_index = len(nums) - k

    def quick_select(left: int, right: int) -> int:
        pivot_index = random.randint(left, right)  # 随机化避免最坏情况
        nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
        pivot = nums[right]
        i = left
        for j in range(left, right):
            if nums[j] <= pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[right] = nums[right], nums[i]
        if i == target_index:
            return nums[i]
        elif i < target_index:
            return quick_select(i + 1, right)
        else:
            return quick_select(left, i - 1)

    return quick_select(0, len(nums) - 1)

def top_k_elements(nums: list[int], k: int) -> list[int]:
    """工业版 Top-K：堆实现，稳定 O(n log k)"""
    import heapq
    return heapq.nlargest(k, nums)

print(top_k_elements([3, 2, 1, 5, 6, 4], 2))

[6, 5]

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return -1

def lengthOfLongestSubstring(s: str) -> int:
    window = set()
    left = 0
    ans = 0
    for right, ch in enumerate(s):
        while ch in window:
            window.remove(s[left])
            left += 1
        window.add(ch)
        ans = max(ans, right - left)
    return ans

def numIslands(grid: list[list[str]]) -> int:
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count