1 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1 输出：["()"] 思路：
一个合法的括号组合需要满足以下两个条件：
- 左括号和右括号的数量相等；
- 在任何一个位置，左括号的数量都不少于右括号的数量。
基于以上思路，可以采用回溯法或深度优先搜索（DFS）来生成所有有效的括号组合。
回溯法的实现思路是在每一步中都尝试添加左括号和右括号，并检查是否满足上述两个条件。如果满足条件，则继续向下递归生成；如果不满足条件，则进行回溯，尝试其他可能的选择。
深度优先搜索的实现思路是从当前括号组合开始，尝试向下递归生成所有可能的括号组合。在递归的过程中，需要记录当前左括号和右括号的数量，并根据条件决定是否继续添加左括号或右括号。
总体来说，无论是回溯法还是深度优先搜索，核心思想都是通过递归生成所有可能的括号组合，并在生成过程中保证每一步的合法性。这样，最终可以得到所有有效的括号组合。
代码：
#include <vector>
#include <string>
using namespace std;
class Solution {
vector<string> ans; // 存储生成的所有有效括号组合
public:
// 生成所有有效的括号组合
vector<string> generateParenthesis(int n) {
dfs(0, 0, n, ""); // 调用深度优先搜索函数
return ans; // 返回结果集
}
// 深度优先搜索函数，生成所有有效的括号组合
void dfs(int left, int right, int n, string seq) {
// 当左右括号数量均达到n时，生成了一个有效括号组合
if (left == n && right == n) {
ans.push_back(seq); // 将当前字符串加入结果集
return; // 结束当前递归
}
// 向下递归生成括号组合
if (left < n)
dfs(left + 1, right, n, seq + "("); // 向当前字符串追加左括号，继续递归
if (right < left)
dfs(left, right + 1, n, seq + ")"); // 向当前字符串追加右括号，继续递归
}
};
2合并 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 = [[]] 输出：[] 思路：
1最小堆法
最小堆是一种数据结构，它保证了堆顶元素是堆中最小的元素。我们可以利用最小堆来维护当前K个链表中最小的元素。具体步骤如下：
创建一个最小堆，并定义一个比较函数，使得堆中的节点按照节点值的大小进行排序，以确保堆顶元素是当前K个链表中最小的节点。
遍历K个链表的头节点，并将它们依次加入到最小堆中。
创建一个哨兵节点（dummy），作为合并后链表的头节点的前一个节点。
循环直到最小堆为空：
- 取出最小堆的堆顶节点（当前K个链表中最小的节点）。
- 如果这个最小节点有下一个节点，则将其下一个节点加入到最小堆中。
- 将这个最小节点接入到合并后的链表中。
返回哨兵节点的下一个节点，即合并后链表的头节点。
代码：
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
// 定义比较函数用于最小堆排序
auto cmp = [](const ListNode *a, const ListNode *b) {
return a->val > b->val; // 最小堆
};
// 定义优先队列（最小堆），使用自定义的比较函数
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
// 将每个链表的头结点放入优先队列中
for (auto head: lists)
if (head) pq.push(head);
// 哨兵节点，作为合并后链表头节点的前一个节点
auto dummy = new ListNode(-1);
auto cur = dummy;
// 循环直到堆为空
while (!pq.empty()) {
// 取出堆顶节点，即剩余节点中的最小节点
auto node = pq.top();
pq.pop();
// 如果最小节点有下一个节点，则将下一个节点加入堆中
if (node->next)
pq.push(node->next);
// 将当前最小节点接入新链表中
cur->next = node;
cur = cur->next;
}
// 返回哨兵节点的下一个节点，即新链表的头节点
return dummy->next;
}
};
// 创建链表函数
ListNode* createLinkedList(vector<int>& arr) {
ListNode* dummy = new ListNode(-1);
ListNode* current = dummy;
for (int val : arr) {
current->next = new ListNode(val);
current = current->next;
}
return dummy->next;
}
2 分治法
分治法的基本思路是将原问题分解成若干个规模较小的子问题，然后递归地解决这些子问题，最后将子问题的解合并起来，得到原问题的解。对于合并K个升序链表的问题，我们可以采用以下步骤：
分解：将K个链表划分为两个大致相等的子组。对于每个子组，递归地调用合并函数
mergeTwoLists，将两个链表合并成一个有序链表。合并：递归地将子组的合并结果再次合并，直到最终将所有链表合并成一个有序链表。
代码：
class Solution {
// 21. 合并两个有序链表
// 输入两个有序链表，返回合并后的有序链表
ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
auto dummy = new ListNode(); // 使用哨兵节点简化代码
auto cur = dummy; // cur 指向新链表的末尾
while (list1 && list2) {
if (list1->val < list2->val) {
cur->next = list1; // 将 list1 加入新链表
list1 = list1->next; // 移动 list1 指针
} else { // 注意：当节点值相等时，可选任意一个加入新链表
cur->next = list2; // 将 list2 加入新链表
list2 = list2->next; // 移动 list2 指针
}
cur = cur->next; // 移动新链表的指针
}
// 将剩余部分链接到新链表
cur->next = list1 ? list1 : list2;
return dummy->next; // 返回合并后的链表头节点
}
// 合并 lists[i] 到 lists[j-1] 的链表
// 递归实现分治法合并链表
ListNode *mergeKLists(vector<ListNode *> &lists, int i, int j) {
int m = j - i;
if (m == 0) return nullptr; // 若链表为空，则返回空指针
if (m == 1) return lists[i]; // 若只有一个链表，则直接返回该链表
auto left = mergeKLists(lists, i, i + m / 2); // 合并左半部分链表
auto right = mergeKLists(lists, i + m / 2, j); // 合并右半部分链表
return mergeTwoLists(left, right); // 最终合并左右两部分链表
}
public:
// 合并 K 个升序链表
ListNode *mergeKLists(vector<ListNode *> &lists) {
return mergeKLists(lists, 0, lists.size());
}
};3. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
提示：
- 链表中节点的数目在范围
[0, 100]内 0 <= Node.val <= 100
思路：
- 创建一个虚拟头节点
dummy，并将其指向原链表的头部。 - 使用
prev指针初始化为虚拟头节点，用于迭代遍历链表。 - 在循环中，每次交换两个相邻的节点，需要记住当前的第一个节点
first和第二个节点second。 - 进行节点交换：将
prev->next指向second，first->next指向second->next，second->next指向first，完成交换。 - 将
prev指针移动到下一组待交换的节点位置，即first的位置。 - 重复以上步骤，直到遍历完所有相邻的节点。
- 终止条件是在循环中，当
prev->next或prev->next->next为空时，即链表中不足两个节点可供交换时，循环停止。这是因为两两交换节点需要至少有两个节点才能进行交换，所以当没有足够的节点时，就不需要再进行交换操作，循环可以结束。
代码：
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
// 创建一个虚拟头结点，简化边界情况处理
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head; // 将虚拟头结点指向head，方便后面做删除操作
ListNode* prev = dummyHead; // 初始化前一个节点指针
// 循环遍历链表，直到链表末尾或者仅剩一个节点
while (prev->next != nullptr && prev->next->next != nullptr) {
// 记录当前两个相邻节点
ListNode* first = prev->next;
ListNode* second = prev->next->next;
// 交换节点
prev->next = second; // 前一个节点指向第二个节点
first->next = second->next; // 第一个节点指向第二个节点的下一个节点
second->next = first; // 第二个节点指向第一个节点
// 移动prev指针到下一组待交换的位置
prev = first; // 前一个节点移动两位，准备下一轮交换
}
// 虚拟头结点指向链表的新头部
ListNode* result = dummyHead->next;
// 删除虚拟头结点，避免内存泄漏
delete dummyHead;
// 返回交换后的链表头部
return result;
}
};4员工奖金
表：Employee
+-------------+---------+ | Column Name | Type | +-------------+---------+ | empId | int | | name | varchar | | supervisor | int | | salary | int | +-------------+---------+ empId 是该表中具有唯一值的列。 该表的每一行都表示员工的姓名和 id，以及他们的工资和经理的 id。
表：Bonus
+-------------+------+ | Column Name | Type | +-------------+------+ | empId | int | | bonus | int | +-------------+------+ empId 是该表具有唯一值的列。 empId 是 Employee 表中 empId 的外键(reference 列)。 该表的每一行都包含一个员工的 id 和他们各自的奖金。
编写解决方案，报告每个奖金 少于 1000 的员工的姓名和奖金数额。
以 任意顺序 返回结果表。
结果格式如下所示。
示例 1：
输入： Employee table: +-------+--------+------------+--------+ | empId | name | supervisor | salary | +-------+--------+------------+--------+ | 3 | Brad | null | 4000 | | 1 | John | 3 | 1000 | | 2 | Dan | 3 | 2000 | | 4 | Thomas | 3 | 4000 | +-------+--------+------------+--------+ Bonus table: +-------+-------+ | empId | bonus | +-------+-------+ | 2 | 500 | | 4 | 2000 | +-------+-------+ 输出： +------+-------+ | name | bonus | +------+-------+ | Brad | null | | John | null | | Dan | 500 | +------+-------+
思路：
首先需要知道每个员工的奖金数量，因此需要首先将 Employee 表与 Bonus 表连接。注意需要使用外连接，以处理员工没有出现在 Bonus 表上的情况。这里因为不存在员工只出现在 Bonus 表中的情况，所以只需要使用左外连接（left join 或 left outer join）
其中 Brad 和 John 的 bonus 值为空，空值在数据库中的表示为 null。我们使用 bonus is null（而不是 bonus = null）判断奖金是否为 null。随后即可用 where 子句筛选奖金小于 1000 或者为空的员工。
代码：
#选择员工的姓名和奖金
select name, bonus
#从 Employee 表和 Bonus 表进行左连接
from Employee left join Bonus
on Employee.EmpId = Bonus.EmpId
#筛选出奖金为空或者奖金小于 1000 的员工
where bonus is null or bonus < 10005大的国家
World 表：
+-------------+---------+
| Column Name | Type |
+-------------+---------+
| name | varchar |
| continent | varchar |
| area | int |
| population | int |
| gdp | bigint |
+-------------+---------+
name 是该表的主键（具有唯一值的列）。
这张表的每一行提供：国家名称、所属大陆、面积、人口和 GDP 值。
如果一个国家满足下述两个条件之一，则认为该国是 大国 ：
- 面积至少为 300 万平方公里（即，
3000000 km2），或者 - 人口至少为 2500 万（即
25000000）
编写解决方案找出 大国 的国家名称、人口和面积。
按 任意顺序 返回结果表。
返回结果格式如下例所示。
示例：
输入： World 表： +-------------+-----------+---------+------------+--------------+ | name | continent | area | population | gdp | +-------------+-----------+---------+------------+--------------+ | Afghanistan | Asia | 652230 | 25500100 | 20343000000 | | Albania | Europe | 28748 | 2831741 | 12960000000 | | Algeria | Africa | 2381741 | 37100000 | 188681000000 | | Andorra | Europe | 468 | 78115 | 3712000000 | | Angola | Africa | 1246700 | 20609294 | 100990000000 | +-------------+-----------+---------+------------+--------------+ 输出： +-------------+------------+---------+ | name | population | area | +-------------+------------+---------+ | Afghanistan | 25500100 | 652230 | | Algeria | 37100000 | 2381741 | +-------------+------------+---------+
思路：我们需要从 World 表中选择符合大国条件的国家，并返回它们的名称、人口和面积。
这个查询会选择满足以下条件之一的国家：
- 面积大于等于 300 万平方公里；
- 人口大于等于 2500 万。
代码：
select name ,population,area
from World
where
area >= 3000000
or population >= 25000000
6超过5名学生的课
表: Courses
+-------------+---------+ | Column Name | Type | +-------------+---------+ | student | varchar | | class | varchar | +-------------+---------+ 在 SQL 中，(student, class)是该表的主键列。 该表的每一行表示学生的名字和他们注册的班级。
查询 至少有5个学生 的所有班级。
以 任意顺序 返回结果表。
查询结果格式如下所示。
示例 1:
输入: Courses table: +---------+----------+ | student | class | +---------+----------+ | A | Math | | B | English | | C | Math | | D | Biology | | E | Math | | F | Computer | | G | Math | | H | Math | | I | Math | +---------+----------+ 输出: +---------+ | class | +---------+ | Math | +---------+ 解释: -数学课有6个学生，所以我们包括它。 -英语课有1名学生，所以我们不包括它。 -生物课有1名学生，所以我们不包括它。 -计算机课有1个学生，所以我们不包括它。
思路：我们需要找出至少有5个学生的所有班级。要做到这一点，我们可以使用SQL的聚合功能，具体来说，我们会按班级进行分组，并统计每个班级中的学生数量。然后，我们将筛选出学生数量至少为5的班级。这样，我们就可以得到满足条件的班级列表。
代码：
-- 选择至少有5个学生的所有班级
select class
-- 从 Courses 表中进行查询
from Courses
-- 根据班级进行分组，并筛选出学生数量至少为5的班级
group by class
having count(student) >= 5;