1. 字母异位词分组题目要求将互为字母异位词的字符串放入同一组。例如[eat, tea, tan, ate, nat, bat]可以分为[[eat, tea, ate], [tan, nat], [bat]]核心思路字母异位词中每种字符出现的次数相同。将字符串排序后互为异位词的字符串一定会得到同一个结果eat - aet tea - aet ate - aet使用HashMapkey排序后的字符串 value具有相同 key 的原字符串列表复杂度设字符串平均长度为k字符串数量为n时间复杂度O(n × k log k) 空间复杂度O(n × k)2. 环形链表判断一个链表中是否存在环。3 - 2 - 0 - -4 ^ | |_________|核心思路快慢指针定义两个指针slow每次走 1 步 fast每次走 2 步无环fast最终会到达null有环fast会在环中追上slow两个指针会指向同一个节点。while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { return true; } }复杂度时间复杂度O(n) 空间复杂度O(1)3. 最长回文子串在字符串中找到最长的回文子串。输入babad 输出bab 或 aba 输入cbbd 输出bb核心思路中心扩展回文串有两种中心奇数长度aba 中心是 b 偶数长度abba 中心在两个 b 之间因此每个位置都需要尝试两次扩展expandAroundCenter(s, i, i); // 奇数长度 expandAroundCenter(s, i, i 1); // 偶数长度扩展条件left 0 right s.length() s.charAt(left) s.charAt(right)起始下标计算当回文长度为len当前左中心为i时start i - (len - 1) / 2;这条公式能统一处理奇数长度与偶数长度回文。复杂度时间复杂度O(n²) 空间复杂度O(1)4. 零钱兑换给定硬币面额coins和金额amount求凑出目标金额所需的最少硬币数。无法凑出时返回-1。coins [1, 2, 5] amount 11 答案3 解释5 5 1为什么不能贪心coins [1, 3, 4] amount 6 贪心4 1 1需要 3 枚 最优3 3只需要 2 枚因此不能只优先选择面额最大的硬币。核心思路一维动态规划定义dp[x]凑出金额 x 所需的最少硬币数量初始状态dp[0] 0;其他位置先初始化为不可能达到的大值Arrays.fill(dp, amount 1);状态转移dp[currentAmount] Math.min( dp[currentAmount], dp[currentAmount - coin] 1 );含义是最后选择一枚coin后前面先凑出currentAmount - coin。复杂度时间复杂度O(amount × coins.length) 空间复杂度O(amount)5. 买卖股票的最佳时机只能买入一次、卖出一次求最大利润。prices [7, 1, 5, 3, 6, 4] 答案5 第 2 天以 1 买入第 5 天以 6 卖出。核心思路维护历史最低价格遍历每一天的股价时维护minPrice截至当前日期的最低买入价格 maxProfit截至当前日期的最大利润for (int price : prices) { minPrice Math.min(minPrice, price); maxProfit Math.max(maxProfit, price - minPrice); }当出现一个更低价格时它将成为后续更好的买入机会当前价格则可以尝试作为卖出价格。复杂度时间复杂度O(n) 空间复杂度O(1)6. 除自身以外数组的乘积返回数组answer其中answer[i] 除 nums[i] 外其余元素的乘积输入[1, 2, 3, 4] 输出[24, 12, 8, 6]核心思路前缀积 后缀积定义left[i]i 左边所有元素的乘积 right[i]i 右边所有元素的乘积因此answer[i] left[i] × right[i]例如nums [1, 2, 3, 4] left [1, 1, 2, 6] right [24, 12, 4, 1] answer [24, 12, 8, 6]边界位置left[0] 1; right[n - 1] 1;因为没有元素参与相乘时乘积定义为1。复杂度时间复杂度O(n) 空间复杂度O(n)还可以进一步优化为将前缀积直接存入answer再用一个变量从右向左累乘后缀积从而将额外空间优化到O(1)。7. 最大子数组和找到一个和最大的连续子数组。输入[-2, 1, -3, 4, -1, 2, 1, -5, 4] 输出6 最大连续子数组[4, -1, 2, 1]核心思路Kadane 算法不断累加当前连续子数组的和当前累计和大于等于0继续保留当前累计和小于0它会拖累后续结果直接丢弃从后续元素重新开始。int currentSum 0; int maxSum nums[0]; for (int num : nums) { currentSum num; maxSum Math.max(maxSum, currentSum); if (currentSum 0) { currentSum 0; } }为什么不能把maxSum初始化为 0对于全负数数组[-3, -2, -5]最大连续子数组和应该是-2若初始化为0会错误返回0。复杂度时间复杂度O(n) 空间复杂度O(1)8. 合并区间将所有重叠区间合并。输入[[1,3], [2,6], [8,10], [15,18]] 输出[[1,6], [8,10], [15,18]]核心思路排序 贪心扫描先按区间左端点排序Arrays.sort(intervals, (a, b) - a[0] - b[0]);然后依次判断当前区间是否和结果中最后一个区间重叠。判断条件lastEnd currentStart若成立不重叠直接加入结果否则发生重叠更新右端点。lastEnd Math.max(lastEnd, currentEnd);端点相接也需要合并[1, 4] 和 [4, 5]两者在端点4相接结果应为[1, 5]因此“不重叠”的条件必须是lastEnd currentStart而不能写成lastEnd currentStart复杂度排序O(n log n) 扫描O(n) 总时间复杂度O(n log n) 空间复杂度O(n)