刷题记录帖子

Myron2017

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.

SELECT
player_id,
event_date,
SUM(games_played) OVER (
PARTITION BY player_id
ORDER BY event_date
) AS games_played_so_far
FROM
Activity;

复制代码

SELECT
a1.player_id,
a1.event_date,
SUM(a2.games_played) AS games_played_so_far
FROM
Activity a1
JOIN
Activity a2 ON a1.player_id = a2.player_id
AND a1.event_date >= a2.event_date
GROUP BY
a1.player_id, a1.event_date;

复制代码

Myron2017

550. Game Play Analysis IV

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 fraction of players that logged in again on the day after the day they first logged in, rounded to 2 decimal places. In other words, you need to determine the number of players who logged in on the day immediately following their initial login, and divide it by the number of total players.

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-03-02 | 6          |

| 2       | 3       | 2017-06-25 | 1          |

| 3       | 1       | 2016-03-02 | 0          |

| 3       | 4       | 2018-07-03 | 5          |

+-----------+-----------+------------+--------------+Output:

+-----------+

| fraction  |

+-----------+

| 0.33    |

+-----------+Explanation:

Only the player with id 1 logged back in after the first day he had logged in so the answer is 1/3 = 0.33

主要考察的是次日留存率的计算。解题思路要计算次日留存率，我们需要完成三个步骤：找到每个玩家的首次登录日期（分母的基础）。判断该玩家在首次登录的“第二天”是否也登录了（分子的基础）。计算比例：$\text{次日留存人数} / \text{总人数}$。

SELECT
ROUND(
COUNT(t2.player_id) / COUNT(t1.player_id),
2
) AS fraction
FROM (
-- 步骤 1: 找出每个玩家的首次登录日期
SELECT player_id, MIN(event_date) AS first_login
FROM Activity
GROUP BY player_id
) t1
-- 步骤 2: 尝试连接原表，看是否存在 (首登日期 + 1天) 的记录
LEFT JOIN Activity t2 ON
t1.player_id = t2.player_id AND
DATEDIFF(t2.event_date, t1.first_login) = 1;

复制代码

Myron2017

LC. 3908. Valid Digit Number

简单题，直接 string 操作。

class Solution:
def validDigit(self, n: int, x: int) -> bool:
s = str(n)
return (s[0] != str(x)) and (str(x) in s)

复制代码

Myron2017

LC 3914. Minimum Operations to Make Array Non Decreasing
Solved
Medium
Hint
You are given an integer array nums of length n.

In one operation, you may choose any subarray nums[l..r] and increase each element in that subarray by x, where x is any positive integer.

Return the minimum possible sum of the values of x across all operations required to make the array non-decreasing.

An array is non-decreasing if nums[i] <= nums[i + 1] for all 0 <= i < n - 1.

Example 1:

Input: nums = [3,3,2,1]

Output: 2

Explanation:

One optimal set of operations:

Choose subarray [2..3] and add x = 1 resulting in [3, 3, 3, 2]
Choose subarray [3..3] and add x = 1 resulting in [3, 3, 3, 3]
The array becomes non-decreasing, and the total sum of chosen x values is 1 + 1 = 2.

Example 2:

Input: nums = [5,1,2,3]

Output: 4

Explanation:

One optimal set of operations:

Choose subarray [1..3] and add x = 4 resulting in [5, 5, 6, 7]
The array becomes non-decreasing, and the total sum of chosen x values is 4.

Constraints:

1 <= n == nums.length <= 105
1 <= nums[i] <= 109

✅ 这题的本质总结
🧠 一句话核心

你不是在“修每个点”，而是在用区间 +x 去填补“下降造成的缺口”，目标是让数组最终不再下降。

🧠 正确理解“坑”

只有一种情况需要处理：

nums[i] > nums[i+1]

👉 这叫“下降”

🧠 关键直觉

每个下降意味着：

后面至少要被“抬到前面的高度”

但注意：

👉 这个抬升可以顺带影响后面一整段

🧠 为什么不是逐个点累加？

因为：

一次区间 +x
可以同时修复多个位置
不需要为每个位置重复付钱
🧠 最重要的结构理解

你最终在做的是：

构造一个“最小增量数组 inc”，让 nums + inc 变成非递减

🧠 成本本质

👉 成本 = 所有必须发生的“抬升高度变化”

但这些抬升是：

可以合并的
可以覆盖多个点的
不会重复计费
🧠 回到你的例子
[1, 100, 2, 3]

只有一个真正问题：

100 → 2

👉 必须整体补到 100

✅ 最优操作
[2..3] +98

最终：

[1, 100, 100, 101]
✅ 最终答案
98
🧠 一句话终极总结（面试版）

只需要找到“最深下降点”，做一次最小整体抬升，并利用区间操作传播到后面即可。

🧠 一句话本质

用最少“区间 +x 操作”，让数组变成非递减，本质是在修复所有下降，并尽量共享一次抬升的成本。

🔍 关键观察

只看相邻：

如果 nums[i] ≤ nums[i+1] → 没事
如果 nums[i] > nums[i+1] → 出现“下降”

👉 下降就是“必须修复的地方”。

🧠 核心直觉

每个下降意味着：

后面的值太小，至少要被抬到前一个高度

但注意：

👉 这个“抬升”可以用一个区间操作覆盖后面一整段
👉 所以不会为每个位置重复付钱

🧠 最重要的本质（一定要记住）

你其实在做：

构造一个最小“补偿数组 inc”，让 nums + inc 变成非递减

🧠 为什么答案不是逐点累加？

因为：

一个 +x 操作可以影响很多位置
多个“下降”可以被同一次操作一起解决
成本不是“点的数量”，而是“必要抬升层数”
🧠 正确贪心理解

从左到右：

一旦出现下降
就需要“至少补齐这个差值”
并且可以把这个补偿延续到后面

👉 每次只处理“新增必须抬升的部分”

🧠 最终结论（算法本质）

👉 答案 = 所有“必要抬升量”的合并成本（不会重复计算）

🚀 面试级一句话总结

扫描数组，发现下降就需要引入一次“区间抬升”，这些抬升可以覆盖后续位置，因此只计算必要的最小抬升层数，而不是逐点累加。

class Solution:
def minOperations(self, nums: list[int]) -> int:
ans = 0
for i in range(len(nums)-1):
diff = nums[i] - nums[i+1]
if diff > 0:
ans += diff
return ans

复制代码

Myron2017

LC 3913. Sort Vowels by Frequency
Solved
Medium
Hint
You are given a string s consisting of lowercase English characters.

Rearrange only the vowels in the string so that they appear in non-increasing order of their frequency.

If multiple vowels have the same frequency, order them by the position of their first occurrence in s.

Return the modified string.

Vowels are 'a', 'e', 'i', 'o', and 'u'.

The frequency of a letter is the number of times it occurs in the string.

Example 1:

Input: s = "leetcode"

Output: "leetcedo"

Explanation:

Vowels in the string are ['e', 'e', 'o', 'e'] with frequencies: e = 3, o = 1.
Sorting in non-increasing order of frequency and placing them back into the vowel positions results in "leetcedo".
Example 2:

Input: s = "aeiaaioooa"

Output: "aaaaoooiie"

Explanation:

Vowels in the string are ['a', 'e', 'i', 'a', 'a', 'i', 'o', 'o', 'o', 'a'] with frequencies: a = 4, o = 3, i = 2, e = 1.
Sorting them in non-increasing order of frequency and placing them back into the vowel positions results in "aaaaoooiie".
Example 3:

Input: s = "baeiou"

Output: "baeiou"

Explanation:

Each vowel appears exactly once, so all have the same frequency.
Thus, they retain their relative order based on first occurrence, and the string remains unchanged.

Constraints:

1 <= s.length <= 105
s consists of lowercase English letters

class Solution:
def sortVowels(self, s: str) -> str:
freqDict = {'a':0, 'e':0, 'i':0, 'o':0,'u':0}
firstOccDict = {'a':-1, 'e':-1, 'i':-1, 'o':-1, 'u':-1}
vowel_ind = []
for ind, ch in enumerate(s):
if ch in ['a', 'e', 'i', 'o', 'u']:
vowel_ind.append(ind)
freqDict[ch] += 1
if firstOccDict[ch] == -1:
firstOccDict[ch] = ind
sorted_list = []
for ch in ['a', 'e', 'i', 'o', 'u']:
if freqDict[ch] != 0:
sorted_list.append((-freqDict[ch], firstOccDict[ch], ch))
sorted_list.sort()
s_list = [ch for ch in s]
i = 0
for sl in sorted_list:
curr_ch = sl[2]
curr_freq = -sl[0]
while curr_freq:
s_list[vowel_ind[i]] = curr_ch
curr_freq -= 1
i += 1
return "".join(s_list)

复制代码

这道题目还是可以优化的，我做的时候比较急，所以很多时候没考虑更简化的写法。

class Solution:
def sortVowels(self, s: str) -> str:
vowels_set = set('aeiou')
# 1. 统计频率和首次出现位置
freq = {}
first_occ = {}
vowel_positions = [] # 记录 s 中哪些位置是元音
for i, ch in enumerate(s):
if ch in vowels_set:
vowel_positions.append(i)
freq[ch] = freq.get(ch, 0) + 1
if ch not in first_occ:
first_occ[ch] = i
# 2. 构造待排序的元音列表
# 规则：(-频率, 首次出现下标)
unique_vowels = list(freq.keys())
unique_vowels.sort(key=lambda x: (-freq[x], first_occ[x]))
# 3. 展开排序后的元音序列
# 比如 e 出现 3 次，o 出现 1 次 -> ['e', 'e', 'e', 'o']
sorted_vowels_stream = []
for v in unique_vowels:
sorted_vowels_stream.extend([v] * freq[v])
# 4. 覆写回原字符串
res = list(s)
for idx, v in zip(vowel_positions, sorted_vowels_stream):
res[idx] = v
return "".join(res)

复制代码

Myron2017

LC 3912. Valid Elements in an Array

You are given an integer array nums.

An element nums[i] is considered valid if it satisfies at least one of the following conditions:

It is strictly greater than every element to its left.
It is strictly greater than every element to its right.
The first and last elements are always valid.

Return an array of all valid elements in the same order as they appear in nums.

Example 1:

Input: nums = [1,2,4,2,3,2]

Output: [1,2,4,3,2]

Explanation:

nums[0] and nums[5] are always valid.
nums[1] and nums[2] are strictly greater than every element to their left.
nums[4] is strictly greater than every element to its right.
Thus, the answer is [1, 2, 4, 3, 2].
Example 2:

Input: nums = [5,5,5,5]

Output: [5,5]

Explanation:

The first and last elements are always valid.
No other elements are strictly greater than all elements to their left or to their right.
Thus, the answer is [5, 5].
Example 3:

Input: nums = [1]

Output: [1]

Explanation:

Since there is only one element, it is always valid. Thus, the answer is [1].

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

class Solution:
def findValidElements(self, nums: list[int]) -> list[int]:
n = len(nums)
if n == 1: return nums
else:
ansInd = set()
# find strictly greater than every element to its left
leftMax = -1
for i in range(n):
if nums[i] > leftMax:
leftMax = nums[i]
if i not in ansInd:
ansInd.add(i)
# strictly greater than every element to its right
rightMax = -1
for i in range(n-1, -1, -1):
if nums[i] > rightMax:
rightMax = nums[i]
if i not in ansInd:
ansInd.add(i)
ansInd = sorted(list(ansInd))
return [nums[i] for i in ansInd]

复制代码

索引排序的替代方案：虽然排序索引（$O(N \log N)$）在 $N=100$ 时完全没问题，但如果 $N$ 很大，我们可以改用一个布尔数组（[False] * n），这样最后按顺序扫一遍布尔数组即可，复杂度稳稳维持在 $O(N)$。

class Solution:
def findValidElements(self, nums: list[int]) -> list[int]:
n = len(nums)
if n <= 2:
return nums # 1个或2个元素时，首尾规则保证全部有效
# 使用布尔数组记录每个位置是否有效，避免最后的排序
is_valid = [False] * n
# 规则 3：首尾始终有效
is_valid[0] = True
is_valid[n-1] = True
# 规则 1：严格大于左边所有元素
left_max = nums[0]
for i in range(1, n - 1):
if nums[i] > left_max:
is_valid[i] = True
left_max = nums[i]
# 规则 2：严格大于右边所有元素
right_max = nums[n-1]
for i in range(n - 2, 0, -1):
if nums[i] > right_max:
is_valid[i] = True
right_max = nums[i]
# 按原顺序收集结果
return [nums[i] for i in range(n) if is_valid[i]]

复制代码

Myron2017

LC. 1559. Detect Cycles in 2D Grid
Solved
Medium
Topics
conpanies icon
Companies
Hint
Given a 2D array of characters grid of size m x n, you need to find if there exists any cycle consisting of the same value in grid.

A cycle is a path of length 4 or more in the grid that starts and ends at the same cell. From a given cell, you can move to one of the cells adjacent to it - in one of the four directions (up, down, left, or right), if it has the same value of the current cell.

Also, you cannot move to the cell that you visited in your last move. For example, the cycle (1, 1) -> (1, 2) -> (1, 1) is invalid because from (1, 2) we visited (1, 1) which was the last visited cell.

Return true if any cycle of the same value exists in grid, otherwise, return false.

Example 1:

Input: grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
Output: true
Explanation: There are two valid cycles shown in different colors in the image below:

Example 2:

Input: grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
Output: true
Explanation: There is only one valid cycle highlighted in the image below:

Example 3:

Input: grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
Output: false

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid consists only of lowercase English letters.

import sys
class Solution:
def containsCycle(self, grid: List[List[str]]) -> bool:
# 1. 应对大规模网格，Python 必须增加递归深度限制
sys.setrecursionlimit(300000)
nrows, ncols = len(grid), len(grid[0])
visited = [[False] * ncols for _ in range(nrows)]
def DFS(r, c, pr, pc):
visited[r][c] = True
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
# 越界判断 & 字符相同判断
if 0 <= nr < nrows and 0 <= nc < ncols and grid[nr][nc] == grid[r][c]:
# 关键点 1：如果是父节点，直接跳过
if (nr, nc) == (pr, pc):
continue
# 关键点 2：如果邻居已经访问过，且不是父节点 -> 发现环！
if visited[nr][nc]:
return True
# 关键点 3：继续递归，如果递归深处发现了环，立即向上返回 True
if DFS(nr, nc, r, c):
return True
return False
for i in range(nrows):
for j in range(ncols):
if not visited[i][j]:
if DFS(i, j, -1, -1):
return True
return False

复制代码

或者用 set 判断 vistied

from typing import List
class Solution:
def containsCycle(self, grid: List[List[str]]) -> bool:
nrows, ncols = len(grid), len(grid[0])
visited = set() # 使用 set 或二维数组均可，set 在 Python 中很常用
def hasCycle(r, c, pr, pc):
visited.add((r, c))
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
# 1. 边界检查 & 字符匹配
if 0 <= nr < nrows and 0 <= nc < ncols and grid[nr][nc] == grid[r][c]:
# 2. 关键：不能走回头路
if (nr, nc) == (pr, pc):
continue
# 3. 核心：如果遇到已访问节点，说明绕了一圈回来了
if (nr, nc) in visited:
return True
# 4. 递归探索，只有发现 True 时才向上返回
if hasCycle(nr, nc, r, c):
return True
return False
# 遍历所有起点
for i in range(nrows):
for j in range(ncols):
if (i, j) not in visited:
if hasCycle(i, j, -1, -1):
return True
return False

复制代码

Myron2017

2033. Minimum Operations to Make a Uni-Value Grid

Hint
You are given a 2D integer grid of size m x n and an integer x. In one operation, you can add x to or subtract x from any element in the grid.

A uni-value grid is a grid where all the elements of it are equal.

Return the minimum number of operations to make the grid uni-value. If it is not possible, return -1.

Example 1:

Input: grid = [[2,4],[6,8]], x = 2
Output: 4
Explanation: We can make every element equal to 4 by doing the following:
- Add x to 2 once.
- Subtract x from 6 once.
- Subtract x from 8 twice.
A total of 4 operations were used.
Example 2:

Input: grid = [[1,5],[2,3]], x = 1
Output: 5
Explanation: We can make every element equal to 3.
Example 3:

Input: grid = [[1,2],[3,4]], x = 2
Output: -1
Explanation: It is impossible to make every element equal.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 105
1 <= m * n <= 105
1 <= x, grid[i][j] <= 104

还是很有意思的一道题目，数学模型说明白了很简单，找中位数。

但是这个 +x， -x 可以得到相同的数字，确实是我没怎么考虑过的。但是说白了很简单，如果两个数 $a$ 和 $b$ 之间的差值 $(a - b)$ 不能被 $x$ 整除，那你无论怎么加减 $x$，它们永远无法相等。技巧：我们可以统一检查所有数相对于第一个数的余数是否相同。或者更简单地，在计算步数时发现 diff % x != 0 就直接返回 -1。

class Solution:
def minOperations(self, grid: List[List[int]], x: int) -> int:
l = []
for i in range(len(grid)):
for j in range(len(grid[0])):
l.append(grid[i][j])
l.sort()
mid = len(l) // 2
m1, m2 = mid, mid - 1
if m2 < 0: return 0
a1, a2 = 0, 0
for e in l:
d1, d2 = abs(l[m1]-e), abs(l[m2]-e)
if d1 % x != 0:
return -1
else:
a1 += (d1//x)
if d2 % x != 0:
return -1
else:
a2 += (d2//x)
return min(a1, a2)

复制代码

另外一个优化点就是如何计算偶数个元素的时候的中位数，我的解法是考虑不同的位置，因为偶数中位数有两个，但是其实没有必要，这是等价的，两个中位数可以任意选择！

面试的时候考察起来应该是个很赞的点，如果可以证明出来。

from typing import List
class Solution:
def minOperations(self, grid: List[List[int]], x: int) -> int:
# 1. 扁平化矩阵
nums = [val for row in grid for val in row]
nums.sort()
# 2. 检查可行性：所有元素对 x 取模的余数必须相同
# 只需要对比所有元素是否和第一个元素同余
mod = nums[0] % x
for num in nums:
if num % x != mod:
return -1
# 3. 找到中位数
# 无论长度奇偶，取 len // 2 均可
mid_val = nums[len(nums) // 2]
# 4. 计算总操作步数
res = 0
for num in nums:
res += abs(num - mid_val) // x
return res

复制代码

Myron2017

LC. 3622. Check Divisibility by Digit Sum and Product
Solved
Easy
Topics
Hint
You are given a positive integer n. Determine whether n is divisible by the sum of the following two values:

The digit sum of n (the sum of its digits).

The digit product of n (the product of its digits).

Return true if n is divisible by this sum; otherwise, return false.

Example 1:

Input: n = 99

Output: true

Explanation:

Since 99 is divisible by the sum (9 + 9 = 18) plus product (9 * 9 = 81) of its digits (total 99), the output is true.

Example 2:

Input: n = 23

Output: false

Explanation:

Since 23 is not divisible by the sum (2 + 3 = 5) plus product (2 * 3 = 6) of its digits (total 11), the output is false.

Constraints:

1 <= n <= 106

这个题目唯一可以值得深入思考的就是乘积的初始化最好是 1.

class Solution:
def checkDivisibility(self, n: int) -> bool:
ds, dp = 0, 1
for ch in str(n):
ds += int(ch)
dp *= int(ch)
#print(ds, dp, ds+dp)
return n % (ds+dp) == 0

复制代码

Myron2017

LC. 396. Rotate Function

很有意思的题目，直接暴力做会 TLE。

但是如果仔细观察写出递推公式还是很容易的

F_n = F_n-1 + S0 - n * arr_k[n-1]

做出来的时候还是很舒服的。

还是 Leetcode 早起的题目经典而且有意思，现在的题目啊，为了出题而出题，很多题目吧，就是考察炫技没有啥思考的乐趣。

class Solution:
def maxRotateFunction(self, nums: List[int]) -> int:
n = len(nums)
F0 = 0
S0 = 0
for j in range(0, len(nums)):
F0 += j * nums[j]
S0 += nums[j]
ans = F0
# For F1 to Fn
# F_n = F_n-1 + S0 - n * arr_k[n-1]
start = n-1
F1 = 0
while start > 0:
F1 = F0 + S0 - n * nums[start]
F0 = F1
start -= 1
ans = max(F1, ans)
return ans

复制代码

当然如果非要优化也是可以的，比如用下 Python 的惯用法等，不过不影响整体思路。

class Solution:
def maxRotateFunction(self, nums: List[int]) -> int:
n = len(nums)
# 求整个数组的和
total_sum = sum(nums)
# 计算初始的 F(0)
current_f = sum(i * num for i, num in enumerate(nums))
# 记录最大值，初始值为 F(0)
max_f = current_f
# 遍历计算 F(1) 到 F(n-1)
# i 从 n-1 倒推到 1
for i in range(n - 1, 0, -1):
# 核心状态转移方程
current_f = current_f + total_sum - n * nums[i]
# 更新最大值
max_f = max(max_f, current_f)
return max_f

复制代码