Java LeetCode 热门算法精讲

5. 寻找无序数组的中位数

对于无序数组，可以通过多种算法高效地找到中位数。

• 常用解法：
  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. 检测环：如果在移动过程中 fast 与 slow 相遇（指向同一节点），则链表存在环。
  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] 即为所求的第 n 个斐波那契数。
• 核心要点：可以通过只使用两个变量来替代数组，优化存储空间，将空间复杂度降至 O(1)。

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

贪心算法在解决会议室预定时，通过每次选择结束时间最早且不与已选会议重叠的会议，来安排最多的会议。

• 步骤解析：
  1. 排序会议：首先按照会议的结束时间对所有会议进行升序排序。
  2. 选择会议：从排好序的列表中选择结束时间最早的会议作为第一个会议。
  3. 更新时间：选择会议后，将当前时间更新为该会议的结束时间。
  4. 重复选择：继续选择下一个开始时间不早于当前时间，且结束时间最早的会议。
  5. 考虑重叠：在选择过程中，确保新选的会议开始时间大于等于上次会议的结束时间。
• 核心要点：通过局部最优选择（每次选结束最早且可行的会议），最终达到全局最优解。

12. 回溯算法 (八皇后)

八皇后问题是回溯算法的经典应用，通过尝试每一种可能的布局来寻找所有合法的解决方案。

• 步骤解析：
  1. 定义棋盘：初始化一个 N x N 的棋盘（通常用数组表示），用于记录皇后的位置。
  2. 放置皇后：从第一行开始，逐行尝试在每一列放置皇后。
  3. 检查冲突：验证当前放置的皇后是否与已放置的皇后在同一列、同一对角线（主对角线和副对角线）上。
  4. 递归与回溯：如果当前位置合法，则递归地放置下一行的皇后；如果导致后续无法放置，则回溯到上一行，将皇后移动到下一列重新尝试。
  5. 找到解：当成功在最后一行放置皇后时，记录当前棋盘布局，然后继续回溯寻找其他解。
• 核心要点：回溯法系统地搜索所有可能的候选解，并在发现当前路径不可能产生合法解时及时退回。

13. 深度优先搜索 (DFS)

DFS 是一种用于遍历或搜索树或图的算法，它会尽可能深地探索树的分支。

• 树上的 DFS 实现：
  1. 递归实现：利用递归函数，先访问当前节点，然后递归地对左子树和右子树调用 DFS。
  2. 栈的使用：使用栈来模拟递归过程，手动将节点压栈和弹栈来管理遍历顺序。
  3. 前/中/后序遍历：
     • 前序遍历：访问根节点 -> 遍历左子树 -> 遍历右子树。
     • 中序遍历：遍历左子树 -> 访问根节点 -> 遍历右子树。
     • 后序遍历：遍历左子树 -> 遍历右子树 -> 访问根节点。
• 图上的 DFS 实现：
  1. 使用栈或递归：通过栈或递归函数实现遍历。
  2. 标记已访问：访问一个节点时，需要将其标记为已访问，避免重复访问和陷入循环。
  3. 遍历邻接节点：对当前节点的所有未访问邻接节点递归执行 DFS。
  4. 探索路径：深入每一个可能的分支，直到达到末端或所有可达节点都已访问。
• 核心要点：DFS 适用于需要深入到叶子节点或探索所有可能路径的问题，如路径搜索、连通性检测。

14. 广度优先搜索 (BFS)

BFS 是一种按层遍历树或图的算法，常用于寻找最短路径。

• 树上的 BFS (层序遍历) 实现：
  1. 使用队列：利用队列先进先出的特性来保证按层访问。
  2. 根节点入队：首先将根节点放入队列。
  3. 节点出队遍历：节点出队时，访问该节点，并将其左右子节点（如果存在）依次入队。
  4. 重复过程：继续上述过程，直到队列为空。
  5. 按层访问：可以通过在每次循环开始时记录当前队列的大小，来确保一次处理一层的所有节点。
• 图上的 BFS 实现：
  1. 使用队列：BFS 利用队列存储待访问的节点。
  2. 起始节点入队：首先将起始节点放入队列中。
  3. 节点出队遍历：节点出队时，访问该节点，并将其所有未访问过的邻接节点入队。
  4. 标记已访问：在节点入队或出队时，将其标记为已访问，防止重复入队。
  5. 按层次遍历：通过队列的特性，实现从起点开始，一层一层向外扩展的遍历。
• 核心要点：BFS 是图的基本算法之一，特别适用于在无权图中寻找最短路径或进行层次遍历。

五、数组与字符串技巧

15. 数组去重

利用集合（如 HashSet）的特性可以轻松实现数组去重。

• 步骤解析：
  1. 使用 HashSet：利用 HashSet 自动去除重复元素的特性。
  2. 遍历数组：将数组中的每个元素添加到 HashSet 中，重复的元素不会被加入。
  3. 转换为数组：遍历结束后，将 HashSet 中的元素转换回数组或列表，得到去重后的结果。
  4. 保持顺序：如果需要保持原数组的元素顺序，可以使用 LinkedHashSet 代替 HashSet。
• 核心要点：此方法实现简单，但会增加 O(n) 的空间复杂度，应根据实际情况权衡。

16. 寻找数组交集

通过哈希集合可以快速找出两个数组的交集。

• 步骤解析：
  1. 使用 HashSet 存储：遍历第一个数组，将其所有元素存储到一个 HashSet 中。
  2. 查找交集：遍历第二个数组，对于每个元素，检查它是否在第一步创建的 HashSet 中。
  3. 收集结果：如果存在，则将该元素加入到结果集（另一个 HashSet 或直接加入结果列表并进行后续去重）。
  4. 去重复：由于使用了 HashSet，交集中的元素自然被去重。
• 核心要点：此方法时间复杂度较低（O(m+n)），但需要额外的空间存储 HashSet。

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

摩尔投票法是一种空间复杂度为 O(1) 的算法，用于找出数组中出现次数超过一半的元素。

• 步骤解析：
  1. 初始化：选定数组的第一个元素作为候选众数 candidate，并初始化计数 count = 1。
  2. 遍历数组：从第二个元素开始遍历数组。
  3. 增减计数：如果当前元素等于 candidate，则 count++；否则 count--。
  4. 更新候选者：如果 count 变为 0，则将下一个元素设为新的 candidate，并将 count 重置为 1。
  5. 找到候选者：遍历完成后，candidate 即为所求的众数候选。
  6. 验证众数：为了确保正确性，通常需要再次遍历数组，验证 candidate 的出现次数是否真的超过一半。
• 核心要点：算法的有效性在于利用众数数量优势，通过计数抵消非众数元素的影响。

18. 数组旋转

通过反转数组的特定部分，可以高效地实现数组旋转。

• 步骤解析：
  1. 确定旋转次数：对数组长度取模，得到实际需要旋转的有效步数 k = k % n，因为旋转整数倍长度等于没转。
  2. 反转整个数组：先将整个数组反转。
  3. 反转部分数组：将数组分为两部分：前 k 个元素和剩余元素，并分别对这两部分进行反转。
  4. 合并结果：两部分反转后，整个数组即完成了右旋 k 步的效果。
• 核心要点：通过三次反转实现 O(1) 额外空间的数组旋转，是一种非常巧妙的解法。

19. 判断回文字符串

使用双指针法可以高效地判断一个字符串是否为回文串。

• 步骤解析：
  1. 双指针法：设置两个指针，left 指向字符串开头，right 指向字符串末尾。
  2. 忽略非字母数字：在比较前，跳过字符串中的非字母数字字符（如空格、标点）。
  3. 大小写不敏感：将比较的字符统一转换为小写或大写。
  4. 向中间移动并比较：当 left < right 时，循环比较 s[left] 和 s[right] 是否相等。如果不相等，则不是回文串。如果相等，则 left++，right--，继续比较。
  5. 结束判断：如果循环正常结束，说明所有对应字符都相等，字符串是回文串。
• 核心要点：此方法时间复杂度为 O(n)，空间复杂度为 O(1)，是判断回文串的经典解法。

20. 字符串的全排列

利用回溯法可以遍历并生成一个字符串的所有可能排列。

• 步骤解析：
  1. 回溯法：使用递归函数，遍历所有可能的排列组合。
  2. 字符选择：在每一步，从剩余的字符中选择一个作为当前排列的下一个字符。
  3. 排除重复：如果输入字符串包含重复字符，需要使用一个标记数组（如 used）或在同一层递归中跳过已使用过的相同字符，以避免生成重复排列。
  4. 递归组合：将选中的字符加入当前路径，标记为已使用，然后递归地处理剩下的字符。
  5. 还原状态：每次递归返回后，需要将当前字符从路径中移除，并取消其已使用标记，以便进行下一次选择（回溯）。
• 核心要点：回溯法是解决排列、组合类问题的标准范式，关键在于正确地选择和撤销选择。

21. 最小覆盖子串

滑动窗口法是解决最小覆盖子串问题的经典方法。

• 步骤解析：
  1. 滑动窗口法：使用左右指针维护一个动态窗口，遍历长字符串。
  2. 字符计数：分别用两个哈希表（或数组）统计目标字符串 T 中每个字符的需求量，以及当前窗口内各字符的拥有量。
  3. 窗口调整：右指针不断右移扩大窗口，直到窗口内包含了 T 的所有字符。此时，尝试移动左指针缩小窗口，以找到满足条件的最小子串。
  4. 更新结果：在窗口缩小的过程中，如果新的窗口依然满足条件，则更新最小子串的起始位置和长度。
  5. 效率与准确性：精确控制窗口的扩大和缩小，确保在 O(n) 的时间复杂度内找到最优解。
• 核心要点：滑动窗口法高效地解决了子串匹配问题，关键在于维护一个动态窗口并记录有效状态。

22. 判断快乐数

快乐数的判断涉及到循环检测，可以通过快慢指针技巧高效解决。

• 步骤解析：
  1. 数字变换：定义一个函数，计算一个数各位数字的平方和。
  2. 快慢指针技巧：将数字变换的过程视为一个隐式链表。slow 每次计算一次变换，fast 每次计算两次变换。
  3. 判断条件：快乐数最终会变换为 1。如果 slow 或 fast 变为 1，则该数是快乐数。
  4. 检测循环：如果 fast 与 slow 相遇（得到相同的结果，且该结果不为 1），则说明进入了循环，该数不是快乐数。
• 核心要点：此方法避免了使用 HashSet 记录历史结果，空间复杂度为 O(1)，效率较高。

六、其他经典问题

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

LCS 是经典的二维动态规划问题，用于衡量两个序列的相似度。

• 步骤解析：
  1. 定义动态规划表：创建二维数组 dp[i][j]，表示字符串 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列长度。
  2. 初始化边界：dp[0][j] 和 dp[i][0] 均为 0，表示空串与任何字符串的 LCS 长度为 0。
  3. 填表计算：遍历两个字符串，如果当前字符相等 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
  4. 回溯构造序列：从 dp[m][n] 开始，根据状态转移的方向回溯，可以构造出其中一个最长公共子序列。
  5. 优化空间复杂度：由于 dp[i] 只依赖于 dp[i-1]，可以通过滚动数组将空间复杂度优化到 O(min(m, n))。
• 核心要点：LCS 问题完美体现了动态规划处理字符串比较的能力。

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

利用二叉搜索树中序遍历结果为递增序列的特性，可以高效找到第 k 小的元素。

• 步骤解析：
  1. 中序遍历：对二叉搜索树进行中序遍历。
  2. 计数访问：在遍历过程中，使用一个计数器记录当前已访问的元素个数。
  3. 找到第 k 个元素：当计数器增加到 k 时，当前正在访问的节点即为所求的第 k 小的元素。
  4. 递归或迭代：可以使用递归方式进行中序遍历，也可以使用栈进行迭代遍历，以便在找到第 k 个元素时提前终止。
• 核心要点：此方法时间复杂度为 O(k)，最坏情况为 O(n)，其中 n 是树中的节点数。

25. 数组中第 k 大的元素

找出数组中第 k 大的元素有多种解法，适用于不同场景。

• 常用解法：
  1. 排序后选择：将数组排序，然后直接选择索引为 n-k 的元素。时间复杂度 O(n log n)。
  2. 使用优先队列：维护一个大小为 k 的最小堆。遍历数组，将元素加入堆，当堆大小超过 k 时，弹出堆顶（最小值）。遍历结束后，堆顶元素即为第 k 大的元素。时间复杂度 O(n log k)，空间 O(k)。
  3. 快速选择：基于快速排序的分区思想。每次分区后，判断基准元素的位置与 n-k 的关系，只在包含目标的一侧递归查找。平均时间复杂度 O(n)，最坏 O(n²)。
• 核心要点：不同方法的时间和空间复杂度各异，快速选择在平均情况下性能最优，但堆方法在数据流场景下更有优势。