核心内容整理
一、序章
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
- N-Queens：回溯法 + 剪枝，处理皇后不共行、列、对角线的约束。
总结
该文档是 LeetCode 刷题的系统指南，涵盖基础理论、算法专题、实用模板及 700 道题的最优解，适合通过刷题提升算法能力的读者，尤其适合使用 Go 语言的开发者。内容注重实战与优化，强调对算法思想的理解与灵活应用。
关注微信公众号“人工智能产业链union”回复关键字“AI加油站48”获取下载地址。
【AI加油站】第八部：《模式识别（第四版）-模式识别与机器学习》（附下载）
