覆盖了 Java 算法、数据结构、字符串、数组、链表、树、图、动态规划、贪心、回溯等高频考点。
快速排序是 Java 里超常用的高效排序，核心用分治法。先选一个基准数，把数组里比基准小的放左边，大的放右边，再递归处理左右两边的子数组。实现时可以选第一个数、随机数当基准，避免有序数组导致性能变差。用递归写最简洁，定义分区函数交换元素，把基准放到正确位置。平均时间复杂度 O(nlogn)，空间复杂度 O(logn)，是基本类型排序的首选，JDK 的 Arrays.sort 底层就用了快排，处理大数据量比冒泡、插入排序快太多，日常开发基本都用它。
二分查找必须用在有序数组里，效率超高。核心思路是双指针，左指针指向开头，右指针指向结尾，每次取中间位置的元素和目标值对比。如果中间值等于目标，直接返回下标；比目标小，就去右半部分找；比目标大，就去左半部分找，不断缩小范围。Java 可以用循环实现，避免递归栈溢出，时间复杂度 O(logn)。注意数组一定要有序，无序的话得先排序，这是二分查找的前提，特别适合有序数组的快速查找场景。
链表反转是高频面试题，有递归和迭代两种方法，迭代法更实用，不会栈溢出。迭代的话，定义三个指针：前驱、当前、后继，遍历链表时，把当前节点的 next 指向前驱节点，然后三个指针依次后移，直到遍历结束，最后前驱节点就是新的头节点。递归法是从后往前反转，代码更简洁，但链表太长会栈溢出。两种方法时间复杂度都是 O(n)，空间复杂度迭代是 O(1)，递归是 O(n)，日常开发推荐用迭代法，简单又稳定。
背包问题用动态规划解，核心是定义状态和状态转移方程。最经典的 01 背包，定义 dp 数组，dp[i][j] 表示前 i 个物品、容量 j 的背包能装的最大价值。状态转移就两种选择：不装第 i 个物品，继承上一个状态；装的话，用剩余容量的最大价值加当前物品价值，取两者最大值。还能优化成一维 dp 数组，倒序遍历节省空间。完全背包、多重背包都是在 01 背包基础上改遍历顺序，核心思路都是用子问题的最优解推导出最终最优解。
数组去重分有序和无序两种场景。有序数组超简单，用双指针，慢指针标记去重后的位置，快指针遍历，遇到不同元素就赋值给慢指针，最后截取数组。无序数组的话，用 HashSet，因为集合不允许重复元素，遍历数组把元素放进 set，再转成数组就行。还可以用 HashMap 统计次数去重。有序数组去重时间 O(n)、空间 O(1)；无序用集合时间 O(n)、空间 O(n)，根据数组是否有序选方法，日常开发用集合最省事。
找两个数组的交集，核心是去重 + 匹配。方法一：用 HashSet，先把第一个数组放进 set，遍历第二个数组，元素在 set 里就加入结果集合，最后转成数组，自动去重。方法二：两个数组都排序，然后用双指针遍历，相等就加入结果，同时移动指针，不等就移动小的那个指针，适合有序数组。两种方法都能实现，集合法代码最简单，不用排序，适合无序数组；双指针法空间复杂度更低，适合有序数组，根据场景选就行。
判断链表环用快慢指针法，也叫龟兔赛跑算法，是最优解。定义快指针和慢指针，都从头节点出发，快指针每次走两步，慢指针每次走一步。如果链表有环，两个指针一定会在环里相遇；如果快指针走到 null，说明没有环。时间复杂度 O(n)，空间复杂度 O(1)，不用额外空间。还有一种方法是用 HashSet 存节点，遍历判断是否重复，但是要占用额外空间，面试优先推荐快慢指针法，简洁又高效。
二叉树 DFS 有三种遍历方式：前序、中序、后序，实现分递归和非递归。递归法代码超简单，直接按照遍历顺序访问节点，再递归左右子树，但是树太深会栈溢出。非递归法用 Stack 手动模拟递归栈，前序遍历先压右节点再压左节点，中序和后序调整入栈顺序就行。DFS 的核心是一路走到底再回溯，适合找路径、判断子树、遍历所有节点，时间复杂度都是 O(n)，每个节点只访问一次，面试常考非递归实现。
堆排序基于二叉大顶堆实现，原地排序不用额外空间。第一步把数组构建成大顶堆，堆顶就是最大值；第二步把堆顶和数组末尾元素交换，最大值固定，再把剩余元素重新调整为大顶堆；重复这个过程直到数组有序。核心是堆调整函数，维护堆的结构。时间复杂度稳定 O(nlogn)，空间复杂度 O(1)，是不稳定排序。适合大数据量排序、TopK 问题，Java 的 PriorityQueue 底层就是堆，理解堆调整就能轻松实现堆排序。
找第 k 大元素有两种高效方法。方法一：快速选择法，基于快排的分区思想，不用完整排序，找到基准位置等于 k-1 就返回，平均时间 O(n)。方法二：用最小堆，维护大小为 k 的堆，遍历数组，比堆顶大就替换，最后堆顶就是第 k 大元素，时间 O(nlogk)。快速选择法效率更高，适合大数据量；堆排序法代码更简单，容易实现。这两种都比全排序 O(nlogn) 高效，是面试高频题，优先推荐快速选择法。
图的 DFS 和二叉树类似，用递归或栈实现，关键是加访问标记，避免环。图一般用邻接表存储，定义布尔数组标记节点是否访问过。递归法：访问当前节点，标记为已访问，遍历所有邻接节点，没访问过就递归 DFS。非递归法：用 Stack 存节点，入栈后标记，出栈时遍历邻接节点。图 DFS 适合找路径、判断连通性、拓扑排序，时间复杂度 O(V+E)，V 是节点数，E 是边数，一定要加访问标记，否则会死循环。
斐波那契用动态规划解，避免递归的重复计算，效率超高。递归法时间复杂度 O(2ⁿ)，动态规划是 O(n)。核心思路：自底向上，用 dp 数组保存中间结果，dp[0]=0，dp[1]=1，后面的数都是前两个之和。还能优化空间，不用数组，用两个变量交替保存值，空间复杂度降到 O(1)。代码超简单，循环遍历到 n，更新变量就行。这是动态规划入门题，核心是用子问题解推导出父问题，避免重复计算，比递归实用太多。
会议室预定用贪心算法，最优策略是选结束时间最早的会议，能安排最多场次。第一步把会议数组按结束时间升序排序；第二步初始化第一个会议，遍历后面的会议，只要开始时间大于等于上一个会议的结束时间，就安排，计数加一。时间复杂度主要在排序 O(nlogn)，遍历 O(n)。贪心算法在这里能得到全局最优解，代码简洁，适合会议室调度、活动安排等场景，核心就是每次选最优的局部解。
八皇后是经典回溯题，要求 8 个皇后不同行、列、斜线。核心思路：一行一行放皇后，每行只放一个，用数组记录列位置。递归尝试每一列，判断当前位置是否和之前的皇后冲突（同列、斜线），不冲突就放下，继续下一行；放完 8 行就记录结果，然后回溯，撤销当前选择，尝试下一列。用回溯的暴力搜索 + 剪枝，能找到所有解法。代码用递归 + 判断冲突，时间复杂度高，但八皇后规模小，完全够用，是回溯算法的经典案例。
数组旋转分左旋转和右旋转，最优方法是三次反转法，不用额外空间。比如右旋转 k 位，先把整个数组反转，再反转前 k 个元素，最后反转剩余元素。左旋转同理，调整反转顺序就行。还可以用临时数组存旋转元素，再复制回去，但是占用 O(n) 空间。三次反转法时间 O(n)，空间 O(1)，是最优解。注意 k 可能大于数组长度，要取余处理，避免无效旋转，代码超简洁，日常开发首选这个方法。
找众数有个神算法叫摩尔投票法，时间 O(n)，空间 O(1)，不用哈希表。核心思路：遍历数组，维护候选数和计数，相同就计数加一，不同就减一，计数为 0 就换候选数。因为众数超过一半，最后剩下的候选数就是众数。还可以用 HashMap 统计每个元素的次数，遍历找最大值，代码简单但占用空间。摩尔投票法最优，面试必问，专门针对出现次数超一半的众数场景，高效又巧妙。
二叉树层序遍历就是按一层一层访问节点，用队列实现，是 BFS 的基础。初始化队列，把根节点入队，循环判断队列不为空，记录当前层的节点数量，遍历这一层所有节点，出队并加入值，再把左右子节点入队。这样就能按层收集结果，时间复杂度 O(n)，空间复杂度 O(n)。层序遍历适合求树的深度、每层最大值、节点平均值，代码固定模板，记住队列的使用就行，是二叉树必学的遍历方式。
LCS 是经典动态规划题，用于找两个字符串的最长公共子序列。定义二维 dp 数组，dp[i][j] 表示第一个字符串前 i 个、第二个前 j 个字符的 LCS 长度。字符相等，dp[i][j]=dp[i-1][j-1]+1；不等，取左边或上边的最大值。最后根据 dp 数组回溯找到子序列。时间复杂度 O(mn)，空间 O(mn)，可以优化成一维数组。常用于文本对比、基因匹配，核心是状态转移，记住二维数组的推导逻辑就能实现。
归并排序是稳定的分治法排序，核心是分解 + 合并。把数组递归拆分成左右两个子数组，直到每个子数组只有一个元素，再把两个有序子数组合并成一个大的有序数组。合并时用临时数组保存元素，避免覆盖。时间复杂度稳定 O(nlogn)，空间复杂度 O(n)，是稳定排序。适合外部排序、链表排序，缺点是占用额外空间。代码分拆分和合并两个函数，逻辑清晰，稳定是它最大的优势，适合对排序稳定性有要求的场景。
二叉搜索树的中序遍历是升序序列，所以第 k 小元素就是中序遍历的第 k 个节点。实现分递归和迭代，迭代法用栈，中序遍历，计数到 k 就返回节点值。还能优化，利用 BST 的性质，统计左子树节点数，判断第 k 小在左还是右子树，减少遍历。时间复杂度 O(h)，h 是树高，最优 O(logn)。这是 BST 的经典题，核心利用中序遍历有序的特点，代码简单，面试常考。
图的 BFS 用队列实现，按层遍历节点，关键是访问标记防环。邻接表存图，布尔数组标记访问，初始化队列，入队起始节点并标记。循环出队节点，遍历所有邻接节点，没访问过就入队标记。BFS 适合找无权图的最短路径、判断连通性、层序遍历，时间复杂度 O(V+E)。和 DFS 相比，BFS 无递归栈溢出问题，是最短路径的最优解，代码固定模板，记住队列 + 访问标记就行。
字符串全排列用回溯算法，核心是交换 + 递归。把字符串转成字符数组，固定第一个位置的字符，递归排列后面的字符，递归到底就记录结果，然后回溯交换回来，尝试下一个字符。有重复字符的话，用 HashSet 去重，避免重复排列。时间复杂度 O(n!)，因为全排列数量是阶乘级的。代码用递归 + 回溯，逻辑清晰，是字符串处理的经典题，注意处理重复字符的情况，避免输出重复结果。
快乐数的规则：不断替换为各位数字平方和，最终等于 1 就是快乐数，无限循环就不是。核心是判断是否循环，用快慢指针法，快指针算两次平方和，慢指针算一次，相遇就说明循环。如果相遇时是 1，就是快乐数。不用 HashSet 存结果，空间 O(1)，时间 O(logn)。这是数学 + 双指针的题，代码超简单，记住快慢指针判断循环的思路，比集合法更高效。
最小覆盖子串用滑动窗口 + 哈希表，是经典双指针题。用哈希表统计目标字符串的字符次数，左右指针形成滑动窗口，右指针扩大窗口包含所有目标字符，左指针缩小窗口找最小长度。实时更新最小窗口的起始和长度，遍历结束就得到结果。时间复杂度 O(n)，n 是字符串长度，是最优解法。适合找包含目标字符的最小子串，核心是滑动窗口的收缩和扩张，面试高频题。
无序数组找中位数，最优方法是快速选择，不用全排序。找到数组中间位置的元素，奇数长度直接返回，偶数返回中间两个的平均值。快速选择基于快排分区，平均时间 O(n)，比全排序 O(nlogn) 高效。还可以先排序再取中位数，代码简单但效率低。大数据量推荐快速选择，小数据量直接排序，根据场景选，核心是不用完整排序就能找到中间值。
旋转排序数组是有序数组旋转后的结果，二分查找依然能用。核心思路：每次取中间值，判断左半部分还是右半部分有序，在有序的部分里判断目标值是否在范围内，缩小查找范围。循环执行，找到就返回下标，没找到返回 -1。时间复杂度 O(logn)，和普通二分一样高效。注意处理边界条件，比如数组有重复元素的情况，代码稍作调整就行，是二分查找的进阶题。
判断回文用双指针法最优，左指针在开头，右指针在结尾，两两对比字符。相等就同时向中间移动，不等就直接返回 false。可以先过滤非字母数字、统一大小写，处理带特殊字符的场景。时间复杂度 O(n)，空间复杂度 O(1)，不用额外空间。还可以用字符串反转对比，但是占用空间。双指针法最简单高效，是回文判断的标准解法，日常开发首选。
带随机指针的链表深拷贝，难点是随机指针的指向。最优方法是节点拼接 + 拆分：第一步在每个原节点后面插入拷贝节点；第二步给拷贝节点的随机指针赋值，指向原节点随机指针的下一个节点；第三步拆分原链表和拷贝链表。还能用 HashMap 存原节点和拷贝节点的映射，赋值随机指针。拼接法空间 O(1)，更高效，是面试高频题，核心是利用节点相邻关系映射随机指针。
盛水最多用左右双指针，贪心算法。左指针在开头，右指针在结尾，计算当前容器面积，记录最大值。移动高度更小的指针，因为移动高指针无法增加面积，只有移动矮指针才可能找到更高的边。时间复杂度 O(n)，一次遍历搞定，比暴力枚举 O(n²) 高效太多。核心是贪心选择，每次移动短板，代码超简洁，是双指针的经典应用题，面试必背。
大数相加因为数字超过 long 范围，只能用字符串处理。核心思路：从字符串末尾开始遍历，逐位相加，记录进位。定义两个指针指向末尾，进位初始 0，每次相加当前位 + 进位，计算当前位值和新进位。遍历结束后如果还有进位，追加到结果前面，最后反转字符串得到结果。时间复杂度 O(max(n,m))，n 和 m 是两个字符串长度，是大数运算的标准解法，只能用字符串，不能用数值类型。
二叉树后序遍历顺序是左→右→根，分递归和非递归。递归法代码最简单，递归左子树→递归右子树→访问节点，但是树深会栈溢出。非递归法用栈，有两种方法：一种是标记节点是否访问过，另一种是用前序遍历（根→右→左）反转得到后序。时间复杂度 O(n)，空间复杂度 O(h)。后序遍历适合删除节点、计算树的后缀表达式，非递归法是面试重点，记住标记法就行。
找第三大数，用三个变量保存第一、第二、第三大的数，遍历数组更新。初始化变量为最小值，遍历每个数，跳过重复值，依次更新三个最大值。遍历结束后，如果第三大数存在就返回，不存在返回第一大。时间复杂度 O(n)，空间 O(1)，不用排序，最优解。还能排序后取，但是效率低。核心是维护三个变量，跳过重复元素，代码简单，适合处理大数据量。
这道题用滑动窗口 + 哈希集合，双指针实现。左指针固定，右指针遍历字符串，字符不在集合里就加入，更新最大长度；字符重复就移动左指针，删除集合里的字符，直到无重复。还能用哈希表存字符下标，直接跳左指针，优化效率。时间复杂度 O(n)，一次遍历搞定，是滑动窗口的经典题，面试高频，核心是用窗口维护无重复子串。
消失的数字是数组 1n，有些数重复，找缺失的数。最优方法是原地修改，不用额外空间。遍历数组，把当前元素对应的下标位置的数变成负数，最后遍历数组，正数对应的下标 +1 就是消失的数字。时间复杂度 O(n)，空间 O(1)，完美符合题目要求。还能用 HashSet 存元素，再遍历 1n 找缺失，但是占用空间。原地修改法最优，面试必问。
岛屿问题用DFS 或 BFS，二维数组遍历，遇到 1（陆地）就计算面积。DFS：递归遍历上下左右四个方向，标记访问过的陆地为 0，避免重复计算，累加面积。BFS：用队列存陆地坐标，层序遍历。遍历所有陆地，记录最大面积。时间复杂度 O(mn)，m 和 n 是矩阵行列数，是二维数组搜索的经典题，核心是标记已访问的陆地，防止重复计算。
三数之和用排序 + 双指针，避免暴力枚举 O(n³)。第一步数组排序，第二步遍历每个元素作为第一个数，用左右指针在后面找两个数，和为目标值。找到后加入结果，跳过重复元素，避免重复组合。排序后方便去重和双指针查找，时间复杂度 O(n²)，是最优解。核心是排序 + 去重 + 双指针，面试高频题，注意处理重复元素的边界。
股票买卖 DP 分多种场景，核心是定义状态：持有股票 / 不持有股票的最大利润。无限次交易：dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])；dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])。最多 1 次交易：记录最小价格，计算最大差价。还能优化成变量，不用 dp 数组，空间 O(1)。时间复杂度 O(n)，根据交易次数调整状态转移，是动态规划的经典应用题。
判断重排相等，核心是两个字符串字符种类和次数完全相同。方法一：用数组统计 26 个字母的次数，遍历两个字符串，一个加一个减，最后数组全 0 就可以。方法二：排序两个字符串，对比是否相等。数组统计法时间 O(n)，空间 O(1)，更高效；排序法 O(nlogn)，代码简单。都是常用方法，优先推荐数组统计，适合字母字符串的判断。
这是动态规划题，类似最长公共子序列。定义 dp[i][j] 为两个字符串前 i、j 个字符的最小删除和。字符相等，dp[i][j]=dp[i-1][j-1]；不等，删除其中一个字符，取最小值加上对应 ASCII 值。最后 dp[m][n] 就是结果。时间复杂度 O(mn)，空间 O(mn)，可以优化成一维数组。核心是借鉴 LCS 的状态转移，是字符串 DP 的进阶题。
文本模式匹配常用KMP 算法，比暴力匹配高效。暴力匹配 O(nm)，KMP 预处理模式串，生成 next 数组，跳过无效匹配，时间 O(n+m)。next 数组记录模式串的最长前缀后缀，匹配失败时，模式串不用回退到开头，直接跳到 next 数组的位置。还有朴素匹配、BM 算法，KMP 是面试必考，核心是 next 数组的构建，解决字符串高效匹配问题。
罗马数字用贪心算法，定义阿拉伯数字和罗马字符的对应数组，从大到小排列。遍历数组，数字大于等于当前值，就拼接罗马字符，减去对应数值，直到数字为 0。数组包含 1000、900、500 等关键值，不用复杂计算，贪心选择最大的符号。时间复杂度 O(1)，因为数值范围固定，代码超简单，是贪心算法的小应用。
二叉树最近公共祖先，递归实现超简洁。递归终止条件：节点为 null 或等于 p/q，返回节点。递归左子树和右子树，左右都不为空，当前节点就是祖先；左空返回右，右空返回左。二叉搜索树可以利用大小关系优化，普通二叉树用这个递归法，时间复杂度 O(n)。核心是后序遍历，从下往上找，是二叉树高频面试题。
跳跃游戏分能否到达终点和最小跳跃次数。能否到达：维护最大能到达的位置，遍历数组，当前位置超过最大位置返回 false，更新最大位置，遍历完返回 true。最小次数：贪心选每一步能跳最远的位置，计数加一。时间复杂度 O(n)，一次遍历搞定，核心是贪心维护最远可达位置，代码简洁，是贪心经典题。
螺旋遍历用边界法，定义上下左右四个边界，按右→下→左→上的顺序遍历，每遍历完一边就收缩对应边界，直到边界交叉。循环遍历，收集元素，注意边界判断，避免重复遍历。时间复杂度 O(mn)，空间 O(1)（除结果外），是二维数组遍历的经典题，代码固定模板，记住边界收缩的逻辑就行。
最长递增子序列有两种方法。动态规划：dp[i] 表示以 i 结尾的最长长度，O(n²)。贪心 + 二分查找：维护一个递增数组，遍历元素，二分查找替换，长度就是结果，O(nlogn)，最优解。核心是贪心选择最小的尾部元素，给后面留更多空间，是面试高频题，优先推荐贪心 + 二分法。
合并区间先按区间起始值排序，然后遍历合并。初始化结果列表，加入第一个区间，遍历后面的区间，当前区间起始≤结果最后一个区间的结束，就合并，更新结束值；否则直接加入。时间复杂度 O(nlogn)，主要在排序，是区间处理的经典题，核心是排序 + 贪心合并，代码简单实用。
环检测用快慢指针，相遇说明有环。找入环点：相遇后，慢指针回到头节点，快慢指针都每次走一步，再次相遇的节点就是入环点。数学推导证明这个方法有效，时间 O(n)，空间 O(1)，是链表高频题，比哈希表法更高效，记住相遇后重置慢指针的逻辑。
找重复数字，方法一：HashSet 遍历，存在就返回，O(n) 空间。方法二：原地置换，数组元素 0~n-1，把元素放到对应下标，冲突就是重复，O(1) 空间。原地置换法最优，适合有范围限制的数组，面试必问，核心是利用下标和元素的对应关系。
缺失重复数字，用数学法或原地修改。数学法：计算和与平方和，列方程求解。原地修改：遍历数组，标记对应下标为负，重复的数是下标 +1，缺失的是正数下标 +1。时间 O(n)，空间 O(1)，原地修改法最优，和消失的数字思路一致。
字母组合用回溯算法，定义数字和字母的映射，递归遍历每个数字的字母，拼接组合，递归到底就加入结果。回溯遍历所有可能的组合，时间复杂度 O(3^m×4^n)，m 是 3 个字母的数字，n 是 4 个字母的数字，是回溯的经典应用题。
表达式求值用双栈法，一个栈存数字，一个栈存运算符。定义运算符优先级，遍历表达式，数字入栈，运算符比较优先级，优先级低就弹出计算，最后计算栈中剩余元素。支持加减乘除和括号，时间复杂度 O(n)，是栈的经典应用，核心是优先级判断。
