Day 11。
今天两道题分别是 Generate Parentheses 和 Merge k Sorted Lists。
一道是非常经典的 回溯搜索题，一道是典型的 堆 + 链表合并题。
今天的关键词：回溯、剪枝、优先队列、小根堆、多路归并。
🧠 LeetCode 22 – Generate Parentheses
💡 思路总结
这题要求生成所有合法的括号组合。
看到“生成所有可能结果”这种题，第一反应通常就要想到：
回溯 / DFS
因为我们是在一步一步构造字符串：
- 可以放左括号
( - 也可以放右括号
)
但不是随便放，而是要始终保证当前字符串合法。
你的做法很标准：
left记录已经用了多少个左括号right记录已经用了多少个右括号- 当字符串长度达到
2 * n时，加入答案
💻 代码实现
class Solution {
public:
vector<string> result;
vector<string> generateParenthesis(int n) {
backtrack("",0,0,n);
return result;
}
void backtrack(string cur, int left, int right, int n) {
if (cur.size() == 2 * n) {
result.push_back(cur);
return;
}
if (left < n) {
backtrack(cur + "(", left + 1, right, n);
}
if (right < left) {
backtrack(cur + ")", left, right + 1, n);
}
}
};
📌 知识点总结
1️⃣ 回溯的本质
这题本质就是：
- 先做一个选择
- 递归进入下一层
- 再继续尝试别的选择
也就是典型的“决策树搜索”。
你这里的每一步都在问：
- 当前位置能不能放左括号？
- 当前位置能不能放右括号？
2️⃣ 两个限制条件非常关键
这题最核心的不是“枚举”，而是“合法枚举”。
你这里用了两个判断：
if (left < n)
表示左括号总数不能超过 n。
if (right < left)
表示右括号数量不能超过左括号数量。
这个条件尤其关键，因为它保证了：
任意时刻，字符串前缀都不会非法
比如你不能一上来就放 )，因为这样一定不可能构成合法括号串。
3️⃣ 这其实就是剪枝
如果暴力想法是：
- 每个位置都试
(和) - 最后再判断是否合法
那会生成很多无效答案。
而你现在的写法是：
在搜索过程中就提前排除不合法情况
这就是回溯题里非常经典的“剪枝”思想。
4️⃣ 回溯题的典型特征
这题很适合你记一个信号：
如果题目是这种：
- 求所有组合
- 求所有方案
- 求所有排列
- 结果数量不固定
就要优先想：
- 回溯
- DFS
- 递归构造
🔗 LeetCode 23 – Merge k Sorted Lists
💡 思路总结
这题要求把 k 个有序链表合并成一个有序链表。
如果直接暴力合并，当然也能做，但效率不够高。
更聪明的办法是：
每次从 k 个链表当前节点里，取最小的那个出来
这就非常适合用：
- 优先队列
- 小根堆
你的思路非常标准：
- 先把每个链表的头节点放进堆里
- 每次取出最小节点，接到结果链表后面
- 如果这个节点后面还有节点，就把它的
next再放进堆里 - 重复直到堆空
💻 代码实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
struct cmp {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val; // 小根堆
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
// 先把每个链表的头节点放进堆
for (ListNode* node : lists) {
if (node != nullptr) {
pq.push(node);
}
}
ListNode dummy(0);
ListNode* tail = &dummy;
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
tail->next = node;
tail = tail->next;
if (node->next != nullptr) {
pq.push(node->next);
}
}
return dummy.next;
}
};
📌 知识点总结
1️⃣ 这是“多路归并”问题
如果 mergeTwoLists 是“两路归并”，
那么这题其实就是：
多路归并
也就是说，不再是两个有序链表比较，而是 k 个有序链表一起竞争“当前最小值”。
2️⃣ 为什么堆很适合
因为我们需要反复做一件事：
- 在多个候选节点里找最小值
- 取出来
- 再补一个新候选节点进去
这正是堆最擅长的场景。
优先队列可以让：
- 取最小值：
O(log k) - 插入新节点：
O(log k)
整体效率会比反复线性扫描所有链表头节点高很多。
3️⃣ 自定义比较器
你这里写了：
struct cmp {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val; // 小根堆
}
};
这个地方很重要。
因为 C++ 的 priority_queue 默认是大根堆，而我们这里需要的是最小值优先出来，所以要自己定义成小根堆。
这是优先队列题里特别高频的写法。
4️⃣ 虚拟头结点继续出现了
你这里又用了：
ListNode dummy(0);
ListNode* tail = &dummy;
这说明链表题里，虚拟头结点真的到处都能用。
它的作用还是一样：
- 方便统一拼接逻辑
- 不需要特判结果链表第一个节点
5️⃣ 和 LeetCode 21 的联系
你可以把今天这题和 Day 10 的 Merge Two Sorted Lists 放在一起看：
21：两个链表合并23：多个链表合并
如果说 21 是双指针版有序合并，
那 23 就是堆优化版的多路有序合并。
这就是很典型的“旧题升级版”。
🧩 今日总结
| 题目 | 核心思想 |
|---|---|
| LeetCode 22 | 回溯 + 剪枝 + 合法括号构造 |
| LeetCode 23 | 优先队列 + 小根堆 + 多路归并 |
今天这两题都很有代表性：
22是回溯题模板23是堆题 + 链表题结合的经典题
🧠 今日收获
今天最值得记住的两个模型：
1. 回溯生成类问题
遇到“生成所有合法结果”这类题时，优先想：
- 当前状态是什么
- 下一步有哪些选择
- 哪些选择不合法，要提前剪掉
这题的：
if (left < n)
if (right < left)
就是非常标准的剪枝条件。
2. 多路最小值选择问题
如果题目是：
- 多个有序序列
- 每次取最小 / 最大
- 动态补入新元素
就要优先想到：
- 堆
- 优先队列
这类题以后在数组、链表、区间题里都还会出现。
💬 写给自己的话
Day 11 了。
你已经开始接触到越来越典型的“核心模板题”了：
- 回溯怎么写
- 剪枝怎么做
- 堆什么时候上
- 多路归并怎么想
这很重要。
因为刷题真正的进步，往往不是“今天又做了一题”，
而是：
我又掌握了一种可复用的思维模型。
今天这两题，就是这样的题。
继续坚持。
一天天看似普通，但你的题库记忆、代码表达、模板熟悉度，都在慢慢累加。
总有一天你再回头看这些题，会发现它们已经成了你的基本功。
阿玉，Day 11，继续冲。
—— 刷题第 11 天
