Javajava算法

Java LeetCode 热门算法精讲

本文整理了 Java 语言在 LeetCode 上的高频算法题目，涵盖排序（快速、堆、归并）、查找（二分、中位数）、数据结构（链表、树）、算法思想（动态规划、贪心、回溯、DFS/BFS）及数组字符串技巧。通过步骤解析与核心要点总结，帮助读者掌握常见解题思路与优化方案，适用于面试准备与算法能力提升。

晚风告白发布于 2026/3/29更新于 2026/4/131 浏览

Java LeetCode 热门算法精讲

本文整理了一系列在 LeetCode 上高频出现的算法题目核心解题思路，涵盖了排序、查找、链表、动态规划、字符串处理等多个领域。每个算法都配有精炼的步骤解析和核心思想总结。

一、核心排序算法

1. 快速排序

快速排序采用分治策略，通过选取基准值将数组分为两部分，递归排序后得到整体有序序列。

步骤解析：
1. 选择基准值：从数组中选择一个元素作为基准（pivot），常见选择为首元素或中间元素。
2. 分区操作：重新排列数组，使所有小于基准的元素位于其左侧，大于基准的位于其右侧。
3. 递归排序：对基准左右两侧的子数组递归地应用快速排序。
4. 合并结果：由于是在原数组上进行原地排序，递归结束后数组即完全有序，无需额外合并。
核心要点：基准值的选择直接影响算法性能，理想情况下应选择中位数作为基准。

2. 堆排序

堆排序利用堆数据结构进行选择排序，通过构建最大堆并反复交换堆顶与末尾元素来实现排序。

步骤解析：
1. 构建最大堆：从最后一个非叶子节点开始，自底向上进行下沉操作，确保每个节点都大于或等于其子节点。
2. 交换堆顶元素：将堆顶元素（最大值）与当前堆的最后一个元素交换。
3. 重新调整堆：缩小堆的范围，并对新的堆顶元素执行下沉操作，以恢复最大堆性质。
4. 重复过程：重复交换与调整步骤，直到堆的大小缩减为 1。
核心要点：堆排序不是稳定的排序算法，时间复杂度为 O(n log n)，特别适合处理大数据集。

3. 归并排序

归并排序是典型的分治算法，它将数组不断拆分至最小单元，再通过合并有序子数组来完成整体排序。

步骤解析：
1. 分解数组：递归地将当前数组一分为二，直到每个子数组只包含一个元素。
2. 合并排序：将两个已排序的子数组合并成一个新的有序数组。
3. 递归实现：分解与合并的过程通过递归调用完成。
4. 辅助空间：合并过程需要额外的临时数组来存储中间结果。
核心要点：归并排序是一种稳定的排序算法，时间复杂度 O(n log n)，适合数据量大且要求稳定性的场景。

二、经典查找算法

4. 二分查找

二分查找是一种在有序数组中快速定位目标值的高效算法。

步骤解析：
1. 初始化边界：设定查找范围的起始索引 low = 0 和结束索引 high = 数组长度 - 1。
2. 计算中间索引：在每次循环中计算中间索引 mid = low + (high - low) / 2。
3. 比较中间元素：将 arr[mid] 与目标值 target 进行比较。
4. 调整搜索范围：若 arr[mid] < target，则在右侧区间 [mid+1, high] 继续查找；若 arr[mid] > target，则在左侧区间 [low, mid-1] 查找。
5. 重复查找：重复步骤 2-4，直到找到目标值或搜索区间为空（low > high）。
核心要点：算法通过对数级别的比较次数实现高效查找，时间复杂度 O(log n)。

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²)。
核心要点：不同方法的时间和空间复杂度各异，快速选择在平均情况下性能最优，但堆方法在数据流场景下更有优势。

Java LeetCode 热门算法精讲

Java LeetCode 热门算法精讲

一、核心排序算法

1. 快速排序

2. 堆排序

3. 归并排序

二、经典查找算法

4. 二分查找

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

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

三、数据结构专项

7. 链表反转

8. 判断链表中是否有环

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

四、算法思想与应用

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

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

12. 回溯算法 (八皇后)

13. 深度优先搜索 (DFS)

14. 广度优先搜索 (BFS)

五、数组与字符串技巧

15. 数组去重

16. 寻找数组交集

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

18. 数组旋转

19. 判断回文字符串

20. 字符串的全排列

21. 最小覆盖子串

22. 判断快乐数

六、其他经典问题

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

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

25. 数组中第 k 大的元素

更多推荐文章

相关免费在线工具

Java LeetCode 热门算法精讲

Java LeetCode 热门算法精讲

一、核心排序算法

1. 快速排序

2. 堆排序

3. 归并排序

二、经典查找算法

4. 二分查找

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

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

三、数据结构专项

7. 链表反转

8. 判断链表中是否有环

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

四、算法思想与应用

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

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

12. 回溯算法 (八皇后)

13. 深度优先搜索 (DFS)

14. 广度优先搜索 (BFS)

五、数组与字符串技巧

15. 数组去重

16. 寻找数组交集

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

18. 数组旋转

19. 判断回文字符串

20. 字符串的全排列

21. 最小覆盖子串

22. 判断快乐数

六、其他经典问题

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

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

25. 数组中第 k 大的元素

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具