刷题记录帖子

LC. 3793. Find Users with High Token Usage

Table: prompts

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| user_id     | int     |
| prompt      | varchar |
| tokens      | int     |
+-------------+---------+
(user_id, prompt) is the primary key (unique value) for this table.
Each row represents a prompt submitted by a user to an AI system along with the number of tokens consumed.
Write a solution to analyze AI prompt usage patterns based on the following requirements:

For each user, calculate the total number of prompts they have submitted.
For each user, calculate the average tokens used per prompt (Rounded to 2 decimal places).
Only include users who have submitted at least 3 prompts.
Only include users who have submitted at least one prompt with tokens greater than their own average token usage.
Return the result table ordered by average tokens in descending order, and then by user_id in ascending order.

The result format is in the following example.



Example:

Input:

prompts table:

+---------+--------------------------+--------+
| user_id | prompt                   | tokens |
+---------+--------------------------+--------+
| 1       | Write a blog outline     | 120    |
| 1       | Generate SQL query       | 80     |
| 1       | Summarize an article     | 200    |
| 2       | Create resume bullet     | 60     |
| 2       | Improve LinkedIn bio     | 70     |
| 3       | Explain neural networks  | 300    |
| 3       | Generate interview Q&A   | 250    |
| 3       | Write cover letter       | 180    |
| 3       | Optimize Python code     | 220    |
+---------+--------------------------+--------+
Output:

+---------+---------------+------------+
| user_id | prompt_count  | avg_tokens |
+---------+---------------+------------+
| 3       | 4             | 237.5      |
| 1       | 3             | 133.33     |
+---------+---------------+------------+
Explanation:

User 1:
Total prompts = 3
Average tokens = (120 + 80 + 200) / 3 = 133.33
Has a prompt with 200 tokens, which is greater than the average
Included in the result
User 2:
Total prompts = 2 (less than the required minimum)
Excluded from the result
User 3:
Total prompts = 4
Average tokens = (300 + 250 + 180 + 220) / 4 = 237.5
Has prompts with 300 and 250 tokens, both greater than the average
Included in the result
The Results table is ordered by avg_tokens in descending order, then by user_id in ascending order

1. # Write your MySQL query statement below
   
2. WITH RawStats AS (
   
3.     -- 1. 核心步骤：利用窗口函数在每一行旁边标记出该用户的“全局”指标
   
4.     SELECT
   
5.         user_id,
   
6.         tokens,
   
7.         COUNT(*) OVER(PARTITION BY user_id) as total_prompts,
   
8.         AVG(tokens * 1.0) OVER(PARTITION BY user_id) as avg_tokens_raw
   
9.     FROM prompts
   
10. ),
    
11. FilteredUsers AS (
    
12.     -- 2. 过滤：满足提交次数 >= 3 且 存在单次 tokens > 个人平均值的用户
    
13.     SELECT
    
14.         user_id,
    
15.         MAX(total_prompts) as prompt_count, -- 窗口函数出来的结果每行都一样，取 MAX 即可
    
16.         ROUND(MAX(avg_tokens_raw), 2) as avg_tokens
    
17.     FROM RawStats
    
18.     WHERE total_prompts >= 3
    
19.       AND tokens > avg_tokens_raw  -- 核心条件：单次请求超过自己的平均水平
    
20.     GROUP BY user_id
    
21. )
    
22. -- 3. 排序输出
    
23. SELECT
    
24.     user_id,
    
25.     prompt_count,
    
26.     avg_tokens
    
27. FROM FilteredUsers
    
28. ORDER BY
    
29.     avg_tokens DESC,
    
30.     user_id ASC;

复制代码

LC. 3769. Sort Integers by Binary Reflection

1. class Solution:
   
2.     def sortByReflection(self, nums: List[int]) -> List[int]:
   
3.         reflection = [(int(bin(n)[2:][::-1], 2), n) for n in nums]
   
4.         reflection.sort()
   
5. 
   
6.         return [x[1] for x in reflection]
   
7.         

复制代码

更 Python 的代码

1. class Solution:
   
2.     def sortByReflection(self, nums: List[int]) -> List[int]:
   
3.         def get_reflection(n):
   
4.             # 将 n 转为二进制字符串，反转，再按 2 进制转回整数
   
5.             reflected_val = int(bin(n)[2:][::-1], 2)
   
6.             # 返回一个元组用于多级排序：(主要关键字, 次要关键字)
   
7.             return (reflected_val, n)
   
8. 
   
9.         # sort 是稳定的，但直接在 key 里返回元组是最标准的做法
   
10.         nums.sort(key=get_reflection)
    
11.         return nums

复制代码

补充内容 (2026-03-16 11:58 +08:00):

LC. 3754. Concatenate Non-Zero Digits and Multiply by Sum I

1. class Solution:
   
2.     def sumAndMultiply(self, n: int) -> int:
   
3.         s = [ch for ch in str(n) if ch != '0']
   
4.         if not s: s = ['0']
   
5.         x = int("".join(s))
   
6.         sum_x = sum([int(x) for x in s])
   
7. 
   
8.         return x * sum_x
   
9.         

复制代码

不用字符串解法，使用数学，循环提取。

1. class Solution:
   
2.     def sumAndMultiply(self, n: int) -> int:
   
3.         if n == 0: return 0
   
4.         
   
5.         nums = []
   
6.         temp = n
   
7.         # 从低位到高位提取
   
8.         while temp > 0:
   
9.             digit = temp % 10
   
10.             if digit != 0:
    
11.                 nums.append(digit)
    
12.             temp //= 10
    
13.         
    
14.         if not nums: return 0
    
15.         
    
16.         # 因为是从低位提取的，拼接 x 时需要反转
    
17.         x = 0
    
18.         total_sum = 0
    
19.         for d in reversed(nums):
    
20.             x = x * 10 + d
    
21.             total_sum += d
    
22.             
    
23.         return x * total_sum

复制代码

LC. 3750. Minimum Number of Flips to Reverse Binary String

1. class Solution:
   
2.     def minimumFlips(self, n: int) -> int:
   
3.         s = bin(n)[2:]
   
4.         rev_s = s[::-1]
   
5.         ans = 0
   
6. 
   
7.         for i in range(len(s)):
   
8.             if s[i] != rev_s[i]:
   
9.                 ans += 1
   
10.         return ans
    
11.         

复制代码

可以快速验证，

1. class Solution:
   
2.     def minimumFlips(self, n: int) -> int:
   
3.         s = bin(n)[2:]
   
4.         n_len = len(s)
   
5.         ans = 0
   
6.         # 只需要遍历一遍字符串即可
   
7.         for i in range(n_len):
   
8.             # 对比当前位和它镜像位置的字符
   
9.             if s[i] != s[n_len - 1 - i]:
   
10.                 ans += 1
    
11.         return ans

复制代码

LC  3745. Maximize Expression of Three Elements

脑子困住了，第一遍想到的解法居然是 N^3 循环暴力求解。。。

其实做之前就可以想下套路，是不是可以贪心，是不是可以二分，是不是可以 DFS / BFS。

优化思路 (贪心解法)既然 $a, b, c$ 之间没有顺序限制，我们其实只需要关注整个数组中最大的那些数和最小的那颗数。我们需要两个最大的数作为 $a$ 和 $b$。我们需要一个最小的数作为 $c$。但是有一个小细节： 如果数组中最大的数恰好也是最小的数（即数组元素都一样），或者最小的数被选作 $a$ 或 $b$ 了怎么办？其实最稳妥的做法是：直接对数组排序。

1. class Solution:
   
2.     def maximizeExpressionOfThree(self, nums: List[int]) -> int:
   
3.         # ans = float('-inf')
   
4.         # n = len(nums)
   
5.         # for i in range(n):
   
6.         #     for j in range(i+1, n):
   
7.         #         for k in range(j+1, n):
   
8.         #             sum3 = nums[i] + nums[j] + nums[k]
   
9.         #             for c in [i, j, k]:
   
10.         #                 ans = max(ans, sum3 - 2 * nums[c])
    
11.         # return ans
    
12.         nums.sort()
    
13. 
    
14.         return nums[-1] + nums[-2] - nums[0]

复制代码

LC 3740. Minimum Distance Between Three Equal Elements I

完全可以边遍历，边查找最小值。

拓展一下，如果是 四个数字，循环 abs 差呢，还是首尾两个位置作差。

1. class Solution:
   
2.     def minimumDistance(self, nums: List[int]) -> int:
   
3.         val_index = defaultdict(list)
   
4.         ans = float('inf')
   
5.         
   
6.         for ind, val in enumerate(nums):
   
7.             val_index[val].append(ind)
   
8.             
   
9.             # 必须是 indices[-1] - indices[-3]
   
10.             # 这样才能保证我们检查的是“最近”的三个相同数字
    
11.             if len(val_index[val]) >= 3:
    
12.                 dist = 2 * (val_index[val][-1] - val_index[val][-3])
    
13.                 if dist < ans:
    
14.                     ans = dist
    
15.                     
    
16.         return ans if ans != float('inf') else -1

复制代码

或者简明写法，

1. class Solution:
   
2.     def minimumDistance(self, nums: List[int]) -> int:
   
3.         val_index = defaultdict(list)
   
4.         checked_vals = set()
   
5.         
   
6.         for ind,val in enumerate(nums):
   
7.             val_index[val].append(ind)
   
8.             if len(val_index[val]) == 3 and val not in checked_vals:
   
9.                 checked_vals.add(val)
   
10.         
    
11.         if not checked_vals: return -1
    
12.         ans = float('inf')
    
13.         for val in checked_vals:
    
14.             ind_list = val_index[val]
    
15.             for i in range(len(ind_list) - 2):
    
16.                 ans = min(ans, abs(ind_list[i+2] - ind_list[i]) + abs(ind_list[i+2] - ind_list[i+1]) + abs(ind_list[i+1] - ind_list[i]))
    
17.         return ans

复制代码

LC 3070. Count Submatrices with Top-Left Element and Sum Less Than k

S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + grid[i][j]

1. class Solution:
   
2.     def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
   
3.         # s(i,j) means top-left (0,0) to (i,j) sum
   
4.         # s(i,j) = s(i-1, j) + s(i, j-1) - s(i-1, j-1) + grid(i,j)
   
5.         n_row = len(grid)
   
6.         n_col = len(grid[0])
   
7.         sum_grid = []
   
8.         for i in range(n_row): sum_grid.append([0] * n_col)
   
9. 
   
10.         # calculate sum of first row
    
11.         sum_grid[0][0] = grid[0][0]
    
12. 
    
13.         for i in range(1, n_col):
    
14.             sum_grid[0][i] = sum_grid[0][i-1] + grid[0][i]
    
15.         # calculate sum of first col
    
16.         for i in range(1, n_row):
    
17.             sum_grid[i][0] = sum_grid[i-1][0] + grid[i][0]
    
18.         
    
19.         # loop all other cells that are not 1st row or col
    
20.         for i in range(1, n_row):
    
21.             for j in range(1, n_col):
    
22.                 sum_grid[i][j] = sum_grid[i-1][j] + sum_grid[i][j-1] - sum_grid[i-1][j-1] + grid[i][j]
    
23.         
    
24.         count = 0
    
25.         for i in range(n_row):
    
26.             for j in range(n_col):
    
27.                 if sum_grid[i][j] <= k:
    
28.                     count += 1
    
29.         return count

复制代码

你分开了第一行、第一列和中间部分的计算。在面试中，我们可以通过增加一行一列的偏移（Padding）或者在循环内做边界判断来简化代码，减少出错概率。优化 B：空间复杂度优化其实我们不需要一个完整的 sum_grid 矩阵后再去遍历一遍计数。我们可以在计算当前 sum_grid[i][j] 的同时就进行判断。甚至，如果你不介意修改原数组，可以直接在 grid 上原地操作，空间复杂度降为 $O(1)$（不计输入输出）。优化 C：剪枝（Pruning）题目说了 grid[i][j] >= 0。这意味着如果 sum_grid[i][0] 已经大于 $k$ 了，那么这一行后面的所有 sum_grid[i][j] 肯定也都大于 $k$，可以直接跳过当前行的后续计算。

1. from typing import List
   
2. 
   
3. class Solution:
   
4.     def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
   
5.         m, n = len(grid), len(grid[0])
   
6.         count = 0
   
7.         
   
8.         # 直接在 grid 上原地计算前缀和，省去额外的 sum_grid 空间
   
9.         for i in range(m):
   
10.             for j in range(n):
    
11.                 # 计算当前位置的前缀和
    
12.                 if i > 0:
    
13.                     grid[i][j] += grid[i-1][j]
    
14.                 if j > 0:
    
15.                     grid[i][j] += grid[i][j-1]
    
16.                 if i > 0 and j > 0:
    
17.                     grid[i][j] -= grid[i-1][j-1]
    
18.                
    
19.                 # 核心判断
    
20.                 if grid[i][j] <= k:
    
21.                     count += 1
    
22.                 else:
    
23.                     # 剪枝优化：
    
24.                     # 因为 grid 元素 >= 0，所以同一行往右的和只会更大。
    
25.                     # 注意：由于二维的特性，即使当前位置 > k，下一行的同列位置仍可能通过前面的小值拉回来，
    
26.                     # 所以只能 break 内层循环（当前行），不能直接结束整个函数。
    
27.                     break
    
28.                     
    
29.         return count

复制代码

LC. 3736. Minimum Moves to Equal Array Elements III

1. class Solution:
   
2.     def minMoves(self, nums: List[int]) -> int:
   
3.         ans = 0
   
4.         max_val = max(nums)
   
5. 
   
6.         for n in nums:
   
7.             ans += (max_val - n)
   
8.         return ans
   
9.         

复制代码

LC. 3212. Count Submatrices With Equal Frequency of X and Y

1. class Solution:
   
2.     def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
   
3.         freq = dict() #freq of 'X', 'Y', and '.'
   
4.         curr_freq = {'X': [1, 0, 0], 'Y':[0, 1, 0], '.': [0, 0, 1]}
   
5.         n_row = len(grid)
   
6.         n_col = len(grid[0])
   
7.         # set first cell grid[0][0]
   
8.         freq[(0, 0)] =  curr_freq[grid[0][0]]
   
9.         # first row
   
10.         for i in range(1, n_col):
    
11.             freq[(0, i)] = [x + y for x, y in zip(freq[(0, i-1)], curr_freq[grid[0][i]])]
    
12.         # first col
    
13.         for i in range(1, n_row):
    
14.             freq[(i, 0)] = [x + y for x, y in zip(freq[(i-1, 0)], curr_freq[grid[i][0]])]
    
15.         # loop all other rows and cols
    
16.         for i in range(1, n_row):
    
17.             for j in range(1, n_col):
    
18.                 freq[(i, j)] = [ p+q-r+t for p, q, r, t in zip(freq[(i-1, j)], freq[(i, j-1)], freq[(i-1, j-1)], curr_freq[grid[i][j]])]
    
19.         # count freq with equal freq X and Y
    
20.         ans = 0
    
21.         for i in range(n_row):
    
22.             for j in range(n_col):
    
23.                 if freq[(i,j)][0] > 0 and freq[(i,j)][0] == freq[(i,j)][1]:
    
24.                     ans += 1
    
25.         return ans

复制代码

优化方向

1. 空间可以优化
你用字典存储，其实可以直接用二维数组，访问更快：
python# 当前写法
freq = dict()
freq[(i, j)] = [x_count, y_count, dot_count]

# 优化写法
freq = [[[0, 0, 0] for _ in range(n_col)] for _ in range(n_row)]
freq[i][j] = [x_count, y_count, dot_count]
2. 不需要存储 '.' 的数量
题目只关心 X 和 Y 的数量，不需要统计 '.'：
python# 简化
curr_freq = {'X': [1, 0], 'Y': [0, 1], '.': [0, 0]}
3. 代码可以更简洁
第一行、第一列、其他格子可以统一处理：

1. class Solution:
   
2.     def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
   
3.         m, n = len(grid), len(grid[0])
   
4.         
   
5.         # freq[i][j] = [X的数量, Y的数量] 在子矩阵 (0,0) 到 (i,j) 中
   
6.         freq = [[[0, 0] for _ in range(n)] for _ in range(m)]
   
7.         
   
8.         ans = 0
   
9.         
   
10.         for i in range(m):
    
11.             for j in range(n):
    
12.                 # 当前格子的贡献
    
13.                 x_add = 1 if grid[i][j] == 'X' else 0
    
14.                 y_add = 1 if grid[i][j] == 'Y' else 0
    
15.                
    
16.                 # 计算前缀和
    
17.                 if i == 0 and j == 0:
    
18.                     freq[i][j] = [x_add, y_add]
    
19.                 elif i == 0:
    
20.                     freq[i][j][0] = freq[i][j-1][0] + x_add
    
21.                     freq[i][j][1] = freq[i][j-1][1] + y_add
    
22.                 elif j == 0:
    
23.                     freq[i][j][0] = freq[i-1][j][0] + x_add
    
24.                     freq[i][j][1] = freq[i-1][j][1] + y_add
    
25.                 else:
    
26.                     # 包含-排斥原理
    
27.                     freq[i][j][0] = freq[i-1][j][0] + freq[i][j-1][0] - freq[i-1][j-1][0] + x_add
    
28.                     freq[i][j][1] = freq[i-1][j][1] + freq[i][j-1][1] - freq[i-1][j-1][1] + y_add
    
29.                
    
30.                 # 检查条件
    
31.                 x_count, y_count = freq[i][j]
    
32.                 if x_count > 0 and x_count == y_count:
    
33.                     ans += 1
    
34.         
    
35.         return ans

复制代码

LC 3731. Find Missing Elements

1. class Solution:
   
2.     def findMissingElements(self, nums: List[int]) -> List[int]:
   
3.         low, high = min(nums), max(nums)
   
4. 
   
5.         if len(nums) == (high - low + 1): return []
   
6.         else:
   
7.             nums_set = set(nums)
   
8.             ans = []
   
9.             for n in range(low, high + 1):
   
10.                 if n not in nums_set:
    
11.                     ans.append(n)
    
12.         return ans

复制代码

更好的解法，不额外引入空间，

优化解法：排序 + 线性扫描
如果我们将数组排序，那么缺失的数字必然存在于相邻两个元素 nums[i] 和 nums[i+1] 之间的空隙里。

1. class Solution:
   
2.     def findMissingElements(self, nums: List[int]) -> List[int]:
   
3.         # 1. 原地排序，不消耗额外空间（或消耗 O(log N) 的递归栈空间）
   
4.         nums.sort()
   
5.         ans = []
   
6.         
   
7.         # 2. 遍历相邻元素
   
8.         for i in range(len(nums) - 1):
   
9.             # 如果两个数不连续（差值大于 1）
   
10.             # 缺失的部分就是 (nums[i] + 1) 到 (nums[i+1] - 1)
    
11.             for miss in range(nums[i] + 1, nums[i+1]):
    
12.                 ans.append(miss)
    
13.         
    
14.         return ans

复制代码