刷题记录帖子

LC 3606. Coupon Code Validator

虽然是简单题，但是其实还是考察了具体的排序和业务代码还是比较好的题目。

可以作为简单 medium ，这道题目并不完全简单。考察严谨性。

1. class Solution:
   
2.     def validateCoupons(self, code: List[str], businessLine: List[str], isActive: List[bool]) -> List[str]:
   
3.         ans = []
   
4.         
   
5.         for c, bl, is_active in zip(code, businessLine, isActive):
   
6.             if len(c) > 0 and ( set([ch for ch in c]) == set('_') or c.replace('_', "").lower().isalnum()) and bl in ("electronics", "grocery", "pharmacy", "restaurant") and is_active:
   
7.                 ans.append((bl, c))
   
8.         
   
9.         ans.sort(key = lambda x: x[1])
   
10.         ans.sort(key = lambda x: x[0])
    
11.         return [x[1] for x in ans]

复制代码

更加优化的代码，

all 的运用

1. 
   
2. 
   
3. from typing import List
   
4. 
   
5. class Solution:
   
6.     def validateCoupons(self, code: List[str], businessLine: List[str], isActive: List[bool]) -> List[str]:
   
7.         # 1. 定义 businessLine 的优先级顺序
   
8.         category_order = {
   
9.             "electronics": 0,
   
10.             "grocery": 1,
    
11.             "pharmacy": 2,
    
12.             "restaurant": 3
    
13.         }
    
14.         
    
15.         valid_coupons = []
    
16.         
    
17.         # 2. 遍历并过滤
    
18.         for c, bl, active in zip(code, businessLine, isActive):
    
19.             # 校验 isActive
    
20.             if not active:
    
21.                 continue
    
22.             
    
23.             # 校验 businessLine 是否在白名单中
    
24.             if bl not in category_order:
    
25.                 continue
    
26.                
    
27.             # 校验 code: 非空 且 (字母/数字/下划线)
    
28.             is_valid_code = len(c) > 0 and all(ch.isalnum() or ch == '_' for ch in c)
    
29.             if not is_valid_code:
    
30.                 continue
    
31.             
    
32.             # 存储：(优先级权重, code)
    
33.             valid_coupons.append((category_order[bl], c))
    
34.             
    
35.         # 3. 多级排序：先按权重排，权重相同按 code 字典序排
    
36.         # Python 的元组排序天然支持多级比较
    
37.         valid_coupons.sort()
    
38.         
    
39.         # 4. 提取结果
    
40.         return [item[1] for item in valid_coupons]
    
41. 
    

复制代码

LC. 2452. Words Within Two Edits of Dictionary


我要是出进阶题目就用 TireTree，但是对于当前问题，多次遍历还是可以的。

1. class Solution:
   
2.     def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
   
3.         ans = []
   
4. 
   
5.         for q in queries:
   
6.                            
   
7.             FOUND = False
   
8.             for d in dictionary:
   
9.                 diff = 0
   
10.                 for i in range(len(q)):
    
11.                     if q[i] != d[i]: diff += 1
    
12.                     if diff > 2:
    
13.                         break
    
14.                     if i == len(q) -1 and diff <= 2:
    
15.                         FOUND = True
    
16.                         break
    
17.                 if FOUND:
    
18.                     ans.append(q)
    
19.                     break
    
20.         return ans

复制代码

Trie 的写法

1. class Solution:
   
2.     def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
   
3.         # 1. 构建字典树 (Trie)
   
4.         # 使用 {} 嵌套来表示树结构，省去定义类的开销
   
5.         trie = {}
   
6.         for word in dictionary:
   
7.             node = trie
   
8.             for char in word:
   
9.                 if char not in node:
   
10.                     node[char] = {}
    
11.                 node = node[char]
    
12.             node['#'] = True  # 单词结束标记
    
13. 
    
14.         # 2. 定义带容错的 DFS 搜索
    
15.         # memo = {} # 如果单词长度很长且重复，可以加记忆化，本题不需要
    
16.         
    
17.         def can_match(node, word, index, edits):
    
18.             # 剪枝：编辑次数超过 2 直接失败
    
19.             if edits > 2:
    
20.                 return False
    
21.             
    
22.             # 递归出口：单词匹配完成
    
23.             if index == len(word):
    
24.                 return True
    
25.             
    
26.             char = word[index]
    
27.             
    
28.             # 策略：优先走不需要修改的分支，更容易提前退出
    
29.             if char in node:
    
30.                 if can_match(node[char], word, index + 1, edits):
    
31.                     return True
    
32.             
    
33.             # 如果 edits 还没到 2，尝试修改当前字母（走其他分支）
    
34.             if edits < 2:
    
35.                 for next_char in node:
    
36.                     if next_char == char or next_char == '#':
    
37.                         continue
    
38.                     if can_match(node[next_char], word, index + 1, edits + 1):
    
39.                         return True
    
40.             
    
41.             return False
    
42. 
    
43.         # 3. 过滤 queries
    
44.         ans = []
    
45.         for q in queries:
    
46.             if can_match(trie, q, 0, 0):
    
47.                 ans.append(q)
    
48.         return ans

复制代码

LC. 168. Excel Sheet Column Title

这道题目看起来 easy 但是写起来到处是坑。。。。

虽然是简单题，但是还是值得学习。

1. class Solution:
   
2.     def convertToTitle(self, columnNumber: int) -> str:
   
3.         ans = []
   
4.         
   
5.         while columnNumber > 0:
   
6.             # 核心技巧：先减 1，对齐 0-25 的区间
   
7.             columnNumber -= 1
   
8.             
   
9.             # 现在计算余数，0 就是 A，25 就是 Z
   
10.             remainder = columnNumber % 26
    
11.             ans.append(chr(ord('A') + remainder))
    
12.             
    
13.             # 更新 columnNumber 进行下一轮
    
14.             columnNumber //= 26
    
15.             
    
16.         # 因为是从低位往高位算（先算个位），所以需要反转
    
17.         return "".join(ans[::-1])

复制代码

171. Excel Sheet Column Number

上面题目的反例，但是从字母转成数字更加简单原因在于这个是可以按照十进制等类比的做

多项式求值

1. class Solution:

复制代码

170. Two Sum III - Data structure design

Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.

Implement the TwoSum class:

TwoSum() Initializes the TwoSum object, with an empty array initially.
void add(int number) Adds number to the data structure.
boolean find(int value) Returns true if there exists any pair of numbers whose sum is equal to value, otherwise, it returns false.


Example 1:

Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]

Explanation
TwoSum twoSum = new TwoSum();
twoSum.add(1);   // [] --> [1]
twoSum.add(3);   // [1] --> [1,3]
twoSum.add(5);   // [1,3] --> [1,3,5]
twoSum.find(4);  // 1 + 3 = 4, return true
twoSum.find(7);  // No two integers sum up to 7, return false


Constraints:

-105 <= number <= 105
-231 <= value <= 231 - 1
At most 104 calls will be made to add and find.

虽然是简单题，但是还是很值得讨论的。

我的虽然想到了排序但是再find的时候，固定思维带入了 2 sum 来做。其实可以用 two pointer 来查找。

1. class TwoSum:
   
2. 
   
3.     def __init__(self):
   
4.         self.arr = []
   
5. 
   
6.     def add(self, number: int) -> None:
   
7.         if not self.arr:
   
8.             self.arr.append(number)
   
9.         else:
   
10.             ind = bisect.bisect_left(self.arr, number)
    
11.             self.arr.insert(ind, number)
    
12. 
    
13.     def find(self, value: int) -> bool:
    
14. 
    
15.         res = set()
    
16. 
    
17.         for n in self.arr:
    
18.             if value - n in res:
    
19.                 return True
    
20.             else:
    
21.                 res.add(n)
    
22.         
    
23.         return False
    
24. 
    
25.         
    
26. 
    
27. 
    
28. # Your TwoSum object will be instantiated and called as such:
    
29. # obj = TwoSum()
    
30. # obj.add(number)
    
31. # param_2 = obj.find(value)

复制代码

双指针

1. class TwoSum:
   
2. 
   
3.     def __init__(self):
   
4.         self.arr = []
   
5. 
   
6.     def add(self, number: int) -> None:
   
7.         if not self.arr:
   
8.             self.arr.append(number)
   
9.         else:
   
10.             ind = bisect.bisect_left(self.arr, number)
    
11.             self.arr.insert(ind, number)
    
12. 
    
13.     def find(self, value: int) -> bool:
    
14.         # 优化：利用有序性使用双指针，空间复杂度 O(1)
    
15.         left, right = 0, len(self.arr) - 1
    
16.         while left < right:
    
17.             current_sum = self.arr[left] + self.arr[right]
    
18.             if current_sum == value:
    
19.                 return True
    
20.             elif current_sum < value:
    
21.                 left += 1
    
22.             else:
    
23.                 right -= 1
    
24.         return False
    
25.         
    
26. 
    
27. 
    
28. # Your TwoSum object will be instantiated and called as such:
    
29. # obj = TwoSum()
    
30. # obj.add(number)
    
31. # param_2 = obj.find(value)

复制代码

其实最优的解法是用 dict，这样写入可以极快，查找的时候可以直接看具体数字出现的次数如果target == num，否则就查找是不是存在 target。

1. from collections import defaultdict
   
2. 
   
3. class TwoSum:
   
4. 
   
5.     def __init__(self):
   
6.         # 记录每个数字出现的次数
   
7.         self.num_counts = defaultdict(int)
   
8. 
   
9.     def add(self, number: int) -> None:
   
10.         # 核心：写入的时间复杂度降为 O(1)
    
11.         self.num_counts[number] += 1
    
12. 
    
13.     def find(self, value: int) -> bool:
    
14.         # 遍历哈希表中的 key
    
15.         for num in self.num_counts:
    
16.             target = value - num
    
17.             
    
18.             # 坑点：如果 target 和 num 是同一个数，必须保证它出现至少 2 次
    
19.             if target == num:
    
20.                 if self.num_counts[num] > 1:
    
21.                     return True
    
22.             # 如果不是同一个数，只要 target 在字典里即可
    
23.             elif target in self.num_counts:
    
24.                 return True
    
25.                
    
26.         return False
    
27. 
    
28. # Your TwoSum object will be instantiated and called as such:
    
29. # obj = TwoSum()
    
30. # obj.add(number)
    
31. # param_2 = obj.find(value)

复制代码

可以清晰看到时间复杂度的变化。

LC. 2833. Furthest Point From Origin

我的解法

1. class Solution:
   
2.     def furthestDistanceFromOrigin(self, moves: str) -> int:
   
3.         freq = Counter(moves)
   
4. 
   
5.         return max(abs(freq['L']+freq['_']-freq['R']), abs(freq['R']+freq['_']-freq['L']))

复制代码

虽然是简单题，但是还是可以提高。

没想到可以继续优化，同时简单的 3 类 case 确实是直接手动统计更加简单。

优化解法

1. class Solution:
   
2.     def furthestDistanceFromOrigin(self, moves: str) -> int:
   
3.         # 一次遍历统计，比使用 Counter 更快一点，也更符合底层逻辑
   
4.         net_moves = 0
   
5.         underscore_count = 0
   
6.         
   
7.         for m in moves:
   
8.             if m == 'L':
   
9.                 net_moves -= 1
   
10.             elif m == 'R':
    
11.                 net_moves += 1
    
12.             else:
    
13.                 underscore_count += 1
    
14.         
    
15.         # 核心逻辑：净位移的绝对值 + 所有的下划线
    
16.         return abs(net_moves) + underscore_count

复制代码

LC  262. Trips and Users

Table: Trips

+-------------+----------+
| Column Name | Type     |
+-------------+----------+
| id          | int      |
| client_id   | int      |
| driver_id   | int      |
| city_id     | int      |
| status      | enum     |
| request_at  | varchar  |     
+-------------+----------+
id is the primary key (column with unique values) for this table.
The table holds all taxi trips. Each trip has a unique id, while client_id and driver_id are foreign keys to the users_id at the Users table.
Status is an ENUM (category) type of ('completed', 'cancelled_by_driver', 'cancelled_by_client').

Table: Users

+-------------+----------+
| Column Name | Type     |
+-------------+----------+
| users_id    | int      |
| banned      | enum     |
| role        | enum     |
+-------------+----------+
users_id is the primary key (column with unique values) for this table.
The table holds all users. Each user has a unique users_id, and role is an ENUM type of ('client', 'driver', 'partner').
banned is an ENUM (category) type of ('Yes', 'No').

The cancellation rate is computed by dividing the number of canceled (by client or driver) requests with unbanned users by the total number of requests with unbanned users on that day.

Write a solution to find the cancellation rate of requests with unbanned users (both client and driver must not be banned) each day between "2013-10-01" and "2013-10-03" with at least one trip. Round Cancellation Rate to two decimal points.

Return the result table in any order.

The result format is in the following example.



Example 1:

Input:
Trips table:
+----+-----------+-----------+---------+---------------------+------------+
| id | client_id | driver_id | city_id | status              | request_at |
+----+-----------+-----------+---------+---------------------+------------+
| 1  | 1         | 10        | 1       | completed           | 2013-10-01 |
| 2  | 2         | 11        | 1       | cancelled_by_driver | 2013-10-01 |
| 3  | 3         | 12        | 6       | completed           | 2013-10-01 |
| 4  | 4         | 13        | 6       | cancelled_by_client | 2013-10-01 |
| 5  | 1         | 10        | 1       | completed           | 2013-10-02 |
| 6  | 2         | 11        | 6       | completed           | 2013-10-02 |
| 7  | 3         | 12        | 6       | completed           | 2013-10-02 |
| 8  | 2         | 12        | 12      | completed           | 2013-10-03 |
| 9  | 3         | 10        | 12      | completed           | 2013-10-03 |
| 10 | 4         | 13        | 12      | cancelled_by_driver | 2013-10-03 |
+----+-----------+-----------+---------+---------------------+------------+
Users table:
+----------+--------+--------+
| users_id | banned | role   |
+----------+--------+--------+
| 1        | No     | client |
| 2        | Yes    | client |
| 3        | No     | client |
| 4        | No     | client |
| 10       | No     | driver |
| 11       | No     | driver |
| 12       | No     | driver |
| 13       | No     | driver |
+----------+--------+--------+
Output:
+------------+-------------------+
| Day        | Cancellation Rate |
+------------+-------------------+
| 2013-10-01 | 0.33              |
| 2013-10-02 | 0.00              |
| 2013-10-03 | 0.50              |
+------------+-------------------+
Explanation:
On 2013-10-01:
  - There were 4 requests in total, 2 of which were canceled.
  - However, the request with Id=2 was made by a banned client (User_Id=2), so it is ignored in the calculation.
  - Hence there are 3 unbanned requests in total, 1 of which was canceled.
  - The Cancellation Rate is (1 / 3) = 0.33
On 2013-10-02:
  - There were 3 requests in total, 0 of which were canceled.
  - The request with Id=6 was made by a banned client, so it is ignored.
  - Hence there are 2 unbanned requests in total, 0 of which were canceled.
  - The Cancellation Rate is (0 / 2) = 0.00
On 2013-10-03:
  - There were 3 requests in total, 1 of which was canceled.
  - The request with Id=8 was made by a banned client, so it is ignored.
  - Hence there are 2 unbanned request in total, 1 of which were canceled.
  - The Cancellation Rate is (1 / 2) = 0.50

JOIN 的技巧：
这里使用了两次 JOIN。如果任意一方（乘客或司机）被封禁，这条行程记录就会因为不满足连接条件而在结果集中被剔除。这是最直接的过滤方式。

1. SELECT
   
2.     t.request_at AS Day,
   
3.     ROUND(
   
4.         SUM(CASE WHEN t.status != 'completed' THEN 1 ELSE 0 END) / COUNT(*),
   
5.         2
   
6.     ) AS "Cancellation Rate"
   
7. FROM Trips t
   
8. -- 连接 Client，过滤掉被封禁的乘客
   
9. JOIN Users c ON t.client_id = c.users_id AND c.banned = 'No'
   
10. -- 连接 Driver，过滤掉被封禁的司机
    
11. JOIN Users d ON t.driver_id = d.users_id AND d.banned = 'No'
    
12. WHERE t.request_at BETWEEN '2013-10-01' AND '2013-10-03'
    
13. GROUP BY t.request_at;

复制代码

LC 511. Game Play Analysis I

Table: Activity

+--------------+---------+
| Column Name  | Type    |
+--------------+---------+
| player_id    | int     |
| device_id    | int     |
| event_date   | date    |
| games_played | int     |
+--------------+---------+
(player_id, event_date) is the primary key (combination of columns with unique values) of this table.
This table shows the activity of players of some games.
Each row is a record of a player who logged in and played a number of games (possibly 0) before logging out on someday using some device.


Write a solution to find the first login date for each player.

Return the result table in any order.

The result format is in the following example.



Example 1:

Input:
Activity table:
+-----------+-----------+------------+--------------+
| player_id | device_id | event_date | games_played |
+-----------+-----------+------------+--------------+
| 1         | 2         | 2016-03-01 | 5            |
| 1         | 2         | 2016-05-02 | 6            |
| 2         | 3         | 2017-06-25 | 1            |
| 3         | 1         | 2016-03-02 | 0            |
| 3         | 4         | 2018-07-03 | 5            |
+-----------+-----------+------------+--------------+
Output:
+-----------+-------------+
| player_id | first_login |
+-----------+-------------+
| 1         | 2016-03-01  |
| 2         | 2017-06-25  |
| 3         | 2016-03-02  |
+-----------+-------------+

1. SELECT
   
2.     player_id,
   
3.     MIN(event_date) AS first_login
   
4. FROM
   
5.     Activity
   
6. GROUP BY
   
7.     player_id;

复制代码

LC. 512. Game Play Analysis II


Table: Activity

+--------------+---------+
| Column Name  | Type    |
+--------------+---------+
| player_id    | int     |
| device_id    | int     |
| event_date   | date    |
| games_played | int     |
+--------------+---------+
(player_id, event_date) is the primary key (combination of columns with unique values) of this table.
This table shows the activity of players of some games.
Each row is a record of a player who logged in and played a number of games (possibly 0) before logging out on someday using some device.


Write a solution to report the device that is first logged in for each player.

Return the result table in any order.

The result format is in the following example.



Example 1:

Input:
Activity table:
+-----------+-----------+------------+--------------+
| player_id | device_id | event_date | games_played |
+-----------+-----------+------------+--------------+
| 1         | 2         | 2016-03-01 | 5            |
| 1         | 2         | 2016-05-02 | 6            |
| 2         | 3         | 2017-06-25 | 1            |
| 3         | 1         | 2016-03-02 | 0            |
| 3         | 4         | 2018-07-03 | 5            |
+-----------+-----------+------------+--------------+
Output:
+-----------+-----------+
| player_id | device_id |
+-----------+-----------+
| 1         | 2         |
| 2         | 3         |
| 3         | 1         |
+-----------+-----------+

1. SELECT
   
2.     player_id,
   
3.     device_id
   
4. FROM
   
5.     Activity
   
6. WHERE
   
7.     (player_id, event_date) IN (
   
8.         SELECT
   
9.             player_id,
   
10.             MIN(event_date)
    
11.         FROM
    
12.             Activity
    
13.         GROUP BY
    
14.             player_id
    
15.     );

复制代码

1. SELECT
   
2.     player_id,
   
3.     device_id
   
4. FROM (
   
5.     SELECT
   
6.         player_id,
   
7.         device_id,
   
8.         RANK() OVER (PARTITION BY player_id ORDER BY event_date ASC) as rk
   
9.     FROM
   
10.         Activity
    
11. ) t
    
12. WHERE
    
13.     rk = 1;

复制代码

LC 534. Game Play Analysis III


Table: Activity

+--------------+---------+
| Column Name  | Type    |
+--------------+---------+
| player_id    | int     |
| device_id    | int     |
| event_date   | date    |
| games_played | int     |
+--------------+---------+
(player_id, event_date) is the primary key (column with unique values) of this table.
This table shows the activity of players of some games.
Each row is a record of a player who logged in and played a number of games (possibly 0) before logging out on someday using some device.


Write a solution to report for each player and date, how many games played so far by the player. That is, the total number of games played by the player until that date. Check the example for clarity.

Return the result table in any order.

The result format is in the following example.



Example 1:

Input:
Activity table:
+-----------+-----------+------------+--------------+
| player_id | device_id | event_date | games_played |
+-----------+-----------+------------+--------------+
| 1         | 2         | 2016-03-01 | 5            |
| 1         | 2         | 2016-05-02 | 6            |
| 1         | 3         | 2017-06-25 | 1            |
| 3         | 1         | 2016-03-02 | 0            |
| 3         | 4         | 2018-07-03 | 5            |
+-----------+-----------+------------+--------------+
Output:
+-----------+------------+---------------------+
| player_id | event_date | games_played_so_far |
+-----------+------------+---------------------+
| 1         | 2016-03-01 | 5                   |
| 1         | 2016-05-02 | 11                  |
| 1         | 2017-06-25 | 12                  |
| 3         | 2016-03-02 | 0                   |
| 3         | 2018-07-03 | 5                   |
+-----------+------------+---------------------+
Explanation:
For the player with id 1, 5 + 6 = 11 games played by 2016-05-02, and 5 + 6 + 1 = 12 games played by 2017-06-25.
For the player with id 3, 0 + 5 = 5 games played by 2018-07-03.
Note that for each player we only care about the days when the player logged in.

1. SELECT
   
2.     player_id,
   
3.     event_date,
   
4.     SUM(games_played) OVER (
   
5.         PARTITION BY player_id
   
6.         ORDER BY event_date
   
7.     ) AS games_played_so_far
   
8. FROM
   
9.     Activity;

复制代码

1. SELECT
   
2.     a1.player_id,
   
3.     a1.event_date,
   
4.     SUM(a2.games_played) AS games_played_so_far
   
5. FROM
   
6.     Activity a1
   
7. JOIN
   
8.     Activity a2 ON a1.player_id = a2.player_id
   
9.     AND a1.event_date >= a2.event_date
   
10. GROUP BY
    
11.     a1.player_id, a1.event_date;

复制代码