核心内容整理

一、序章

1. 书籍背景

• 关于 LeetCode
  ：作为程序员面试刷题平台，2011 年成立，通过周赛、双周赛等考验算法能力，优秀成绩可获企业内推。
• 关于 Cookbook
  ：类比 “烹饪书”，侧重实践操作，适合动手学习算法。
• 写作原因
  ：作者刷题一年后分享心得，通过讲解深化理解，同时与同行交流；作者有 3 年 ACM-ICPC 经历，2019-2020 年完成 600 + 题，计划向 1000 题或多轮刷题推进。
• 使用说明
  ：建议先自主思考（15 分钟无思路再看解题思路），实现后自行优化至最优性能，再参考代码；支持通过 GitHub 提交修改建议。

2. 基础预备知识

• 数据结构知识
  ：涵盖线性表（向量、链表）、哈希表、栈和队列（双端队列、优先队列）、字符串（KMP、BM 算法）、树（二叉树、并查集、哈夫曼树）、堆（极大堆、二项式堆）、查找结构（红黑树、Trie 树）等，及各类变种和相关题目。
• 算法知识
  ：包括排序算法（快排、归并、桶排）、递归与分治（二分搜索、矩阵乘法）、动态规划（最长公共子序列、背包问题）、贪心（活动安排、哈夫曼编码）、回溯法（N 皇后、子集问题）、搜索（DFS、BFS、启发式搜索）、图论（最短路径、最小生成树）、数论（最大公约数、素数判定）等，及对应应用场景。

二、时间复杂度与空间复杂度

• 时间复杂度数据规模
  ：1 秒内可处理的数据规模约为 10⁶~10⁷；O (n²) 适合 10⁴级，O (n) 适合 10⁸级，O (nlogn) 适合 10⁷级。
• 空间复杂度
  ：递归调用需考虑栈空间，非递归算法通常空间更优。
• 递归时间复杂度
  ：单次递归调用为 O (T×depth)（T 为单次操作复杂度，depth 为递归深度）；多次递归调用需通过递归树分析（如斐波那契递归为 O (2ⁿ)）。

三、算法专题

按题型分类，整理核心解题思路与典型题目：

• Array
  ：包括数组去重、旋转、搜索（旋转数组）、最大子数组和等，如 “Two Sum”“Container With Most Water”。
• String
  ：字符串匹配、最长回文子串、字符编码转换等，如 “Longest Palindromic Substring”“String to Integer (atoi)”。
• Two Pointers
  ：双指针滑动窗口（最长无重复子串）、快慢指针（找环）、左右指针（三数之和）等，如 “3Sum”“Minimum Window Substring”。
• Linked List
  ：链表反转、合并、环检测等，如 “Add Two Numbers”“Merge k Sorted Lists”。
• Stack
  ：括号匹配、单调栈（最大矩形面积）等，如 “Valid Parentheses”“Largest Rectangle in Histogram”。
• Tree
  ：二叉树遍历、构建、路径和等，如 “Binary Tree Inorder Traversal”“Lowest Common Ancestor”。
• Dynamic Programming
  ：子序列问题、背包问题、最长递增子序列等，如 “Maximum Subarray”“Coin Change”。
• Backtracking
  ：排列组合、子集、N 皇后等，如 “Permutations”“Combination Sum”。
• Binary Search
  ：二分查找变种（找第一个 / 最后一个匹配元素）、旋转数组搜索等，如 “Search in Rotated Sorted Array”“Find Minimum in Rotated Sorted Array”。
• 其他专题
  ：哈希表（计数、去重）、位操作（异或、位运算特性）、并查集（连通分量）、滑动窗口（子数组问题）、线段树（区间查询与更新）等。

四、常用模板

• 线段树（Segment Tree）
  ：用于区间查询与更新（求和、最值），支持单点更新、区间更新（懒查询优化），时间复杂度 O (logn)。
• 并查集（UnionFind）
  ：路径压缩 + 秩优化实现，用于处理连通性问题，支持集合合并与查询。
• LRUCache
  ：最近最少使用缓存，通过哈希表 + 双向链表实现，Get 和 Put 操作均为 O (1)。
• LFUCache
  ：最不经常使用缓存，通过哈希表 + 频率链表实现，优化访问频率较低元素的淘汰。

五、LeetCode 题解

包含 700 道题的详细解析，每题结构为：

• 题目描述
  ：原题要求。
• 题目大意
  ：简化问题核心。
• 解题思路
  ：算法设计与优化思路（如暴力、动态规划、双指针等）。
• 代码实现
  ：Go 语言代码，确保性能最优（beats 100%）。

典型题目示例：

• Two Sum
  ：用哈希表存储已遍历元素，一次遍历找到目标和，时间 O (n)。
• Longest Palindromic Substring
  ：中心扩散法或 Manacher 算法，时间 O (n²) 或 O (n)。
• Merge k Sorted Lists
  ：分治合并，时间 O (nlogk)。
• N-Queens
  ：回溯法 + 剪枝，处理皇后不共行、列、对角线的约束。

总结

该文档是 LeetCode 刷题的系统指南，涵盖基础理论、算法专题、实用模板及 700 道题的最优解，适合通过刷题提升算法能力的读者，尤其适合使用 Go 语言的开发者。内容注重实战与优化，强调对算法思想的理解与灵活应用。

【AI加油站】第八部：《模式识别（第四版）-模式识别与机器学习》（附下载）