【LeetCode Solutions】LeetCode 176 ~ 180 题解

LeetCode 176. 第二高的薪水（SQL 中等）

【题目描述】

Employee 表：

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| salary      | int  |
+-------------+------+
id 是这个表的主键。
表的每一行包含员工的工资信息。

查询并返回 Employee 表中第二高的不同薪水。如果不存在第二高的薪水，查询应该返回 null（Pandas 则返回 None）。

查询结果如下例所示。

【示例 1】

输入：
Employee 表：
+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+输出：
+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+

【示例 2】

输入：
Employee 表：
+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
+----+--------+输出：
+---------------------+
| SecondHighestSalary |
+---------------------+
| null                |
+---------------------+

---

【分析】

本题有多种解法：

• 方法一：可以先从 Employee 表中查询 Salary 列，并且使用 DISTINCT 关键字去除重复的工资值。然后使用 ORDER BY Salary DESC 将查询结果按照 Salary 列的值进行降序排列，接着使用 LIMIT 1 OFFSET 1 跳过 1 行，并限制输出结果只有 1 行，也就是只输出第二行。然而，如果没有第二高的薪资，即表里可能只有一条记录，这种情况下查询会返回一个空结果集，而不是 NULL，因此可以使用子查询，如果子查询没有返回任何值，外层的 SELECT 会将结果视为 NULL，因此，整个查询会返回 NULL。
• 方法二：先使用 SELECT MAX(Salary) FROM Employee 查询表中的最大工资值，然后将小于最大工资作为查询条件再查一遍表，然后返回查询结果的最大值就是整个表中第二大的值。

---

【代码】

【方法一】

# Write your MySQL query statement below
SELECT (SELECT DISTINCT SalaryFROM EmployeeORDER BY Salary DESCLIMIT 1 OFFSET 1
) AS SecondHighestSalary;

【方法二】

# Write your MySQL query statement below
SELECT MAX(Salary) AS SecondHighestSalary
FROM Employee
WHERE Salary < (SELECT MAX(Salary) FROM Employee);

LeetCode 177. 第 N 高的薪水（SQL 中等）

【题目描述】

表：Employee

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| salary      | int  |
+-------------+------+
id 是该表的主键（列中的值互不相同）。
该表的每一行都包含有关员工工资的信息。

编写一个解决方案查询 Employee 表中第 $n$ 高的不同工资。如果少于 $n$ 个不同工资，查询结果应该为 null。

查询结果格式如下所示。

【示例 1】

输入: 
Employee table:
+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+
n = 2输出: 
+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| 200                    |
+------------------------+

【示例 2】

输入: 
Employee 表:
+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
+----+--------+
n = 2输出: 
+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| null                   |
+------------------------+

---

【分析】

与上一题类似，直接使用第一种方法将偏移量设置为 $n-1$ 即可，需要注意的是 LIMIT 语句中不能有表达式，要先把 $n-1$ 计算出来。

也可以使用窗口函数（Window Function）DENSE_RANK() 为工资值按降序排列计算排名。DENSE_RANK() 函数为相同值分配相同的排名，并且不会跳过后续的排名。然后使用 WHERE ranking = N 来过滤数据，保留排名等于传入参数 N 的行，该方法也适用于上一题。

OVER 关键字是 SQL 中用于定义窗口函数的作用范围和行为的关键字，它允许你在一个查询中对一组相关行进行计算，而无需像聚合函数那样将它们分组到一个单独的行中。

---

【代码】

【方法一】

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGINDECLARE M INT;SET M = N - 1;RETURN (# Write your MySQL query statement below.SELECT (SELECT DISTINCT SalaryFROM EmployeeORDER BY Salary DESCLIMIT 1 OFFSET M));
END

【方法二】

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGINRETURN (# Write your MySQL query statement below.SELECT IF(COUNT(*), RKSalary.Salary, NULL)  # count(*) 计算查询结果的数量，若不为空则返回 Salary 列，否则返回 NULLFROM (SELECT Salary, DENSE_RANK() OVER(ORDER BY Salary DESC) as RKFROM Employee) AS RKSalary  # 子查询生成的派生表必须有一个别名WHERE RKSalary.RK = N);
END

LeetCode 178. 分数排名（SQL 中等）

【题目描述】

表：Scores

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| score       | decimal |
+-------------+---------+
id 是该表的主键（有不同值的列）。
该表的每一行都包含了一场比赛的分数。score 是一个有两位小数点的浮点值。

编写一个解决方案来查询分数的排名。排名按以下规则计算：

• 分数应按从高到低排列。
• 如果两个分数相等，那么两个分数的排名应该相同。
• 在排名相同的分数后，排名数应该是下一个连续的整数。换句话说，排名之间不应该有空缺的数字。

按 score 降序返回结果表。

查询结果格式如下所示。

【示例 1】

Scores 表:
+----+-------+
| id | score |
+----+-------+
| 1  | 3.50  |
| 2  | 3.65  |
| 3  | 4.00  |
| 4  | 3.85  |
| 5  | 4.00  |
| 6  | 3.65  |
+----+-------+输出: 
+-------+------+
| score | rank |
+-------+------+
| 4.00  | 1    |
| 4.00  | 1    |
| 3.85  | 2    |
| 3.65  | 3    |
| 3.65  | 3    |
| 3.50  | 4    |
+-------+------+

---

【分析】

上一题中用到的窗口函数 DENSE_RANK() 正适合用来解决本题。此外还有另一种思路，每个分数的排名就是表经过去重后大于等于当前分数的数量，例如对于样例中的 3.85，去重后大于当前数的值为 4.00 和 3.85，即当前数的排名为 2。

---

【代码】

【方法一】

# Write your MySQL query statement below
SELECT score, DENSE_RANK() OVER(ORDER BY score DESC) AS "rank"  # rank 是关键字，因此需要用引号
FROM Scores;

【方法二】

# Write your MySQL query statement below
SELECT S1.score, (SELECT COUNT(DISTINCT S2.score)FROM Scores S2WHERE S2.score >= S1.score
) AS "rank"
FROM Scores S1
ORDER BY S1.score DESC;

LeetCode 179. 最大数（中等）

【题目描述】

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

【示例 1】

输入：nums = [10,2]
输出："210"

【示例 2】

输入：nums = [3,30,34,5,9]
输出："9534330"

【提示】

$1<=nums.length<=100$
$0<=nums[i]<=10^9$

---

【分析】

本题的思路也比较难想，需要定义一种新的比较方式：

• $a=b⟺ab=ba$
• $a\le b⟺ab\le ba$
• $a\ge b⟺ab\ge ba$

例如我们现在有两个数 123 和 45，由于 $12345<45123$，因此 $123<45$。

假设最大的整数表示为：$s_1{s}_2{s}_3\dots s_n$，那么说明该排序算法从大到小排序后的结果为：$s_1\ge s_2\ge s_3\ge \cdots \ge s_n$。若存在 $s_i<s_{i+1}$ 的情况，说明 $s_i{s}_{i+1}<s_{i+1}{s}_i$，而当前数为最大整数，因此产生了冲突，说明排序算法从大到小排序后的结果一定是最大整数。

到这里还没有完全结束，因为这个比较方式是我们自己定义的，还需要证明这个方式能够正确排序，例如不能出现 $a<b$、$b<c$、$c<a$ 的情况。这是离散数学中的一个概念，一个能够排序的关系被称为全序关系，需要满足以下三个性质：

• 若 $a\le b$ 且 $b\le a$，则 $a=b$（反对称性）；
• 若 $a\le b$ 且 $b\le c$，则 $a\le c$（传递性）；
• $a\le b$ 或 $b\le a$（完全性）。

我们证明一下这三个性质：

• 若 $ab\le ba$ 且 $ba\le ab$，而其中的比较方式为具有全序关系的字典序比较，因此能推出 $ab=ba$；
• 若 $ab\le ba$ 且 $bc\le cb$，假设 $a,b,c$ 的长度分别为 $x,y,z$，因此 $ab$ 的长度等于 $ba$，字典序也就可以转化为普通整数的比较，即 $a\ast 10^y+b\le b\ast 10^x+a\Rightarrow a(10^y-1)\le b(10^x-1)\Rightarrow \frac{a}{b}\le \frac{(10^x-1)}{(10^y-1)}$，同理 $\frac{b}{c}\le \frac{(10^y-1)}{(10^z-1)}$，将两个不等式的左右两边分别同时相乘可以得到 $\frac{a}{c}\le \frac{(10^x-1)}{(10^z-1)}$，这个式子就表示 $ac\le ca$；
• 显然任何的 $ab$ 和 $ba$ 之间都能进行字典序比较，满足完全性。

---

【代码】

class Solution {
public:string largestNumber(vector<int>& nums) {sort(nums.begin(), nums.end(), [](int a, int b){string sa = to_string(a), sb = to_string(b);return sa + sb > sb + sa;});if (nums[0] == 0) return "0";  // 如果全为 0 那么结果只保留一个 0string res;for (int x: nums) res += to_string(x);return res;}
};

LeetCode 180. 连续出现的数字（SQL 中等）

【题目描述】

表：Logs

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| num         | varchar |
+-------------+---------+
在 SQL 中，id 是该表的主键。
id 是一个自增列。

找出所有至少连续出现三次的数字。

返回的结果表中的数据可以按任意顺序排列。

结果格式如下面的例子所示：

【示例 1】

输入：
Logs 表：
+----+-----+
| id | num |
+----+-----+
| 1  | 1   |
| 2  | 1   |
| 3  | 1   |
| 4  | 2   |
| 5  | 1   |
| 6  | 2   |
| 7  | 2   |
+----+-----+输出：
Result 表：
+-----------------+
| ConsecutiveNums |
+-----------------+
| 1               |
+-----------------+解释：1 是唯一连续出现至少三次的数字。

---

【分析】

最简单的方式就是直接查询三个 Logs 表，在 WHERE 语句中判断这三行的 id 是否连续且 num 相等。

此外还可以使用窗口函数 ROW_NUMBER() 为每个分区内的行分配唯一的行号，即使用 CAST(ROW_NUMBER() OVER(PARTITION BY num ORDER BY id) AS SIGNED) AS rn 语句将数据按 num 值分区，使得每个 num 值都有自己的计数序列，接着在每个分区内，按 id 值的升序为行分配行号：

+----+-----+           +----+-----+----+
| id | num |           | id | num | rn |
+----+-----+           +----+-----+----+
| 1  | 1   |           | 1  | 1   | 1  |
| 2  | 1   |           | 2  | 1   | 2  |
| 3  | 1   |     =>    | 3  | 1   | 3  |
| 4  | 2   |           | 5  | 1   | 4  |
| 5  | 1   |           | 4  | 2   | 1  |
| 6  | 2   |           | 6  | 2   | 2  |
| 7  | 2   |           | 7  | 2   | 3  |
+----+-----+           +----+-----+----+

CAST(... AS SIGNED) 将 ROW_NUMBER() 的结果转换为有符号整数类型。这是因为 ROW_NUMBER() 返回的是 BIGINT UNSIGNED 类型，而后续的计算需要使用有符号整数。

接下来使用 GROUP BY num, rn - id 语句将查询结果按 num 列以及 rn - id 的计算结果进行分组。目的是识别和组合具有相同 num 值且连续的 id 值的行，因为如果 id 连续，rn - id 的值会相同：

+----+-----+----+---------+
| id | num | rn | rn - id |
+----+-----+----+---------+
| 1  | 1   | 1  |  0      |
| 2  | 1   | 2  |  0      |
| 3  | 1   | 3  |  0      |
| 5  | 1   | 4  | -1      |
| 4  | 2   | 1  | -3      |
| 6  | 2   | 2  | -4      |
| 7  | 2   | 3  | -4      |
+----+-----+----+---------+

最后使用 HAVING COUNT(num) >= 3 语句对 GROUP BY 生成的分组结果进行过滤，只保留满足连续出现至少 3 次相同 num 的组。

---

【代码】

【方法一】

# Write your MySQL query statement below
SELECT DISTINCT L1.num AS ConsecutiveNums
FROM Logs L1, Logs L2, Logs L3
WHERE L1.id = L2.id - 1 AND L2.id = L3.id - 1 AND L1.num = L2.num AND L2.num = L3.num;

【方法二】

# Write your MySQL query statement below
SELECT DISTINCT num AS ConsecutiveNums
FROM (SELECT id, num, CAST(ROW_NUMBER() OVER(PARTITION BY num ORDER BY id) AS SIGNED) AS rnFROM Logs
) AS Logs_RN
GROUP BY Logs_RN.num, Logs_RN.rn - Logs_RN.id
HAVING COUNT(num) >= 3;