刷题记录帖子

LC. 3121. Count the Number of Special Characters II

还是可以学习的。

我的解法

1. class Solution:
   
2.     def numberOfSpecialChars(self, word: str) -> int:
   
3.         index_dict_list = defaultdict(list)
   
4.         small_letters = []
   
5. 
   
6.         for ind, ch in enumerate(word):
   
7.             index_dict_list[ch].append(ind)
   
8.             if ch.islower() and ch not in small_letters:
   
9.                 small_letters.append(ch)
   
10.         
    
11.         ans = 0
    
12.         
    
13.         for ch in small_letters:
    
14.             if ch.upper() in index_dict_list and index_dict_list[ch][-1] < index_dict_list[ch.upper()][0]:
    
15.                 ans += 1
    
16.         
    
17.         return ans

复制代码

但是，

我们只关心小写的最后一次索引和大写的第一次索引，我们完全不需要把中间的索引都存下来！我们可以一边遍历，一边动态更新这两个极值。

1. class Solution:
   
2.     def numberOfSpecialChars(self, word: str) -> int:
   
3.         # 只记录关键索引，空间复杂度降为 O(1) (最多各存 26 个键值对)
   
4.         last_lower = {}
   
5.         first_upper = {}
   
6.         
   
7.         for i, ch in enumerate(word):
   
8.             if ch.islower():
   
9.                 # 不断覆盖，遍历结束时存的一定是“最后一次”的索引
   
10.                 last_lower[ch] = i
    
11.             else:
    
12.                 # 只有当大写字母还没出现过时才记录，保证是“第一次”的索引
    
13.                 if ch not in first_upper:
    
14.                     first_upper[ch] = i
    
15.                     
    
16.         ans = 0
    
17.         
    
18.         # 遍历所有出现过的小写字母
    
19.         for ch in last_lower:
    
20.             upper_ch = ch.upper()
    
21.             # 必须满足两个条件：
    
22.             # 1. 对应的大写字母存在
    
23.             # 2. 小写的最后一次索引 < 大写的第一次索引
    
24.             if upper_ch in first_upper and last_lower[ch] < first_upper[upper_ch]:
    
25.                 ans += 1
    
26.                
    
27.         return ans

复制代码

570. Managers with at Least 5 Direct Reports
Medium
Topics
conpanies icon
Companies
Hint
SQL Schema
Pandas Schema
Table: Employee

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| name        | varchar |
| department  | varchar |
| managerId   | int     |
+-------------+---------+
id is the primary key (column with unique values) for this table.
Each row of this table indicates the name of an employee, their department, and the id of their manager.
If managerId is null, then the employee does not have a manager.
No employee will be the manager of themself.


Write a solution to find managers with at least five direct reports.

Return the result table in any order.

The result format is in the following example.



Example 1:

Input:
Employee table:
+-----+-------+------------+-----------+
| id  | name  | department | managerId |
+-----+-------+------------+-----------+
| 101 | John  | A          | null      |
| 102 | Dan   | A          | 101       |
| 103 | James | A          | 101       |
| 104 | Amy   | A          | 101       |
| 105 | Anne  | A          | 101       |
| 106 | Ron   | B          | 101       |
+-----+-------+------------+-----------+
Output:
+------+
| name |
+------+
| John |
+------+

1. SELECT name
   
2. FROM Employee
   
3. WHERE id IN (
   
4.     SELECT managerId
   
5.     FROM Employee
   
6.     GROUP BY managerId
   
7.     HAVING COUNT(*) >= 5
   
8. );

复制代码

571. Find Median Given Frequency of Numbers
Hard
Topics
conpanies icon
Companies
SQL Schema
Pandas Schema
Table: Numbers

+-------------+------+
| Column Name | Type |
+-------------+------+
| num         | int  |
| frequency   | int  |
+-------------+------+
num is the primary key (column with unique values) for this table.
Each row of this table shows the frequency of a number in the database.


The median is the value separating the higher half from the lower half of a data sample.

Write a solution to report the median of all the numbers in the database after decompressing the Numbers table. Round the median to one decimal point.

The result format is in the following example.



Example 1:

Input:
Numbers table:
+-----+-----------+
| num | frequency |
+-----+-----------+
| 0   | 7         |
| 1   | 1         |
| 2   | 3         |
| 3   | 1         |
+-----+-----------+
Output:
+--------+
| median |
+--------+
| 0.0    |
+--------+
Explanation:
If we decompress the Numbers table, we will get [0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 3], so the median is (0 + 0) / 2 = 0.

1. WITH RunningTotal AS (
   
2.     SELECT
   
3.         num,
   
4.         frequency,
   
5.         -- 当前数字的累计频率
   
6.         SUM(frequency) OVER (ORDER BY num ASC) AS run_sum,
   
7.         -- 总频率
   
8.         SUM(frequency) OVER () AS total_sum
   
9.     FROM Numbers
   
10. )
    
11. SELECT ROUND(AVG(num * 1.0), 1) AS median
    
12. FROM RunningTotal
    
13. -- 检查中点是否落在当前数字的频率区间内
    
14. WHERE run_sum - frequency <= total_sum / 2.0
    
15.   AND run_sum >= total_sum / 2.0;

复制代码

574. Winning Candidate
Medium
Topics
SQL Schema
Pandas Schema
Table: Candidate

+-------------+----------+
| Column Name | Type     |
+-------------+----------+
| id          | int      |
| name        | varchar  |
+-------------+----------+
id is the column with unique values for this table.
Each row of this table contains information about the id and the name of a candidate.


Table: Vote

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| candidateId | int  |
+-------------+------+
id is an auto-increment primary key (column with unique values).
candidateId is a foreign key (reference column) to id from the Candidate table.
Each row of this table determines the candidate who got the ith vote in the elections.


Write a solution to report the name of the winning candidate (i.e., the candidate who got the largest number of votes).

The test cases are generated so that exactly one candidate wins the elections.

The result format is in the following example.



Example 1:

Input:
Candidate table:
+----+------+
| id | name |
+----+------+
| 1  | A    |
| 2  | B    |
| 3  | C    |
| 4  | D    |
| 5  | E    |
+----+------+
Vote table:
+----+-------------+
| id | candidateId |
+----+-------------+
| 1  | 2           |
| 2  | 4           |
| 3  | 3           |
| 4  | 2           |
| 5  | 5           |
+----+-------------+
Output:
+------+
| name |
+------+
| B    |
+------+
Explanation:
Candidate B has 2 votes. Candidates C, D, and E have 1 vote each.
The winner is candidate B.

1. SELECT name
   
2. FROM Candidate
   
3. WHERE id = (
   
4.     SELECT candidateId
   
5.     FROM Vote
   
6.     GROUP BY candidateId
   
7.     ORDER BY COUNT(id) DESC
   
8.     LIMIT 1
   
9. );

复制代码

577. Employee Bonus
Easy
Topics
conpanies icon
Companies
Hint
SQL Schema
Pandas Schema
Table: Employee

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| empId       | int     |
| name        | varchar |
| supervisor  | int     |
| salary      | int     |
+-------------+---------+
empId is the column with unique values for this table.
Each row of this table indicates the name and the ID of an employee in addition to their salary and the id of their manager.


Table: Bonus

+-------------+------+
| Column Name | Type |
+-------------+------+
| empId       | int  |
| bonus       | int  |
+-------------+------+
empId is the column of unique values for this table.
empId is a foreign key (reference column) to empId from the Employee table.
Each row of this table contains the id of an employee and their respective bonus.


Write a solution to report the name and bonus amount of each employee who satisfies either of the following:

The employee has a bonus less than 1000.
The employee did not get any bonus.
Return the result table in any order.

The result format is in the following example.



Example 1:

Input:
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  |
+-------+-------+
Output:
+------+-------+
| name | bonus |
+------+-------+
| Brad | null  |
| John | null  |
| Dan  | 500   |
+------+-------+

1. SELECT
   
2.     e.name,
   
3.     b.bonus
   
4. FROM
   
5.     Employee e
   
6. LEFT JOIN
   
7.     Bonus b ON e.empId = b.empId
   
8. WHERE
   
9.     b.bonus < 1000 OR b.bonus IS NULL;

复制代码

579. Find Cumulative Salary of an Employee
Hard
Topics
conpanies icon
Companies
Hint
SQL Schema
Pandas Schema
Table: Employee

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| month       | int  |
| salary      | int  |
+-------------+------+
(id, month) is the primary key (combination of columns with unique values) for this table.
Each row in the table indicates the salary of an employee in one month during the year 2020.


Write a solution to calculate the cumulative salary summary for every employee in a single unified table.

The cumulative salary summary for an employee can be calculated as follows:

For each month that the employee worked, sum up the salaries in that month and the previous two months. This is their 3-month sum for that month. If an employee did not work for the company in previous months, their effective salary for those months is 0.
Do not include the 3-month sum for the most recent month that the employee worked for in the summary.
Do not include the 3-month sum for any month the employee did not work.
Return the result table ordered by id in ascending order. In case of a tie, order it by month in descending order.

The result format is in the following example.



Example 1:

Input:
Employee table:
+----+-------+--------+
| id | month | salary |
+----+-------+--------+
| 1  | 1     | 20     |
| 2  | 1     | 20     |
| 1  | 2     | 30     |
| 2  | 2     | 30     |
| 3  | 2     | 40     |
| 1  | 3     | 40     |
| 3  | 3     | 60     |
| 1  | 4     | 60     |
| 3  | 4     | 70     |
| 1  | 7     | 90     |
| 1  | 8     | 90     |
+----+-------+--------+
Output:
+----+-------+--------+
| id | month | Salary |
+----+-------+--------+
| 1  | 7     | 90     |
| 1  | 4     | 130    |
| 1  | 3     | 90     |
| 1  | 2     | 50     |
| 1  | 1     | 20     |
| 2  | 1     | 20     |
| 3  | 3     | 100    |
| 3  | 2     | 40     |
+----+-------+--------+
Explanation:
Employee '1' has five salary records excluding their most recent month '8':
- 90 for month '7'.
- 60 for month '4'.
- 40 for month '3'.
- 30 for month '2'.
- 20 for month '1'.
So the cumulative salary summary for this employee is:
+----+-------+--------+
| id | month | salary |
+----+-------+--------+
| 1  | 7     | 90     |  (90 + 0 + 0)
| 1  | 4     | 130    |  (60 + 40 + 30)
| 1  | 3     | 90     |  (40 + 30 + 20)
| 1  | 2     | 50     |  (30 + 20 + 0)
| 1  | 1     | 20     |  (20 + 0 + 0)
+----+-------+--------+
Note that the 3-month sum for month '7' is 90 because they did not work during month '6' or month '5'.

Employee '2' only has one salary record (month '1') excluding their most recent month '2'.
+----+-------+--------+
| id | month | salary |
+----+-------+--------+
| 2  | 1     | 20     |  (20 + 0 + 0)
+----+-------+--------+

Employee '3' has two salary records excluding their most recent month '4':
- 60 for month '3'.
- 40 for month '2'.
So the cumulative salary summary for this employee is:
+----+-------+--------+
| id | month | salary |
+----+-------+--------+
| 3  | 3     | 100    |  (60 + 40 + 0)
| 3  | 2     | 40     |  (40 + 0 + 0)
+----+-------+--------+

1. WITH EmployeeSummary AS (
   
2.     SELECT
   
3.         id,
   
4.         month,
   
5.         -- 使用 RANGE 按月份数值大小圈定当前月和前两个月
   
6.         SUM(salary) OVER(
   
7.             PARTITION BY id
   
8.             ORDER BY month
   
9.             RANGE BETWEEN 2 PRECEDING AND CURRENT ROW
   
10.         ) AS Salary,
    
11.         -- 按月份倒序打序号，找出最近的一个月
    
12.         ROW_NUMBER() OVER(
    
13.             PARTITION BY id
    
14.             ORDER BY month DESC
    
15.         ) AS rn
    
16.     FROM Employee
    
17. )
    
18. SELECT
    
19.     id,
    
20.     month,
    
21.     Salary
    
22. FROM EmployeeSummary
    
23. -- 过滤掉最近的一个月（即序号为 1 的记录）
    
24. WHERE rn > 1
    
25. ORDER BY id ASC, month DESC;

复制代码

补充内容 (2026-05-26 10:14 +08:00):
SELECT
    e1.id,
    e1.month,
    SUM(e2.salary) AS Salary
FROM Employee e1
JOIN Employee e2
    ON e1.id = e2.id
    -- 圈定 3 个月的滑动窗口（当前月和前两个月）
    AND e2.month BETWEEN e1.month - 2 AND e1.month
-- 剔除每个员工最晚的一个月
WHERE (e1.id, e1.month) NOT IN (
    SELECT id, MAX(month)
    FROM Employee
    GROUP BY id
)
GROUP BY e1.id, e1.month
ORDER BY e1.id ASC, e1.month DESC;

578. Get Highest Answer Rate Question
Medium
Topics
conpanies icon
Companies
Hint
SQL Schema
Pandas Schema
Table: SurveyLog

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| action      | ENUM |
| question_id | int  |
| answer_id   | int  |
| q_num       | int  |
| timestamp   | int  |
+-------------+------+
This table may contain duplicate rows.
action is an ENUM (category) of the type: "show", "answer", or "skip".
Each row of this table indicates the user with ID = id has taken an action with the question question_id at time timestamp.
If the action taken by the user is "answer", answer_id will contain the id of that answer, otherwise, it will be null.
q_num is the numeral order of the question in the current session.


The answer rate for a question is the number of times a user answered the question by the number of times a user showed the question.

Write a solution to report the question that has the highest answer rate. If multiple questions have the same maximum answer rate, report the question with the smallest question_id.

The result format is in the following example.



Example 1:

Input:
SurveyLog table:
+----+--------+-------------+-----------+-------+-----------+
| id | action | question_id | answer_id | q_num | timestamp |
+----+--------+-------------+-----------+-------+-----------+
| 5  | show   | 285         | null      | 1     | 123       |
| 5  | answer | 285         | 124124    | 1     | 124       |
| 5  | show   | 369         | null      | 2     | 125       |
| 5  | skip   | 369         | null      | 2     | 126       |
+----+--------+-------------+-----------+-------+-----------+
Output:
+------------+
| survey_log |
+------------+
| 285        |
+------------+
Explanation:
Question 285 was showed 1 time and answered 1 time. The answer rate of question 285 is 1.0
Question 369 was showed 1 time and was not answered. The answer rate of question 369 is 0.0
Question 285 has the highest answer rate.

1. SELECT question_id AS survey_log
   
2. FROM SurveyLog
   
3. GROUP BY question_id
   
4. ORDER BY
   
5.     SUM(CASE WHEN action = 'answer' THEN 1 ELSE 0 END) /
   
6.     SUM(CASE WHEN action = 'show' THEN 1 ELSE 0 END) DESC,
   
7.     question_id ASC
   
8. LIMIT 1;

复制代码

LC 1752. Check if Array Is Sorted and Rotated

旋转数组别忘记首尾两个元素，它们其实也是相邻的！

核心规律：数“断崖”的次数
一个原本有序的数组（比如 [1, 2, 3, 4, 5]），如果把它切开轮转（比如变成 [3, 4, 5, 1, 2]），在整个首尾相连的环形视角下，它依然是整体上升的，最多只会产生一个“断崖”（即前一个数大于后一个数的地方，也就是你代码里的 nums[i] - nums[i-1] < 0）。

没有断崖：原本就是升序（如 [1, 2, 3]），满足条件。

只有 1 个断崖：标准的轮转数组（如 [3, 4, 5, 1, 2]，断崖在 5 -> 1），满足条件。

大于 1 个断崖：绝对不可能通过单次轮转得到（如 [2, 1, 3, 4]，断崖在 2 -> 1，但如果你把它看作环，还要检查尾首。

1. class Solution:
   
2. 
   
3.     def check(self, nums: list[int]) -> bool:
   
4.         count = 0
   
5.         n = len(nums)
   
6. 
   
7.         for i in range(n):
   
8.             # 使用 (i + 1) % n，当 i = n - 1 时，会自动比较 nums[n-1] 和 nums[0]
   
9.             if nums[i] > nums[(i + 1) % n]:
   
10.                 count += 1
    
11. 
    
12.             # 剪枝优化：一旦断崖数量超过 1，直接可以断定不符合条件
    
13.             if count > 1:
    
14.                 return False
    
15. 
    
16.         return True

复制代码

LC. 2540. Minimum Common Value

这道题目的最大条件就是

sorted in non-decreasing order == > 这个应该能想到二分法或者指针法。

我只想到了二分，没想到指针。

还是需要提高姿势水平。

1. class Solution:
   
2.     def getCommon(self, nums1: list[int], nums2: list[int]) -> int:
   
3.         # 细节优化：我们永远在更长的那个数组里做二分查找
   
4.         # 如果 nums1 比 nums2 长，我们就交换它们，确保 nums2 是长数组
   
5.         if len(nums1) > len(nums2):
   
6.             nums1, nums2 = nums2, nums1
   
7.             
   
8.         # 遍历短数组 nums1
   
9.         for target in nums1:
   
10.             # 在长数组 nums2 中进行二分查找
    
11.             left, right = 0, len(nums2) - 1
    
12.             while left <= right:
    
13.                 mid = (left + right) // 2
    
14.                 if nums2[mid] == target:
    
15.                     return target  # 找到了直接返回
    
16.                 elif nums2[mid] < target:
    
17.                     left = mid + 1
    
18.                 else:
    
19.                     right = mid - 1
    
20.                     
    
21.         return -1

复制代码

双指针！

核心思路：双指针法（Two Pointers）
因为两个数组都是从小到大排好序的，我们可以想象两个指针分别指向 nums1 和 nums2 的开头，就像两个人在赛跑：

初始化两个指针 i = 0, j = 0。

比较 nums1[i] 和 nums2[j]：

如果 nums1[i] == nums2[j]：恭喜，找到了！因为我们是从前往后（从小到大）遍历的，这第一个碰到的相等元素绝对是最小的公共元素，直接返回它。

如果 nums1[i] < nums2[j]：说明 nums1[i] 太小了，它不可能在 nums2 后面找到了（因为 nums2 后面的数更大）。所以我们需要让 i 往后走一步（i += 1），去碰碰运气。

如果 nums1[i] > nums2[j]：同理，说明 nums2[j] 太小了，让 j 往后走一步（j += 1）。

如果其中一个指针越界了还没找到，说明没有公共元素，返回 -1。

1. class Solution:
   
2.     def getCommon(self, nums1: list[int], nums2: list[int]) -> int:
   
3.         i, j = 0, 0
   
4.         len1, len2 = len(nums1), len(nums2)
   
5.         
   
6.         # 只要有一个数组遍历完了，就说明不可能再有公共元素了
   
7.         while i < len1 and j < len2:
   
8.             if nums1[i] == nums2[j]:
   
9.                 return nums1[i]  # 找到的第一个一定是最小的
   
10.             elif nums1[i] < nums2[j]:
    
11.                 i += 1
    
12.             else:
    
13.                 j += 1
    
14.                
    
15.         return -1

复制代码