LeetCode 第22~24题
目录
LeetCode 第22题： 括号生成
LeetCode 第23题：合并k个升序链表
LeetCode 第24题：两两交换链表中的节点
LeetCode 第22题： 括号生成
题目描述
数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
难度：中等
题目链接：22. 括号生成 - 力扣（LeetCode）
示例1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]示例2：
输入：n = 1 输出：["()"]提示：1<=n<=8
解题思路：
回溯法
- 使用StringBuilder构建当前括号组合
- 记录已使用的左括号和右括号数量
- 递归尝试添加左括号或右括号
- 满足条件时将结果加入列表
public class Solution { public IList<string> GenerateParenthesis(int n) { List<string> result = new List<string>(); BackTrack(result,new StringBuilder(),0,0,n); return result; } private void BackTrack(List<string> result,StringBuilder current,int leftCount,int rightCount,int n) { //如果当前字符串长度等于2n，说明找到了一个有效组合 if(current.Length==n*2) result.Add(current.ToString()),return; //如果左括号数量小于n，可以添加左括号 if(leftCount<n) { current.Append('('); BackTrack(result,current,leftCount+1,rightCount,n); current.Length--;//回溯，删除刚才添加的括号 } //如果右括号数量小于左括号数量，可以添加右括号 if(rightCount<leftCount) { current.Append(')'); BackTrack(result,current,leftCount,rightCount+1,n); current.Length--; } } }
LeetCode 第23题：合并k个升序链表
题目描述
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
难度：困难
题目链接：23. 合并 K 个升序链表 - 力扣（LeetCode）
示例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
解题思路：
方法一：分治合并
将k个链表的合并问题分解为两两合并的子问题
- 如果链表数组为空，返回null
- 如果只有一个链表，直接返回
- 将链表数组分为两半
- 递归合并左半部分和右半部分
- 合并得到的两个链表
public class Solution { public ListNode MergeKLists(ListNode[] lists) { if(lists==null || lists.length==0) return null; return MergeSort(lists,0,lists.length-1); } private ListNode MergeSort(ListNode[] lists,int left,int right) { if(left==right) return lists[left]; if(left>right) return null; int mid = left+(right-left)/2; ListNode leftList = MergeSort(lists,left,mid); ListNode rightList = MergeSort(lists,mid+1,right); return MergeTwoLists(leftList,rightList); } private ListNode MergeTwoLists(ListNode l1,ListNode l2) { ListNode dummy = new ListNode(0); ListNode current = dummy; while(l1!=null && l2!=null) { if(l1.val<=l2.val) current.next = l1,l1=l1.next; else current.next = l2,l2=l2.next; current = current.next; } current.next = l1 ?? l2; return dummy.next; } }方法二：优先队列
使用优先队列（最小堆）来维护k个链表的当前最小节点。
- 创建最小堆，将k个链表的头节点加入堆中
- 每次从堆中取出最小节点，加入结果链表
- 如果被取出的节点有后继节点，将后继节点加入堆中
- 重复2~3步骤直到堆为空。
public class Solution { public ListNode MergeKLists(ListNode[] lists) { if(lists==null lists.length==0) return null; //创建优先队列，按节点值升序排序 var pq = new PriorityQueue<ListNode,int>(); //将所有链表的头节点加入队列 foreach(var list in lists) { if(list!=null) pq.Enqueue(list,list.val); } ListNode dummy = new ListNode(0); ListNode current = dummy; //不断从队列中取出最小节点 while(pq.Count>0) { ListNode node = pq.Dequeue(); current.next = node; current = current.next; //如果取出的节点还有后继节点，将后继节点加入队列 if(node.next!=null) pq.Enqueue(node.next,node.next.val); } return dummy.next; } }
LeetCode 第24题：两两交换链表中的节点
题目描述
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即只能进行节点交换） 。
难度：中等
题目链接：24. 两两交换链表中的节点 - 力扣（LeetCode）
示例1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]示例2：
输入：head = [] 输出：[]示例3：
输入：head = [1] 输出：[1]提示：
- 链表中节点的数目在范围[0,100]内
- 0<=Node.val<=100
解题思路：递归法
- 基线条件：空链表或只有一个节点
- 对于每两个节点：
- 交换这两个节点
- 递归处理后续节点
- 返回新的头节点
public class Solution { public ListNode SwapPairs(ListNode head) { //基线条件：空链表或只有一个节点 if(head==null || head.next==null) return head; //获取要交换的两个节点 ListNode first = head; ListNode second = head.next; //保存后续节点并递归处理 ListNode next = second.next; second.next = first; first.next = SwapPairs(next); return second; } }