练习题（2024/4/8）

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 < 1000

5大的国家

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;