LeetCode 高频算法题梳理：Java 面试常见解法

• 常用解法：
  1. 排序法：排序后直接取中间位置元素。
  2. 快速选择：类似快速排序分区，找第 n/2 大元素。
  3. 堆方法：维护最大堆和最小堆，保持平衡。
  4. 分治法：分别找左半部分最大值和右半部分最小值。
• 核心要点：不同方法效率各有优劣，依场景选择。

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 更像'沿着一条路先走到底'。在树和图里都很常用，尤其适合连通性、路径和枚举类问题。

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

14. 广度优先搜索（BFS）

BFS 的特点是按层推进，最适合处理最短路和层序遍历。它比 DFS 更'平'，但在一些题里反而更直接。

• 树上的 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. 找到数组中的众数（摩尔投票法）

摩尔投票法的思路挺巧：把不同元素相互抵消，最后留下来的那个，大概率就是答案。它的好处是常数空间，不靠额外容器。

• 步骤解析：
  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）

LCS 是二维动态规划里很有代表性的一类题。它不要求连续，但要求顺序一致，所以状态设计和转移都比较标准。

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

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

BST 的中序遍历天然是递增序列，所以第 k 小元素直接数着找就行，不用把整棵树都处理完。

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

25. 数组中第 k 大的元素

第 k 大元素一般有三种解法：排完再取、维护一个堆、或者直接快速选择。面试里如果题目没限制输入规模，快速选择通常是最值得优先想到的方案。

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