【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 Salary
FROM Employee
ORDER BY Salary DESC
LIMIT 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 n 高的差别工资。假如少于 n 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 n - 1 n−1 即可，需要注意的是 LIMIT 语句中不能有表达式，要先把 n − 1 n - 1 n−1 计算出来。
也可以使用窗口函数（Window Function）DENSE_RANK() 为工资值按降序排列计算排名。DENSE_RANK() 函数为相同值分配相同的排名，而且不会跳过后续的排名。然后使用 WHERE ranking = N 来过滤数据，保存排名便是传入参数 N 的行，该方法也实用于上一题。
OVER 关键字是 SQL 中用于定义窗口函数的作用范围和行为的关键字，它允许你在一个查询中对一组相关行举行计算，而无需像聚合函数那样将它们分组到一个单独的行中。
【代码】
【方法一】
CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
DECLARE M INT;
SET M = N - 1;
RETURN (
# Write your MySQL query statement below.
SELECT (
SELECT DISTINCT Salary
FROM Employee
ORDER BY Salary DESC
LIMIT 1 OFFSET M
)
);
END
【方法二】
CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
RETURN (
# Write your MySQL query statement below.
SELECT IF(COUNT(*), RKSalary.Salary, NULL)# count(*) 计算查询结果的数量，若不为空则返回 Salary 列，否则返回 NULL
FROM (
SELECT Salary, DENSE_RANK() OVER(ORDER BY Salary DESC) as RK
FROM 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 S2
WHERE S2.score >= S1.score
) AS "rank"
FROM Scores S1
ORDER BY S1.score DESC;
LeetCode 179. 最大数（中等）
【标题描述】
给定一组非负整数 nums，重新排列每个数的次序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，以是你需要返回一个字符串而不是整数。
【示例 1】
输入：nums =
输出："210"
【示例 2】
输入：nums =
输出："9534330"
【提示】
1 < = n u m s . l e n g t h < = 100 1 <= nums.length <= 100 1<=nums.length<=100
0 < = n u m s [ i ] < = 1 0 9 0 <= nums <= 10^9 0<=nums<=109
【分析】
本题的思绪也比力难想，需要定义一种新的比力方式：
[*] a = b ⟺ a b = b a a = b \iff ab = ba a=b⟺ab=ba
[*] a ≤ b ⟺ a b ≤ b a a \le b \iff ab \le ba a≤b⟺ab≤ba
[*] a ≥ b ⟺ a b ≥ b a a \ge b \iff ab \ge ba a≥b⟺ab≥ba
例如我们如今有两个数 123 和 45，由于 12345 < 45123 12345 < 45123 12345<45123，因此 123 < 45 123 < 45 123<45。
假设最大的整数表示为： s 1 s 2 s 3 … s n s_1s_2s_3\dots s_n s1s2s3…sn，那么阐明该排序算法从大到小排序后的结果为： s 1 ≥ s 2 ≥ s 3 ≥ ⋯ ≥ s n s_1 \ge s_2 \ge s_3 \ge \dots \ge s_n s1≥s2≥s3≥⋯≥sn。若存在 s i < s i + 1 s_i < s_{i + 1} si<si+1 的情况，阐明 s i s i + 1 < s i + 1 s i s_is_{i + 1} < s_{i + 1}s_i sisi+1<si+1si，而当前数为最大整数，因此产生了辩论，阐明排序算法从大到小排序后的结果一定是最大整数。
到这里还没有完全结束，因为这个比力方式是我们本身定义的，还需要证实这个方式能够正确排序，例如不能出现 a < b a < b a<b、 b < c b < c b<c、 c < a c < a c<a 的情况。这是离散数学中的一个概念，一个能够排序的关系被称为全序关系，需要满意以下三个性质：
[*]若 a ≤ b a \le b a≤b 且 b ≤ a b \le a b≤a，则 a = b a = b a=b（反对称性）；
[*]若 a ≤ b a \le b a≤b 且 b ≤ c b \le c b≤c，则 a ≤ c a \le c a≤c（传递性）；
[*] a ≤ b a \le b a≤b 或 b ≤ a b \le a b≤a（完全性）。
我们证实一下这三个性质：
[*]若 a b ≤ b a ab \le ba ab≤ba 且 b a ≤ a b ba \le ab ba≤ab，而其中的比力方式为具有全序关系的字典序比力，因此能推出 a b = b a ab = ba ab=ba；
[*]若 a b ≤ b a ab \le ba ab≤ba 且 b c ≤ c b bc \le cb bc≤cb，假设 a , b , c a, b, c a,b,c 的长度分别为 x , y , z x, y, z x,y,z，因此 a b ab ab 的长度便是 b a ba ba，字典序也就可以转化为平常整数的比力，即 a ∗ 1 0 y + b ≤ b ∗ 1 0 x + a ⇒ a ( 1 0 y − 1 ) ≤ b ( 1 0 x − 1 ) ⇒ a b ≤ ( 1 0 x − 1 ) ( 1 0 y − 1 ) a * 10^y + b \le b * 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)} a∗10y+b≤b∗10x+a⇒a(10y−1)≤b(10x−1)⇒ba≤(10y−1)(10x−1)，同理 b c ≤ ( 1 0 y − 1 ) ( 1 0 z − 1 ) \frac{b}{c} \le \frac{(10^y - 1)}{(10^z - 1)} cb≤(10z−1)(10y−1)，将两个不等式的左右双方分别同时相乘可以得到 a c ≤ ( 1 0 x − 1 ) ( 1 0 z − 1 ) \frac{a}{c} \le \frac{(10^x - 1)}{(10^z - 1)} ca≤(10z−1)(10x−1)，这个式子就表示 a c ≤ c a ac \le ca ac≤ca；
[*]显然任何的 a b ab ab 和 b a ba 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) return "0";// 如果全为 0 那么结果只保留一个 0
string 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 rn
FROM Logs
) AS Logs_RN
GROUP BY Logs_RN.num, Logs_RN.rn - Logs_RN.id
HAVING COUNT(num) >= 3;
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]