Java 程序员必读：LeetCode 热门算法核心精讲

6. 在旋转排序数组中搜索

结合二分查找与旋转特性。

• 步骤解析：
  1. 找到旋转点：修改后的二分查找确定最小元素位置。
  2. 确定搜索区间：分为两个有序部分，判断目标所在区间。
  3. 二分查找：在确定的有序区间内标准查找。
  4. 处理边界：注意索引环绕等边界条件。
• 核心要点：时间复杂度 O(log n)，空间 O(1)。

三、数据结构专项

7. 链表反转

经典问题，就地修改指针方向。

• 步骤解析：
  1. 初始化三个指针：prev (null), curr (头节点), next。
  2. 遍历链表：逐个节点反转。
  3. 反转指针：curr.next 指向 prev。
  4. 移动指针：prev 移至 curr, curr 移至 next。
  5. 处理新的头节点：遍历结束后 prev 为新头节点。
• 核心要点：指针操作实现就地反转，无需额外空间。

8. 判断链表中是否有环

快慢指针技巧高效检测。

• 步骤解析：
  1. 使用快慢指针：slow 走一步，fast 走两步。
  2. 移动指针：检查是否相遇。
  3. 检测环：若相遇则存在环。
  4. 考虑边界情况：检查 fast 及其 next 是否为空。
• 核心要点：时间 O(n)，空间 O(1)。

9. 复制带随机指针的链表

深拷贝关键在于正确处理随机指针。

• 步骤解析：
  1. 复制节点：第一次遍历创建新节点，复制值。
  2. 存储映射关系：哈希表存原节点与新节点对应关系。
  3. 复制随机指针：第二次遍历根据哈希表更新随机指针。
  4. 拆分链表：分离新旧链表，返回新头节点。
• 核心要点：哈希表建立映射，空间复杂度 O(n)。

四、算法思想与应用

10. 动态规划 (斐波那契数列)

递推构建最优解的典型入门案例。

• 步骤解析：
  1. 定义状态：dp[i] 表示第 i 个斐波那契数。
  2. 状态转移方程：dp[i] = dp[i-1] + dp[i-2]。
  3. 初始化状态：dp[0] = 0, dp[1] = 1。
  4. 填充动态规划表：循环计算 dp[2] 到 dp[n]。
  5. 解决问题：dp[n] 即为所求。
• 核心要点：可用两个变量替代数组，空间降至 O(1)。

11. 贪心算法 (会议室预定)

每次选结束时间最早且不与已选会议重叠的会议。

• 步骤解析：
  1. 排序会议：按结束时间升序排序。
  2. 选择会议：选结束最早的作为第一个。
  3. 更新时间：当前时间更新为该会议结束时间。
  4. 重复选择：选下一个开始时间不早于当前时间的会议。
  5. 考虑重叠：确保新会议开始时间 >= 上次结束时间。
• 核心要点：局部最优（选结束最早）达到全局最优。

12. 回溯算法 (八皇后)

尝试每一种可能布局寻找合法解。

• 步骤解析：
  1. 定义棋盘：N x N 棋盘记录位置。
  2. 放置皇后：逐行尝试每一列。
  3. 检查冲突：验证同列、同对角线冲突。
  4. 递归与回溯：合法则递归下一行，否则回溯重试。
  5. 找到解：最后一行放置成功则记录，继续回溯。
• 核心要点：系统搜索所有候选解，发现不可行及时退回。

13. 深度优先搜索 (DFS)

尽可能深地探索树的分支。

• 树上的 DFS 实现：
  1. 递归实现：访问当前节点，递归左右子树。
  2. 栈的使用：手动压栈弹栈模拟递归。
  3. 前/中/后序遍历：根左右、左根右、左右根。
• 图上的 DFS 实现：
  1. 使用栈或递归：管理遍历顺序。
  2. 标记已访问：避免重复访问和循环。
  3. 遍历邻接节点：递归执行未访问邻接节点。
  4. 探索路径：深入分支直至末端。
• 核心要点：适用于路径搜索、连通性检测。

14. 广度优先搜索 (BFS)

按层遍历，常用于最短路径。

• 树上的 BFS (层序遍历)：
  1. 使用队列：保证按层访问。
  2. 根节点入队：起始放入队列。
  3. 节点出队遍历：访问并加入左右子节点。
  4. 重复过程：直到队列为空。
  5. 按层访问：记录队列大小确保一次处理一层。
• 图上的 BFS 实现：
  1. 使用队列：存储待访问节点。
  2. 起始节点入队：放入起点。
  3. 节点出队遍历：访问并加入未访问邻接节点。
  4. 标记已访问：防止重复入队。
  5. 按层次遍历：一层层向外扩展。
• 核心要点：无权图最短路径或层次遍历。

五、数组与字符串技巧

15. 数组去重

利用集合特性轻松实现。

• 步骤解析：
  1. 使用 HashSet：自动去除重复元素。
  2. 遍历数组：添加元素到 Set。
  3. 转换为数组：转回数组或列表。
  4. 保持顺序：用 LinkedHashSet 代替 HashSet。
• 核心要点：实现简单，但增加 O(n) 空间。

16. 寻找数组交集

哈希集合快速找出交集。

• 步骤解析：
  1. 使用 HashSet 存储：遍历第一个数组存入 Set。
  2. 查找交集：遍历第二个数组检查是否在 Set 中。
  3. 收集结果：存在则加入结果集。
  4. 去重复：Set 自然去重。
• 核心要点：时间 O(m+n)，需额外空间。

17. 找到数组中的众数 (摩尔投票法)

空间 O(1) 找出超过一半的元素。

• 步骤解析：
  1. 初始化：candidate 为首元素，count = 1。
  2. 遍历数组：从第二个元素开始。
  3. 增减计数：相等 count++，不等 count--。
  4. 更新候选者：count 为 0 时重置 candidate。
  5. 找到候选者：遍历结束 candidate 为候选。
  6. 验证众数：再次遍历验证次数是否超一半。
• 核心要点：利用数量优势抵消非众数影响。

18. 数组旋转

反转特定部分实现旋转。

• 步骤解析：
  1. 确定旋转次数：k = k % n。
  2. 反转整个数组：先整体反转。
  3. 反转部分数组：前 k 个和剩余部分分别反转。
  4. 合并结果：完成右旋 k 步。
• 核心要点：三次反转实现 O(1) 空间。

19. 判断回文字符串

双指针法高效判断。

• 步骤解析：
  1. 双指针法：left 开头，right 末尾。
  2. 忽略非字母数字：跳过空格标点。
  3. 大小写不敏感：统一转换大小写。
  4. 向中间移动并比较：left < right 时比较，不等则非回文。
  5. 结束判断：循环结束说明是回文。
• 核心要点：时间 O(n)，空间 O(1)。

20. 字符串的全排列

回溯法生成所有可能排列。

• 步骤解析：
  1. 回溯法：递归遍历组合。
  2. 字符选择：从剩余字符选一个。
  3. 排除重复：标记已使用相同字符避免重复排列。
  4. 递归组合：加入路径，标记使用，递归处理剩余。
  5. 还原状态：返回后移除字符，取消标记。
• 核心要点：标准范式，关键在于正确选择和撤销。

21. 最小覆盖子串

滑动窗口法解决。

• 步骤解析：
  1. 滑动窗口法：左右指针维护动态窗口。
  2. 字符计数：统计目标字符需求和拥有量。
  3. 窗口调整：右移扩大，包含所有字符后左移缩小。
  4. 更新结果：满足条件时更新最小子串信息。
  5. 效率与准确性：精确控制窗口，O(n) 时间。
• 核心要点：动态窗口记录有效状态。

22. 判断快乐数

涉及循环检测，快慢指针解决。

• 步骤解析：
  1. 数字变换：计算各位数字平方和。
  2. 快慢指针技巧：视为隐式链表，slow 一次变换，fast 两次。
  3. 判断条件：变为 1 则是快乐数。
  4. 检测循环：相遇且不为 1 则进入循环。
• 核心要点：避免 HashSet，空间 O(1)。

六、其他经典问题

23. 最长公共子序列 (LCS)

二维动态规划衡量相似度。

• 步骤解析：
  1. 定义动态规划表：dp[i][j] 表示 LCS 长度。
  2. 初始化边界：空串 LCS 长度为 0。
  3. 填表计算：字符相等则 +1，否则取最大值。
  4. 回溯构造序列：从 dp[m][n] 回溯构造。
  5. 优化空间复杂度：滚动数组优化至 O(min(m, n))。
• 核心要点：体现动态规划处理字符串比较能力。

24. 二叉搜索树中第 k 小的元素

中序遍历结果为递增序列。

• 步骤解析：
  1. 中序遍历：BST 中序遍历。
  2. 计数访问：计数器记录已访问个数。
  3. 找到第 k 个元素：计数器到 k 时即为所求。
  4. 递归或迭代：可提前终止。
• 核心要点：时间 O(k)，最坏 O(n)。

25. 数组中第 k 大的元素

多种解法适用不同场景。

• 常用解法：
  1. 排序后选择：排序选索引 n-k，O(n log n)。
  2. 使用优先队列：大小为 k 的最小堆，O(n log k)。
  3. 快速选择：分区思想，平均 O(n)，最坏 O(n²)。
• 核心要点：快速选择平均最优，堆方法适合数据流。