算法刷题记录——LeetCode篇(7) [第601~700题](持续更新)

更新时间：2025-03-22

• LeetCode刷题目录：算法刷题记录——专题目录汇总
• 技术博客总目录：计算机技术系列博客——目录页

优先整理热门100及面试150，不定期持续更新，欢迎关注！

---

601. 体育馆的人流量

表：Stadium

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| id            | int     |
| visit_date    | date    |
| people        | int     |
+---------------+---------+

visit_date 是该表中具有唯一值的列。
每日人流量信息被记录在这三列信息中：序号 (id)、日期 (visit_date)、 人流量 (people)，每天只有一行记录，日期随着 id 的增加而增加。

编写解决方案找出每行的人数大于或等于 100 且 id 连续的三行或更多行记录。
返回按 visit_date 升序排列 的结果表。

查询结果格式如下所示。

示例 1:

输入：

Stadium 表:

+------+------------+-----------+
| id   | visit_date | people    |
+------+------------+-----------+
| 1    | 2017-01-01 | 10        |
| 2    | 2017-01-02 | 109       |
| 3    | 2017-01-03 | 150       |
| 4    | 2017-01-04 | 99        |
| 5    | 2017-01-05 | 145       |
| 6    | 2017-01-06 | 1455      |
| 7    | 2017-01-07 | 199       |
| 8    | 2017-01-09 | 188       |
+------+------------+-----------+

输出：

+------+------------+-----------+
| id   | visit_date | people    |
+------+------------+-----------+
| 5    | 2017-01-05 | 145       |
| 6    | 2017-01-06 | 1455      |
| 7    | 2017-01-07 | 199       |
| 8    | 2017-01-09 | 188       |
+------+------------+-----------+

解释：
- id 为 5、6、7、8 的四行 id 连续，并且每行都有 >= 100 的人数记录。
- 请注意，即使第 7 行和第 8 行的 visit_date 不是连续的，输出也应当包含第 8 行，因为我们只需要考虑 id 连续的记录。
- 不输出 id 为 2 和 3 的行，因为至少需要三条 id 连续的记录。

---

解题方法

使用窗口函数来识别连续的ID。具体步骤如下：

1. 筛选数据：首先用filtered临时表筛选出所有人数大于或等于100的记录。
2. 计算分组标识：通过计算id - ROW_NUMBER() OVER (ORDER BY id)得到一个分组标识grp。连续的ID将具有相同的grp值。
3. 统计连续组：统计每个grp分组的记录数，子查询筛选出记录数大于或等于3的组。
4. 提取结果：根据筛选出的分组标识，提取对应的所有记录，并按日期visit_date排序输出。

代码实现(SQL)：

WITH filtered AS (SELECT id, visit_date, people,id - ROW_NUMBER() OVER (ORDER BY id) AS grpFROM StadiumWHERE people >= 100
)
SELECT id, visit_date, people
FROM filtered
WHERE grp IN (SELECT grpFROM filteredGROUP BY grpHAVING COUNT(*) >= 3
)
ORDER BY visit_date;

---

602. 好友申请 II ：谁有最多的好友

RequestAccepted 表：

+----------------+---------+
| Column Name    | Type    |
+----------------+---------+
| requester_id   | int     |
| accepter_id    | int     |
| accept_date    | date    |
+----------------+---------+

(requester_id, accepter_id) 是这张表的主键(具有唯一值的列的组合)。
这张表包含发送好友请求的人的 ID ，接收好友请求的人的 ID ，以及好友请求通过的日期。

编写解决方案，找出拥有最多的好友的人和他拥有的好友数目。
生成的测试用例保证拥有最多好友数目的只有 1 个人。

查询结果格式如下例所示。

示例 1：

输入：

RequestAccepted 表：
+--------------+-------------+-------------+
| requester_id | accepter_id | accept_date |
+--------------+-------------+-------------+
| 1            | 2           | 2016/06/03  |
| 1            | 3           | 2016/06/08  |
| 2            | 3           | 2016/06/08  |
| 3            | 4           | 2016/06/09  |
+--------------+-------------+-------------+

输出：

+----+-----+
| id | num |
+----+-----+
| 3  | 3   |
+----+-----+

解释：
- 编号为 3 的人是编号为 1 ，2 和 4 的人的好友，所以他总共有 3 个好友，比其他人都多。

进阶：
在真实世界里，可能会有多个人拥有好友数相同且最多，你能找到所有这些人吗？

---

解题方法

统计每个人的好友总数，并找出拥有最多好友的人及其数目。每个好友请求的双方（请求者和接受者）都会增加各自的好友数。因此，将请求者和接受者的ID合并统计出现次数，次数最多的即为结果。

代码解释

1. 合并ID列：使用UNION ALL将requester_id和accepter_id合并为一个临时表combined，包含所有用户的ID。
2. 统计次数：按id分组统计每个用户出现的次数，即好友总数。
3. 排序取最大值：按好友数降序排序，使用LIMIT 1获取最大值对应的用户。

代码实现(SQL)：

SELECT id, COUNT(*) AS num
FROM (SELECT requester_id AS id FROM RequestAcceptedUNION ALLSELECT accepter_id AS id FROM RequestAccepted
) AS combined
GROUP BY id
ORDER BY num DESC
LIMIT 1;

进阶解法

若存在多个用户好友数相同且最大，可通过子查询计算最大值，并返回所有匹配该值的用户。

代码实现(SQL)：

WITH counts AS (SELECT id, COUNT(*) AS numFROM (SELECT requester_id AS id FROM RequestAcceptedUNION ALLSELECT accepter_id AS id FROM RequestAccepted) AS tGROUP BY id
)
SELECT id, num
FROM counts
WHERE num = (SELECT MAX(num) FROM counts);

---

605. 种花问题

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。

示例 1：

输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

示例 2：

输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

提示：

• 1 <= flowerbed.length <= 2 * 10^4
• flowerbed[i] 为 0 或 1
• flowerbed 中不存在相邻的两朵花
• 0 <= n <= flowerbed.length

---

方法：贪心算法

遍历花坛数组，当遇到一个位置是0，并且其左右相邻的位置都是0或者越界时，就在此处种花，并跳过下一个位置。最后统计可以种的花的数量是否大于等于n。

1. 初始化变量：count用于记录可以种的花的数量，len为数组长度，i为当前遍历的位置。
2. 遍历数组：使用while循环遍历数组，直到处理完所有元素。
3. 检查当前位置：如果当前位置为0，判断其左右是否满足种花条件。
4. 种花并跳过下一位置：如果满足条件，种花（count加1），并跳过下一个位置（i += 2）。
5. 返回结果：最后比较可种花的数量是否大于等于n。

代码实现(Java)：

class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {int count = 0;int len = flowerbed.length;int i = 0;while (i < len) {if (flowerbed[i] == 0) {boolean prevOk = (i == 0) || (flowerbed[i - 1] == 0);boolean nextOk = (i == len - 1) || (flowerbed[i + 1] == 0);if (prevOk && nextOk) {count++;i += 2; // 跳过下一个位置continue;}}i++;}return count >= n;}
}

复杂度分析

• 时间复杂度：O(n)，其中n是数组的长度。我们只需遍历数组一次。
• 空间复杂度：O(1)，仅使用常数级别的额外空间。

---

606. 根据二叉树创建字符串

给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。

空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例 1：

输入：root = [1,2,3,4]
输出："1(2(4))(3)"

解释：初步转化后得到 “1(2(4)())(3()())” ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。

示例 2：

输入：root = [1,2,3,null,4]
输出："1(2()(4))(3)"

解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。

提示：

• 树中节点的数目范围是 [1, 10^4]
• -1000 <= Node.val <= 1000

---

解题方法

将二叉树转换为特定格式的字符串，遵循前序遍历的顺序，并省略不必要的空括号。

1. 前序遍历：先处理当前节点，再处理左子树，最后处理右子树。
2. 括号规则：
   • 左子树为空但右子树存在时，必须为左子树保留空括号()。
   • 右子树为空时，无论左子树是否存在，都不需要处理右子树的括号。

代码实现(Java)：

class Solution {public String tree2str(TreeNode root) {StringBuilder sb = new StringBuilder();helper(root, sb);return sb.toString();}private void helper(TreeNode node, StringBuilder sb) {if (node == null) return;sb.append(node.val);// 当左或右子节点存在时，处理括号if (node.left != null || node.right != null) {// 处理左子节点if (node.left != null) {sb.append("(");helper(node.left, sb);sb.append(")");} else {sb.append("()"); // 左空但右存在时，必须添加空括号}// 处理右子节点if (node.right != null) {sb.append("(");helper(node.right, sb);sb.append(")");}}}
}

复杂度分析

• 时间复杂度：O(n)，其中n是二叉树的节点数。每个节点被访问一次。
• 空间复杂度：O(h)，h是树的高度，递归调用栈的深度。最坏情况下（树退化为链表）为O(n)。

---

607. 销售员

表: SalesPerson

+-----------------+---------+
| Column Name     | Type    |
+-----------------+---------+
| sales_id        | int     |
| name            | varchar |
| salary          | int     |
| commission_rate | int     |
| hire_date       | date    |
+-----------------+---------+

sales_id 是该表的主键列(具有唯一值的列)。
该表的每一行都显示了销售人员的姓名和 ID ，以及他们的工资、佣金率和雇佣日期。

表: Company

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| com_id      | int     |
| name        | varchar |
| city        | varchar |
+-------------+---------+

com_id 是该表的主键列(具有唯一值的列)。
该表的每一行都表示公司的名称和 ID ，以及公司所在的城市。

表: Orders

+-------------+------+
| Column Name | Type |
+-------------+------+
| order_id    | int  |
| order_date  | date |
| com_id      | int  |
| sales_id    | int  |
| amount      | int  |
+-------------+------+

order_id 是该表的主键列(具有唯一值的列)。
com_id 是 Company 表中 com_id 的外键（reference 列）。
sales_id 是来自销售员表 sales_id 的外键（reference 列）。
该表的每一行包含一个订单的信息。这包括公司的 ID 、销售人员的 ID 、订单日期和支付的金额。

编写解决方案，找出没有任何与名为 “RED” 的公司相关的订单的所有销售人员的姓名。

以 任意顺序 返回结果表。

返回结果格式如下所示。

示例 1：

输入：
SalesPerson 表:

+----------+------+--------+-----------------+------------+
| sales_id | name | salary | commission_rate | hire_date  |
+----------+------+--------+-----------------+------------+
| 1        | John | 100000 | 6               | 4/1/2006   |
| 2        | Amy  | 12000  | 5               | 5/1/2010   |
| 3        | Mark | 65000  | 12              | 12/25/2008 |
| 4        | Pam  | 25000  | 25              | 1/1/2005   |
| 5        | Alex | 5000   | 10              | 2/3/2007   |
+----------+------+--------+-----------------+------------+

Company 表:

+--------+--------+----------+
| com_id | name   | city     |
+--------+--------+----------+
| 1      | RED    | Boston   |
| 2      | ORANGE | New York |
| 3      | YELLOW | Boston   |
| 4      | GREEN  | Austin   |
+--------+--------+----------+

Orders 表:

+----------+------------+--------+----------+--------+
| order_id | order_date | com_id | sales_id | amount |
+----------+------------+--------+----------+--------+
| 1        | 1/1/2014   | 3      | 4        | 10000  |
| 2        | 2/1/2014   | 4      | 5        | 5000   |
| 3        | 3/1/2014   | 1      | 1        | 50000  |
| 4        | 4/1/2014   | 1      | 4        | 25000  |
+----------+------------+--------+----------+--------+

输出：

+------+
| name |
+------+
| Amy  |
| Mark |
| Alex |
+------+

解释：
- 根据表 orders 中的订单 ‘3’ 和 ‘4’ ，容易看出只有 ‘John’ 和 ‘Pam’ 两个销售员曾经向公司 ‘RED’ 销售过。
- 所以我们需要输出表 salesperson 中所有其他人的名字。

---

方法一：子查询（NOT IN）

1. 关联订单和公司：通过 JOIN 将 Orders 和 Company 表连接，筛选出公司名称为“RED”的订单。
2. 获取相关销售ID：提取这些订单对应的销售员ID，并使用 DISTINCT 去重。
3. 排除这些销售员：在 SalesPerson 表中筛选出不在上述销售员ID列表中的记录。

代码实现(SQL)：

SELECT name
FROM SalesPerson
WHERE sales_id NOT IN (SELECT DISTINCT o.sales_idFROM Orders oJOIN Company c ON o.com_id = c.com_idWHERE c.name = 'RED'
);

方法二：左连接 + NULL 检查

1. 子查询：获取所有与“RED”公司相关的订单的 sales_id。
2. 左连接：将销售员表与上述结果左连接，未匹配的记录 sales_id 为 NULL。
3. 筛选：通过 WHERE 条件过滤出未匹配的销售员。

代码实现(SQL)：

SELECT s.name
FROM SalesPerson s
LEFT JOIN (SELECT o.sales_idFROM Orders oJOIN Company c ON o.com_id = c.com_idWHERE c.name = 'RED'
) AS red_orders ON s.sales_id = red_orders.sales_id
WHERE red_orders.sales_id IS NULL;

对比总结

• 子查询（NOT IN）：适合大多数场景，DISTINCT 确保去重，提升效率。
• 左连接 + NULL 检查：利用连接特性，可能在大数据量下更高效，但逻辑稍复杂。

---

608. 树节点

表：Tree

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| p_id        | int  |
+-------------+------+

id 是该表中具有唯一值的列。
该表的每行包含树中节点的 id 及其父节点的 id 信息。
给定的结构总是一个有效的树。

树中的每个节点可以是以下三种类型之一：

• “Leaf”：节点是叶子节点。
• “Root”：节点是树的根节点。
• “lnner”：节点既不是叶子节点也不是根节点。

编写一个解决方案来报告树中每个节点的类型。
以 任意顺序 返回结果表。

结果格式如下所示。

示例 1：

输入：
Tree table:

+----+------+
| id | p_id |
+----+------+
| 1  | null |
| 2  | 1    |
| 3  | 1    |
| 4  | 2    |
| 5  | 2    |
+----+------+

输出：

+----+-------+
| id | type  |
+----+-------+
| 1  | Root  |
| 2  | Inner |
| 3  | Leaf  |
| 4  | Leaf  |
| 5  | Leaf  |
+----+-------+

解释：
- 节点 1 是根节点，因为它的父节点为空，并且它有子节点 2 和 3。
- 节点 2 是一个内部节点，因为它有父节点 1 和子节点 4 和 5。
- 节点 3、4 和 5 是叶子节点，因为它们有父节点而没有子节点。

示例 2：

输入：
Tree table:

+----+------+
| id | p_id |
+----+------+
| 1  | null |
+----+------+

输出：

+----+-------+
| id | type  |
+----+-------+
| 1  | Root  |
+----+-------+

解释：如果树中只有一个节点，则只需要输出其根属性。

---

解题方法

根据以下条件判断树中每个节点的类型：

• 根节点（Root）：节点的 p_id 为 NULL。
• 内部节点（Inner）：节点的 p_id 不为 NULL，并且其 id 存在于其他节点的 p_id 中（即有子节点）。
• 叶子节点（Leaf）：节点的 p_id 不为 NULL，但其 id 不存在于其他节点的 p_id 中（即无子节点）。

代码实现(SQL)：

SELECT id,CASE WHEN p_id IS NULL THEN 'Root'WHEN id IN (SELECT DISTINCT p_id FROM Tree) THEN 'Inner'ELSE 'Leaf'END AS type
FROM Tree
ORDER BY id;

---

609. 在系统中查找重复文件

给你一个目录信息列表 paths ，包括目录路径，以及该目录中的所有文件及其内容，请你按路径返回文件系统中的所有重复文件。答案可按 任意顺序 返回。

一组重复的文件至少包括 两个 具有完全相同内容的文件。

输入 列表中的单个目录信息字符串的格式如下：

"root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"

这意味着，在目录 root/d1/d2/.../dm 下，有 n 个文件( f1.txt, f2.txt ... fn.txt )的内容分别是( f1_content, f2_content ... fn_content )。注意: n >= 1 且 m >= 0 。如果 m = 0 ，则表示该目录是根目录。

输出 是由 重复文件路径组 构成的列表。其中每个组由所有具有相同内容文件的文件路径组成。文件路径是具有下列格式的字符串：

"directory_path/file_name.txt"

示例 1：

输入：paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"]
输出：[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]

示例 2：

输入：paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)"]
输出：[["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]

提示：

• 1 <= paths.length <= 2 * 10^4
• 1 <= paths[i].length <= 3000
• 1 <= sum(paths[i].length) <= 5 * 10^5
• paths[i] 由英文字母、数字、字符 '/'、'.'、'('、')' 和 ' ' 组成
• 你可以假设在同一目录中没有任何文件或目录共享相同的名称。
• 你可以假设每个给定的目录信息代表一个唯一的目录。目录路径和文件信息用单个空格分隔。

进阶：

• 假设您有一个真正的文件系统，您将如何搜索文件？广度搜索还是宽度搜索？
• 如果文件内容非常大（GB级别），您将如何修改您的解决方案？
• 如果每次只能读取 1 kb 的文件，您将如何修改解决方案？
• 修改后的解决方案的时间复杂度是多少？其中最耗时的部分和消耗内存的部分是什么？如何优化？
• 如何确保您发现的重复文件不是误报？

---

解题方法

根据给定的文件路径信息，找出所有内容重复的文件组。每个重复组至少包含两个文件。通过哈希表记录每个内容对应的所有文件路径，最后筛选出重复的文件组。

1. 初始化哈希表：contentMap 用于将文件内容映射到对应的文件路径列表。
2. 解析路径字符串：使用正则表达式分割路径字符串，获取目录和文件项。
3. 处理每个文件项：提取文件名和内容，构建完整路径并存入哈希表。
4. 收集结果：遍历哈希表，将长度大于等于2的列表加入结果。

代码实现(Java)：

class Solution {public List<List<String>> findDuplicate(String[] paths) {Map<String, List<String>> contentMap = new HashMap<>();for (String path : paths) {String[] parts = path.split("\\s+");if (parts.length < 2) continue; // 确保至少有一个文件项String directory = parts[0];for (int i = 1; i < parts.length; i++) {String filePart = parts[i];int leftBracket = filePart.indexOf('(');int rightBracket = filePart.lastIndexOf(')');String fileName = filePart.substring(0, leftBracket);String content = filePart.substring(leftBracket + 1, rightBracket);String filePath = directory + "/" + fileName;contentMap.computeIfAbsent(content, k -> new ArrayList<>()).add(filePath);}}List<List<String>> result = new ArrayList<>();for (List<String> files : contentMap.values()) {if (files.size() >= 2) {result.add(files);}}return result;}
}

复杂度分析

• 时间复杂度：O(n * m)，其中 n 是路径数量，m 是平均每个路径中的文件数。哈希表操作平均为 O(1)。
• 空间复杂度：O(n * m)，存储所有文件路径及其内容。

---

610. 判断三角形

表: Triangle

+-------------+------+
| Column Name | Type |
+-------------+------+
| x           | int  |
| y           | int  |
| z           | int  |
+-------------+------+

在 SQL 中，(x, y, z)是该表的主键列。
该表的每一行包含三个线段的长度。
对每三个线段报告它们是否可以形成一个三角形。
以 任意顺序 返回结果表。

查询结果格式如下所示。

示例 1:

输入：
Triangle 表:

+----+----+----+
| x  | y  | z  |
+----+----+----+
| 13 | 15 | 30 |
| 10 | 20 | 15 |
+----+----+----+

输出：

+----+----+----+----------+
| x  | y  | z  | triangle |
+----+----+----+----------+
| 13 | 15 | 30 | No       |
| 10 | 20 | 15 | Yes      |
+----+----+----+----------+

---

方法一

判断三个线段能否构成三角形需满足任意两边之和大于第三边。等价于最大边小于其他两边之和。使用 GREATEST 函数找到最大边，判断剩余两边之和是否大于最大边。

代码实现(SQL)：

SELECT x,y,z,CASE WHEN x + y > z AND x + z > y AND y + z > x THEN 'Yes'ELSE 'No'END AS triangle
FROM Triangle;

方法二：数学优化

代码实现(SQL)：

SELECT x,y,z,IF( (x + y + z - GREATEST(x, y, z)) > GREATEST(x, y, z), 'Yes', 'No') AS triangle
FROM Triangle;

---

声明

1. 本文版权归 CSDN 用户 Allen Wurlitzer 所有，遵循CC-BY-SA协议发布，转载请注明出处。
2. 本文题目来源 力扣-LeetCode ，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

(持续更新，未完待续)