[高频题库 50 题]
        |
        v
[题型分类与知识图谱]
        |
        +--------------------------------------------------+
        |                  |                 |              |
        v                  v                 v              v
  [数组与字符串]      [链表与递归]       [树与图]      [动态规划]
   (双指针, 滑动      (快慢指针,        (DFS/BFS,    (背包, 最优
    窗口, 二分        递归反转,          遍历, 拓扑   子结构, 状态
    查找等)           合并等)            排序等)       转移方程)
        |                  |                 |              |
        +------------------+-----------------+--------------+
                           |
                           v
                   [标准化解题流程]
                           |
                           v
        [审题->分析->选择策略->编码->测试]
                           |
                           v
                   [代码模板库 & 最佳实践]
                           |
                           v
                [面试模拟与实战演练]

def threeSum(nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    nums.sort()  # 步骤1：排序
    n = len(nums)
    result = []

    for i in range(n):
        # 跳过重复的第一个数
        if i > 0 and nums[i] == nums[i-1]:
            continue

        # 双指针查找另外两个数
        left, right = i + 1, n - 1
        target = -nums[i]  # 我们要找 nums[left] + nums[right] == target

        while left < right:
            current_sum = nums[left] + nums[right]
            if current_sum == target:
                # 找到一个解，加入结果
                result.append([nums[i], nums[left], nums[right]])

                # 移动指针并跳过重复元素
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif current_sum < target:
                # 和太小，左指针右移
                left += 1
            else:
                # 和太大，右指针左移
                right -= 1

    return result

# 测试
print(threeSum([-1,0,1,2,-1,-4])) # [[-1,-1,2],[-1,0,1]]

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

def mergeTwoLists(l1, l2):
    # 创建哨兵节点
    dummy = ListNode(-1)
    tail = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    # 拼接剩余部分
    tail.next = l1 if l1 else l2
    return dummy.next

# 辅助函数：用于构建和打印链表
def build_list(vals):
    if not vals:
        return None
    head = ListNode(vals[0])
    current = head
    for val in vals[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

def print_list(head):
    vals = []
    while head:
        vals.append(str(head.val))
        head = head.next
    print(" -> ".join(vals) if vals else "Empty")

# 测试
l1 = build_list([1, 2, 4])
l2 = build_list([1, 3, 4)
merged_head = mergeTwoLists(l1, l2)
print_list(merged_head) # 1 -> 1 -> 2 -> 3 -> 4 -> 4

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def lowestCommonAncestor(root, p, q):
    """
    :type root: TreeNode
    :type p: TreeNode
    :type q: TreeNode
    :rtype: TreeNode
    """
    # 基本情况：空节点或找到目标节点
    if root is None or root == p or root == q:
        return root

    # 后序遍历：先在左右子树中找
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)

    # 判断逻辑
    if left and right:
        # p 和 q 分居两侧，当前 root 是 LCA
        return root
    elif left:
        # p 和 q 都在左子树，返回左子树的结果
        return left
    else:
        # p 和 q 都在右子树，或只在右侧找到一个
        return right

# 构建测试树 (LeetCode 示例)
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
p = root.left  # 节点5
q = root.right # 节点1
lca_node = lowestCommonAncestor(root, p, q)
print(f"LCA of {p.val} and {q.val} is {lca_node.val}") # 输出 3

from collections import deque

def canFinish(numCourses, prerequisites):
    """
    :type numCourses: int
    :type prerequisites: List[List[int]]
    :rtype: bool
    """
    # 步骤1：构建邻接表和入度表
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for a, b in prerequisites: # a 的先决条件是 b，即 b -> a
        graph[b].append(a)
        indegree[a] += 1

    # 步骤2：初始化队列，将所有入度为0的节点入队
    queue = deque()
    for i in range(numCourses):
        if indegree[i] == 0:
            queue.append(i)

    # 步骤3：BFS 拓扑排序
    count = 0 # 记录已遍历的节点数
    while queue:
        node = queue.popleft()
        count += 1
        # 遍历当前节点的所有邻接节点
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    # 步骤4：判断是否所有节点都被访问
    return count == numCourses

# 测试
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # False

def lengthOfLIS(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 0

    n = len(nums)
    dp = [1] * n  # 初始化：每个元素自身就是长度为1的子序列

    # 遍历每个位置
    for i in range(1, n):
        # 查找在 i 之前，且比 nums[i] 小的元素
        for j in range(i):
            if nums[j] < nums[i]:
                # 状态转移
                dp[i] = max(dp[i], dp[j] + 1)

    # 返回 dp 数组中的最大值
    return max(dp)

# 测试
print(lengthOfLIS([10,9,2,5,3,7,101,18])) # 4 ([2,3,7,101] 或 [2,5,7,101] 等)

leetcode-high-frequency-50/
├── README.md                 # 项目总览和学习路线
├── solutions/
│   ├── array/                # 数组与字符串
│   │   ├── two_sum.py
│   │   ├── three_sum.py
│   │   ├── container_with_most_water.py
│   │   └── ...
│   ├── linked_list/          # 链表
│   │   ├── reverse_linked_list.py
│   │   ├── merge_two_sorted_lists.py
│   │   ├── linked_list_cycle.py
│   │   └── ...
│   ├── tree/                 # 二叉树
│   │   ├── invert_binary_tree.py
│   │   ├── maximum_depth_of_binary_tree.py
│   │   ├── lowest_common_ancestor.py
│   │   └── ...
│   ├── graph/                # 图论
│   │   ├── number_of_islands.py
│   │   ├── course_schedule.py
│   │   └── ...
│   ├── dp/                   # 动态规划
│   │   ├── climbing_stairs.py
│   │   ├── coin_change.py
│   │   ├── longest_increasing_subsequence.py
│   │   └── ...
│   └── templates/            # 通用代码模板
│       ├── binary_tree_dfs.py
│       ├── bfs_template.py
│       ├── sliding_window.py
│       └── dp_template.py
└── notes/
    ├── patterns.md           # 解题模式总结
    └── complexity.md         # 复杂度分析笔记