算法刷题记录——LeetCode篇(1) [第1~100题](持续更新)

更新时间：2025-03-21

• LeetCode刷题目录：算法刷题记录——专题目录汇总
• 技术博客总目录：计算机技术系列博客——目录页

优先整理热门100及面试150，不定期持续更新，欢迎关注！

---

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• 只会存在一个有效答案

进阶：
你可以想出一个时间复杂度小于 O(n^2) 的算法吗？

方法：哈希表

利用哈希表存储已遍历元素的值及其索引，对于每个元素 nums[i]，计算其补数 target - nums[i]。若补数存在于哈希表中，则直接返回两个索引；否则将当前元素存入哈希表，继续遍历。

1. 初始化哈希表，键为元素值，值为索引。
2. 遍历数组，对于每个元素计算补数。
3. 检查补数是否存在哈希表中：
   • 存在：返回当前索引和补数的索引。
   • 不存在：将当前元素存入哈希表。
4. 题目保证存在解，无需处理无解情况。

代码实现(Java)：

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int complement = target - nums[i];if (map.containsKey(complement)) {return new int[] { map.get(complement), i };}map.put(nums[i], i);}throw new IllegalArgumentException("No solution found");}
}

复杂度分析

• 时间复杂度：O(n)，只需一次遍历数组。
• 空间复杂度：O(n)，哈希表存储最多 n 个元素。

---

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]

解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

方法：模拟逐位相加

模拟手工逐位相加的过程，从链表头部（最低位）开始遍历，处理每一位的和及进位。使用哑节点简化链表头部的处理，循环直到所有链表遍历完毕且无进位为止。

1. 初始化：
   • 创建哑节点 dummy 和当前指针 current。
   • 初始化进位 carry 为 0。
2. 遍历链表：
   • 只要任一链表未遍历完或存在进位，继续循环。
   • 计算当前位的总和：sum = val1 + val2 + carry。
   • 更新当前节点值和进位。
3. 处理剩余节点和进位：
   • 若链表遍历完毕，对应值取 0。
   • 若最终进位非零，添加新节点。

代码实现(Java)：

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode current = dummy;int carry = 0;while (l1 != null || l2 != null || carry != 0) {int val1 = (l1 != null) ? l1.val : 0;int val2 = (l2 != null) ? l2.val : 0;int sum = val1 + val2 + carry;carry = sum / 10;current.next = new ListNode(sum % 10);current = current.next;if (l1 != null) l1 = l1.next;if (l2 != null) l2 = l2.next;}return dummy.next;}
}

哑节点：简化链表头节点的处理，避免空指针问题。
循环条件：覆盖两链表长度不同及存在最终进位的情况。
进位处理：每位计算后更新进位，并在循环结束时检查是否需要添加新节点。

复杂度分析

• 时间复杂度：O(max(m, n))，其中 m 和 n 为两链表长度。
• 空间复杂度：O(1)（不计结果链表）。

---

4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000

解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000

解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10^6 <= nums1[i], nums2[i] <= 10^6

方法：二分查找法

将问题转化为寻找两个有序数组的第k小元素，通过递归二分排除元素实现。

1. 中位数转换：
   • 将中位数问题转化为寻找第k小元素问题，奇数找中间数，偶数找中间两个数的平均值
2. 递归二分排除：
   • 每次比较两个数组的第k/2个元素（实际取有效长度防止越界）
   • 排除较小值所在数组的前k/2元素（或全部剩余元素）
   • 递归处理剩余部分，直到k=1时直接取较小值
3. 边界处理：
   • 当某个数组起始位置越界时，直接从另一数组取对应元素
   • 有效步长计算确保不会越界访问数组

代码实现(Java)：

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int total = nums1.length + nums2.length;if (total % 2 == 1) {return findKth(nums1, nums2, 0, 0, total / 2 + 1);} else {int left = findKth(nums1, nums2, 0, 0, total / 2);int right = findKth(nums1, nums2, 0, 0, total / 2 + 1);return (left + right) / 2.0;}}private int findKth(int[] A, int[] B, int aStart, int bStart, int k) {if (aStart >= A.length) return B[bStart + k - 1];if (bStart >= B.length) return A[aStart + k - 1];if (k == 1) return Math.min(A[aStart], B[bStart]);// 计算有效步长（防止越界）int aStep = Math.min(k / 2, A.length - aStart);int bStep = Math.min(k / 2, B.length - bStart);int aIndex = aStart + aStep - 1;int bIndex = bStart + bStep - 1;// 比较并排除较小值的区间if (A[aIndex] <= B[bIndex]) {return findKth(A, B, aStart + aStep, bStart, k - aStep);} else {return findKth(A, B, aStart, bStart + bStep, k - bStep);}}
}

复杂度分析

• 时间复杂度为O(log(m+n))，每次递归减少k值约一半。

---

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 1：

输入：s = "babad"
输出："bab"

解释：“aba” 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

方法一：动态规划

• 利用二维数组 dp[i][j] 记录子串 s[i...j] 是否为回文。
• 通过状态转移方程 dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1] 递推计算所有子串的回文性，同时记录最长回文。

代码实现(Java)：

class Solution {public String longestPalindrome(String s) {int n = s.length();if (n < 2) return s;boolean[][] dp = new boolean[n][n];int maxLen = 1, start = 0;// 初始化所有长度为1的子串为回文for (int i = 0; i < n; i++) dp[i][i] = true;// 递推计算所有子串for (int j = 1; j < n; j++) {for (int i = 0; i < j; i++) {if (s.charAt(i) != s.charAt(j)) {dp[i][j] = false;} else {if (j - i < 3) { // 长度<=3时无需检查内部子串dp[i][j] = true;} else {dp[i][j] = dp[i+1][j-1];}}// 更新最长回文if (dp[i][j] && j - i + 1 > maxLen) {maxLen = j - i + 1;start = i;}}}return s.substring(start, start + maxLen);}
}

复杂度分析:

• 时间复杂度：O(n²)，双重循环遍历所有子串。
• 空间复杂度：O(n²)，存储动态规划表。

方法二：中心扩展法

遍历每个可能的回文中心（单个字符或相邻字符对），向两侧扩展直到不满足回文条件。记录扩展过程中的最长回文。

代码实现(Java)：

class Solution {public String longestPalindrome(String s) {if (s == null || s.length() < 1) return "";int start = 0, end = 0;for (int i = 0; i < s.length(); i++) {int len1 = expand(s, i, i);    // 奇数长度int len2 = expand(s, i, i+1);  // 偶数长度int maxLen = Math.max(len1, len2);if (maxLen > end - start) {start = i - (maxLen - 1) / 2;end = i + maxLen / 2;}}return s.substring(start, end + 1);}private int expand(String s, int left, int right) {while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {left--;right++;}return right - left - 1; // 实际回文长度}
}

复杂度分析:

• 时间复杂度：O(n²)，遍历 2n-1 个中心点，每个扩展最多 O(n) 次。
• 空间复杂度：O(1)，无需额外存储。

方法三：BFS 层序扩展

将每个可能的回文中心（长度1或2）加入队列，逐层向两侧扩展。每次扩展后更新最长回文，利用队列避免重复处理。

代码实现(Java)：

class Solution {public String longestPalindrome(String s) {int n = s.length();if (n == 0) return "";Queue<int[]> queue = new LinkedList<>();boolean[][] visited = new boolean[n][n];int maxLen = 1, start = 0;// 初始化长度为1和2的回文for (int i = 0; i < n; i++) {queue.offer(new int[]{i, i});visited[i][i] = true;if (i < n-1 && s.charAt(i) == s.charAt(i+1)) {queue.offer(new int[]{i, i+1});visited[i][i+1] = true;maxLen = 2;start = i;}}// BFS扩展while (!queue.isEmpty()) {int[] pos = queue.poll();int l = pos[0], r = pos[1];// 向两侧扩展int nl = l - 1, nr = r + 1;if (nl >= 0 && nr < n && s.charAt(nl) == s.charAt(nr) && !visited[nl][nr]) {visited[nl][nr] = true;queue.offer(new int[]{nl, nr});if (nr - nl + 1 > maxLen) {maxLen = nr - nl + 1;start = nl;}}}return s.substring(start, start + maxLen);}
}

复杂度分析:

• 时间复杂度：O(n²)，每个子串最多处理一次。
• 空间复杂度：O(n²)，存储队列和访问标记。

方法四：Manacher 算法（最优解）

通过插入特殊字符（如 #）将字符串统一为奇数长度，利用对称性快速计算每个中心的最长回文半径，避免重复计算。

代码实现(Java)：

class Solution {public String longestPalindrome(String s) {StringBuilder sb = new StringBuilder("^#");for (char c : s.toCharArray()) {sb.append(c).append('#');}sb.append('$');String T = sb.toString();int n = T.length();int[] P = new int[n];int C = 0, R = 0;for (int i = 1; i < n-1; i++) {int mirror = 2 * C - i;if (i < R) P[i] = Math.min(R - i, P[mirror]);// 扩展回文while (T.charAt(i + P[i] + 1) == T.charAt(i - P[i] - 1)) {P[i]++;}// 更新中心和右边界if (i + P[i] > R) {C = i;R = i + P[i];}}// 找出最大回文int maxLen = 0, center = 0;for (int i = 1; i < n-1; i++) {if (P[i] > maxLen) {maxLen = P[i];center = i;}}int start = (center - maxLen) / 2;return s.substring(start, start + maxLen);}
}

复杂度分析:

• 时间复杂度：O(n)，线性时间处理。
• 空间复杂度：O(n)，存储变换后的字符串和回文半径数组。

对比总结

方法	优劣势
动态规划	逻辑直观，但空间占用较高
中心扩展法	空间最优，代码简洁
BFS 扩展	类似中心扩展，但需额外空间记录状态
Manacher 算法	线性时间，但实现复杂，适用于极大输入

---

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下，与电话按键相同。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字

方法一：回溯法

通过递归生成所有可能的字母组合，每次递归选择一个字母加入当前路径，处理下一个数字。

代码实现(Java)：

public class Solution {public List<String> letterCombinations(String digits) {List<String> result = new ArrayList<>();if (digits == null || digits.isEmpty()) return result;String[] mapping = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};backtrack(result, new StringBuilder(), digits, 0, mapping);return result;}private void backtrack(List<String> result, StringBuilder current, String digits, int index, String[] mapping) {if (index == digits.length()) {result.add(current.toString());return;}char digit = digits.charAt(index);String letters = mapping[digit - '2']; // 根据数字获取对应字母集合for (char c : letters.toCharArray()) {current.append(c);                // 添加当前字母backtrack(result, current, digits, index + 1, mapping); // 递归处理下一个数字current.deleteCharAt(current.length() - 1); // 回溯，删除最后添加的字母}}
}

复杂度分析:

• 时间复杂度： O(3^m*4^n)，其中 m 是输入中对应 3 个字母的数字个数，n 是 4 个字母的数字个数。
• 空间复杂度： O(k)，k 为结果数量，递归栈深度最大为输入长度。

方法二：迭代法（队列）

通过逐步扩展现有组合生成所有可能结果，利用队列管理中间过程。

代码实现(Java)：

public class Solution {public List<String> letterCombinations(String digits) {List<String> result = new ArrayList<>();if (digits == null || digits.isEmpty()) return result;String[] mapping = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};Queue<String> queue = new LinkedList<>();queue.offer(""); // 初始空字符串for (int i = 0; i < digits.length(); i++) {char digit = digits.charAt(i);String letters = mapping[digit - '2'];int size = queue.size();for (int j = 0; j < size; j++) {String s = queue.poll();for (char c : letters.toCharArray()) {queue.offer(s + c); // 生成新组合并入队}}}result.addAll(queue);return result;}
}

复杂度分析:

• 时间复杂度： O(3^m*4^n)，每个数字的处理需要遍历当前队列中所有元素。
• 空间复杂度： O(3^m*4^n)，队列存储所有中间组合。

---

方法三：迭代法（逐步构造）

直接通过遍历每个数字并扩展现有结果，生成所有组合。

代码实现(Java)：

public class Solution {public List<String> letterCombinations(String digits) {List<String> result = new ArrayList<>();if (digits == null || digits.isEmpty()) return result;String[] mapping = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};result.add(""); // 初始空字符串for (char digit : digits.toCharArray()) {List<String> temp = new ArrayList<>();String letters = mapping[digit - '2'];for (String s : result) {for (char c : letters.toCharArray()) {temp.add(s + c); // 将当前字母与现有字符串拼接}}result = temp; // 更新结果}return result;}
}

复杂度分析:

时间复杂度： O(3^m*4^n)，每次迭代生成新的组合。
空间复杂度： O(3^m*4^n)，存储所有中间结果。

---

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

方法一：双指针法（一次遍历）

使用快慢指针技巧，让快指针先移动n步，然后同时移动快慢指针。当快指针到达链表末尾时，慢指针正好指向要删除节点的前驱节点。通过哑节点简化边界条件处理。

1. 初始化哑节点：避免处理头节点删除的特殊情况。
2. 快指针先移动n步：拉开快慢指针的间距。
3. 同步移动快慢指针：直到快指针到达链表末尾。
4. 删除目标节点：修改慢指针的next指针跳过目标节点。

代码实现(Java)：

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode fast = dummy, slow = dummy;// 快指针先移动n步for (int i = 0; i < n; i++) {fast = fast.next;}// 同步移动，直到快指针到达末尾while (fast.next != null) {fast = fast.next;slow = slow.next;}// 删除目标节点slow.next = slow.next.next;return dummy.next;}
}

复杂度分析:

• 时间复杂度：O(L)，其中 L 为链表长度，只需一次遍历。
• 空间复杂度：O(1)，仅使用固定额外空间。

方法二：计算链表长度（两次遍历）

先遍历链表获取长度 L，再定位到倒数第n个节点的前驱位置（正数第 L-n 个节点），直接删除目标节点。

1. 获取链表长度：遍历链表统计节点总数。
2. 定位前驱节点：通过长度计算前驱位置，移动到该位置。
3. 删除目标节点：修改前驱节点的next指针。

代码实现(Java)：

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0);dummy.next = head;int length = getLength(head);ListNode curr = dummy;// 移动到前驱节点位置for (int i = 0; i < length - n; i++) {curr = curr.next;}// 删除目标节点curr.next = curr.next.next;return dummy.next;}// 辅助函数：计算链表长度private int getLength(ListNode head) {int len = 0;while (head != null) {len++;head = head.next;}return len;}
}

复杂度分析:

• 时间复杂度：O(L)，两次遍历，总体仍为线性时间。
• 空间复杂度：O(1)，仅使用固定额外空间。

---

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([])"
输出：true

提示：

• 1 <= s.length <= 10^4
• s 仅由括号 '()[]{}' 组成

方法：栈辅助法

利用栈结构匹配括号，通过遍历字符串处理括号闭合关系。

代码实现(Java)：

class Solution {public boolean isValid(String s) {if (s.length() % 2 != 0) return false; // 奇数长度直接无效Deque<Character> stack = new ArrayDeque<>();for (char c : s.toCharArray()) {if (c == '(' || c == '[' || c == '{') { // 左括号入栈stack.push(c);} else { // 右括号匹配if (stack.isEmpty()) return false; // 栈空说明无对应左括号char top = stack.pop();if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {return false;}}}return stack.isEmpty(); // 最后检查栈是否为空}
}

1. 提前剪枝：字符串长度为奇数时直接返回false，因为有效括号必须成对出现
2. 栈结构操作：
   • 遇到左括号时压入栈顶
   • 遇到右括号时弹出栈顶元素，检查是否匹配
3. 三种失效情况处理：
   • 右括号出现时栈为空（无对应左括号）
   • 右括号与栈顶左括号类型不匹配
   • 遍历结束后栈中仍有未匹配左括号

复杂度分析：

• 时间复杂度: 单次遍历字符串O(n)，栈操作O(1)，总时间复杂度O(n)。

---

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

方法一：迭代法

使用迭代法合并两个有序链表，通过创建一个 哑节点(dummy node) 作为新链表的起始点，逐步比较两个链表的当前节点值，将较小的节点连接到新链表中，直到其中一个链表遍历完毕，然后将剩余链表直接链接到新链表的尾部。

1. 初始化：创建哑节点 dummy 和当前指针 curr，初始时 curr 指向 dummy。
2. 遍历比较：
   • 当两个链表均不为空时，比较它们的当前节点值。
   • 将较小的节点链接到 curr.next，并移动对应的链表指针。
   • 移动 curr 到下一个位置。
3. 处理剩余节点：将非空链表直接链接到 curr.next。
4. 返回结果：返回 dummy.next 作为合并后的链表头节点。

代码实现(Java)：

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode dummy = new ListNode(-1);ListNode curr = dummy;while (list1 != null && list2 != null) {if (list1.val <= list2.val) {curr.next = list1;list1 = list1.next;} else {curr.next = list2;list2 = list2.next;}curr = curr.next;}curr.next = list1 != null ? list1 : list2;return dummy.next;}
}

复杂度分析：

• 时间复杂度：O(m + n)，其中 m 和 n 分别为两个链表的长度。
• 空间复杂度：O(1)，仅使用固定大小的额外空间。

方法二：递归法

递归法通过比较两个链表头节点的值，将较小节点的 next 指针指向剩余链表合并的结果，递归终止条件为其中一个链表为空时直接返回另一个链表。

1. 终止条件：
   • 若 list1 为空，返回 list2。
   • 若 list2 为空，返回 list1。
2. 递归合并：
   • 比较两个链表头节点的值，较小节点的 next 指向递归合并后的结果。
   • 返回较小的节点作为当前子链表的头节点。

代码实现(Java)：

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null) return list2;if (list2 == null) return list1;if (list1.val <= list2.val) {list1.next = mergeTwoLists(list1.next, list2);return list1;} else {list2.next = mergeTwoLists(list1, list2.next);return list2;}}
}

复杂度分析：

• 时间复杂度：O(m + n)，递归遍历所有节点。
• 空间复杂度：O(m + n)，递归调用栈的深度最大为两链表长度之和。

对比总结

方法	优点	缺点	适用场景
迭代法	空间复杂度低，无递归开销	代码相对较长	处理大规模链表时更优
递归法	代码简洁，逻辑清晰	空间复杂度高，可能栈溢出	链表较短或对代码简洁性要求高时

---

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

方法一：回溯法（深度优先搜索）

通过递归生成所有可能的有效括号组合，优先添加左括号并在条件允许时添加右括号，确保右括号数量不超过左括号。

代码实现(Java)：

public class Solution {public List<String> generateParenthesis(int n) {List<String> res = new ArrayList<>();backtrack(res, new StringBuilder(), 0, 0, n);return res;}private void backtrack(List<String> res, StringBuilder current, int left, int right, int n) {if (current.length() == 2 * n) {res.add(current.toString());return;}if (left < n) {current.append('(');backtrack(res, current, left + 1, right, n);current.deleteCharAt(current.length() - 1); // 回溯}if (right < left) {current.append(')');backtrack(res, current, left, right + 1, n);current.deleteCharAt(current.length() - 1); // 回溯}}
}

复杂度分析：

• 时间复杂度： O(4^n / √n)，由卡塔兰数公式决定，每个组合的生成时间为 O(1) 均摊。
• 空间复杂度： O(n)，递归栈深度最大为 2n，字符串长度最多为 2n。

方法二：动态规划（递推构造）

利用已知较小规模的结果递推生成较大规模的结果，将问题分解为内部和外部括号组合的拼接。

代码实现(Java)：

public class Solution {public List<String> generateParenthesis(int n) {List<List<String>> dp = new ArrayList<>();dp.add(List.of("")); // dp[0] 初始化为空字符串for (int i = 1; i <= n; i++) {List<String> current = new ArrayList<>();for (int k = 0; k < i; k++) {// 内部 k 对括号，外部 i-1-k 对括号for (String inner : dp.get(k)) {for (String outer : dp.get(i - 1 - k)) {current.add("(" + inner + ")" + outer);}}}dp.add(current);}return dp.get(n);}
}

复杂度分析：

• 时间复杂度： O(n^2 * C(n))，C(n) 为卡塔兰数，需要多层嵌套循环。
• 空间复杂度： O(n * C(n))，存储所有中间结果。

方法三：迭代法（广度优先搜索）

用队列保存中间状态，逐步扩展每个可能的括号组合，直到达到目标长度。

代码实现(Java)：

public class Solution {static class Node {String str;int left;int right;public Node(String s, int l, int r) {str = s;left = l;right = r;}}public List<String> generateParenthesis(int n) {List<String> res = new ArrayList<>();Queue<Node> queue = new LinkedList<>();queue.offer(new Node("", 0, 0));while (!queue.isEmpty()) {Node node = queue.poll();if (node.str.length() == 2 * n) {res.add(node.str);continue;}if (node.left < n) {queue.offer(new Node(node.str + "(", node.left + 1, node.right));}if (node.right < node.left) {queue.offer(new Node(node.str + ")", node.left, node.right + 1));}}return res;}
}

复杂度分析：

• 时间复杂度： O(4^n / √n)，与回溯法相同。
• 空间复杂度： O(4^n / √n)，队列中存储所有中间状态的字符串。

对比总结

1. 回溯法 是最高效的实现，直接通过剪枝避免无效路径，代码简洁。
2. 动态规划 思路巧妙，但空间占用较大，适合研究问题分解的规律。
3. 迭代法（BFS） 无递归栈溢出风险，适合需要迭代实现的场景。

---

23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]

解释：链表数组如下,
[1->4->5, 1->3->4, 2->6]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

方法一：分治合并（递归）

将链表数组递归地分成两半，分别合并左右两半，再将结果合并。利用分治策略降低时间复杂度，每次合并两个有序链表。

1. 递归终止：当链表数组为空或只有一个链表时返回。
2. 分治处理：找到中间位置，递归合并左右两半。
3. 合并结果：将递归得到的两个有序链表合并。

代码实现(Java)：

class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) return null;return merge(lists, 0, lists.length - 1);}private ListNode merge(ListNode[] lists, int start, int end) {if (start == end) return lists[start];int mid = start + (end - start) / 2;ListNode left = merge(lists, start, mid);ListNode right = merge(lists, mid + 1, end);return mergeTwoLists(left, right);}private ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode curr = dummy;while (l1 != null && l2 != null) {if (l1.val < l2.val) {curr.next = l1;l1 = l1.next;} else {curr.next = l2;l2 = l2.next;}curr = curr.next;}curr.next = (l1 != null) ? l1 : l2;return dummy.next;}
}

复杂度分析：

• 时间复杂度：O(nk logk)，其中 n 是平均链表长度，k 是链表数量。
• 空间复杂度：O(logk)，递归调用栈的深度。

方法二：分治合并（迭代）

通过迭代方式逐步合并相邻链表，避免递归栈开销。每次将链表两两合并，直到只剩一个链表。

1. 初始化处理：直接处理链表数组。
2. 逐步合并：每次合并相邻两个链表，缩小数组范围。
3. 最终合并：循环直到数组只剩一个链表。

代码实现(Java)：

class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) return null;int k = lists.length;while (k > 1) {int idx = 0;for (int i = 0; i < k; i += 2) {ListNode l1 = lists[i];ListNode l2 = (i + 1 < k) ? lists[i + 1] : null;lists[idx++] = mergeTwoLists(l1, l2);}k = idx;}return lists[0];}private ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode curr = dummy;while (l1 != null && l2 != null) {if (l1.val < l2.val) {curr.next = l1;l1 = l1.next;} else {curr.next = l2;l2 = l2.next;}curr = curr.next;}curr.next = (l1 != null) ? l1 : l2;return dummy.next;}
}

复杂度分析：

• 时间复杂度：O(nk logk)。
• 空间复杂度：O(1)，无额外递归栈空间。

方法三：优先队列（最小堆）

利用最小堆维护当前所有链表的最小节点。每次取出堆顶节点，将其下一节点加入堆中，直到堆为空。

1. 初始化堆：将所有非空链表头节点加入堆。
2. 构建结果：不断取出堆顶节点，链接到结果链表。
3. 维护堆：将取出节点的下一节点入堆。

代码实现(Java)：

class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) return null;PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);for (ListNode node : lists) {if (node != null) heap.offer(node);}ListNode dummy = new ListNode(0);ListNode curr = dummy;while (!heap.isEmpty()) {ListNode minNode = heap.poll();curr.next = minNode;curr = curr.next;if (minNode.next != null) {heap.offer(minNode.next);}}return dummy.next;}
}

复杂度分析：

• 时间复杂度：O(nk logk)。
• 空间复杂度：O(k)，堆存储最多k个节点。

对比总结

方法	优点	缺点	适用场景
分治合并（递归）	代码简洁，逻辑清晰	递归栈空间O(logk)	常规场景，k较小
分治合并（迭代）	无栈溢出风险，空间最优	修改原数组结构	k较大的场景，空间敏感
优先队列	实现简单，直观	堆空间O(k)	k较小的场景，链表较短

---

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

方法：迭代法

通过迭代遍历链表，每次交换相邻两个节点。使用哑节点简化头节点处理，维护前驱指针current，每次交换current后的两个节点，并更新current的位置。

1. 初始化哑节点：避免处理头节点交换的特殊情况。
2. 遍历条件：当前节点后存在两个可交换节点。
3. 节点交换：
   • 保存当前两个节点及后续节点。
   • 调整指针指向完成交换。
4. 移动前驱指针：前驱指针移动到已交换对的第二个节点，继续后续操作。

代码实现(Java)：

class Solution {public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode(-1);dummy.next = head;ListNode current = dummy;while (current.next != null && current.next.next != null) {// 获取要交换的两个节点ListNode first = current.next;ListNode second = first.next;ListNode next = second.next;// 交换节点current.next = second;second.next = first;first.next = next;// 移动current指针到已交换对的第二个节点，作为下一轮的前驱current = first;}return dummy.next;}
}

复杂度分析

• 时间复杂度：O(n)，每个节点仅遍历一次。
• 空间复杂度：O(1)，仅使用常量额外空间。

---

25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

方法一：迭代法

通过迭代遍历链表，每次处理k个节点组成的子链表。使用哑节点简化头节点处理，维护前驱指针pre，每次找到当前组的首尾节点后进行反转，并重新连接链表。

1. 初始化哑节点：避免处理头节点反转的特殊情况。
2. 寻找当前组的尾节点：通过循环k次定位当前组的结束位置。
3. 反转子链表：将当前组的k个节点反转，返回新的头和尾。
4. 重新连接链表：将前驱节点连接到反转后的头，反转后的尾连接到下一组的头。
5. 更新指针：将前驱指针移动到当前组的尾，继续处理后续节点。

代码实现(Java)：

class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode pre = dummy;ListNode end = dummy;while (end.next != null) {// 定位当前组的尾节点for (int i = 0; i < k; i++) {end = end.next;if (end == null) return dummy.next; // 不足k个直接返回}// 记录关键节点ListNode start = pre.next;ListNode nextGroup = end.next;end.next = null; // 断开当前组// 反转当前组并连接pre.next = reverse(start);start.next = nextGroup; // 原start变为当前组的尾// 更新指针pre = start;end = pre;}return dummy.next;}// 反转链表并返回新头节点private ListNode reverse(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}
}

复杂度分析：

• 时间复杂度：O(n)，每个节点被处理两次（遍历和反转）。
• 空间复杂度：O(1)，仅使用常量额外空间。

方法二：递归法

递归处理每个分组，先判断剩余节点是否足够k个，若足够则反转前k个节点，递归处理后续链表，并将当前尾节点与后续结果连接。

1. 检查剩余长度：遍历k次判断是否足够反转。
2. 反转当前组：反转前k个节点。
3. 递归后续链表：将当前尾节点的next指向递归处理后的结果。
4. 返回新头节点：当前组的头节点变为反转后的首节点。

代码实现(Java)：

class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode curr = head;int count = 0;// 检查是否有足够k个节点while (curr != null && count < k) {curr = curr.next;count++;}if (count == k) { // 足够k个则反转ListNode reversedHead = reverse(head, k);head.next = reverseKGroup(curr, k); // 原head变为当前组的尾return reversedHead;}return head; // 不足k个直接返回}// 反转前k个节点private ListNode reverse(ListNode head, int k) {ListNode prev = null;ListNode curr = head;while (k-- > 0) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}
}

复杂度分析：

• 时间复杂度：O(n)，每个节点被处理一次。
• 空间复杂度：O(n/k)，递归栈深度为分组数。

---

声明

1. 本文版权归 CSDN 用户 Allen Wurlitzer 所有，遵循CC-BY-SA协议发布，转载请注明出处。
2. 本文题目来源 力扣-LeetCode ，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

(持续更新，未完待续)