刷题记录帖子

LC 3582. Generate Tag for Video Caption
简单题，但是还是可以优化。

1. class Solution:
   
2.     def generateTag(self, caption: str) -> str:
   
3.         words = caption.split()
   
4.         if not words: return "#"
   
5.         
   
6.         res = ["#"]
   
7.         curr_len = 1
   
8.         
   
9.         for i, w in enumerate(words):
   
10.             word = w.lower() if i == 0 else w.capitalize()
    
11.             res.append(word)
    
12.             curr_len += len(word)
    
13.             
    
14.             # 还是你说的逻辑：先加进去，发现长了再处理
    
15.             if curr_len >= 100:
    
16.                 return "".join(res)[:100]
    
17.         
    
18.         return "".join(res)

复制代码

或者不直接提前截断，当然这个就会带来额外开销但是更加简洁。

1. class Solution:
   
2.     def generateTag(self, caption: str) -> str:
   
3.         # 1. 拆分单词，split() 自动处理多余空格
   
4.         words = caption.split()
   
5.         if not words:
   
6.             return "#"
   
7.         
   
8.         # 2. 处理第一个单词（全小写）
   
9.         res_parts = [words[0].lower()]
   
10.         
    
11.         # 3. 处理后续单词（首字母大写，其余小写）
    
12.         for i in range(1, len(words)):
    
13.             res_parts.append(words[i].capitalize())
    
14.             
    
15.         # 4. 拼接并添加前缀 #
    
16.         # 注意：题目说 caption 只包含字母和空格，所以 split 之后合并就已经去掉了非法字符
    
17.         tag = "#" + "".join(res_parts)
    
18.         
    
19.         # 5. 按照题目要求顺序，最后进行截断
    
20.         return tag[:100]

复制代码

3581. Count Odd Letters from Number

You are given an integer n perform the following steps:

Convert each digit of n into its lowercase English word (e.g., 4 → "four", 1 → "one").
Concatenate those words in the original digit order to form a string s.
Return the number of distinct characters in s that appear an odd number of times.



Example 1:

Input: n = 41

Output: 5

Explanation:

41 → "fourone"

Characters with odd frequencies: 'f', 'u', 'r', 'n', 'e'. Thus, the answer is 5.

Example 2:

Input: n = 20

Output: 5

Explanation:

20 → "twozero"

Characters with odd frequencies: 't', 'w', 'z', 'e', 'r'. Thus, the answer is 5.



Constraints:

1 <= n <= 109

1. class Solution:
   
2.     def countOddLetters(self, n: int) -> int:
   
3.         dtos_map = {
   
4.             '0': 'zero',
   
5.             '1': 'one',
   
6.             '2': 'two',
   
7.             '3': 'three',
   
8.             '4': 'four',
   
9.             '5': 'five',
   
10.             '6': 'six',
    
11.             '7': 'seven',
    
12.             '8': 'eight',
    
13.             '9': 'nine'
    
14.         }
    
15. 
    
16.         s = []
    
17.         for ch in str(n):
    
18.             s.append( dtos_map[ch] )
    
19.         
    
20.         f = Counter("".join(s))
    
21. 
    
22.         ans = 0
    
23.         for k, v in f.items():
    
24.             if v % 2 == 1:
    
25.                 ans += 1
    
26.         return ans
    
27. 
    
28.         

复制代码

3591. Check if Any Element Has Prime Frequency

1. class Solution:
   
2.     def checkPrimeFrequency(self, nums: List[int]) -> bool:
   
3. 
   
4.         def isPrime(num):
   
5.             if num == 1: return False
   
6.             if num == 2: return True
   
7.             if num == 3: return True
   
8.             for n in range(2, int(math.sqrt(num)) + 1):
   
9.                 if num % n == 0:
   
10.                     return False
    
11.             return True
    
12. 
    
13.         freq = Counter(nums)
    
14. 
    
15.         for k,v in freq.items():
    
16.             if isPrime(v):
    
17.                 return True
    
18.         return False

复制代码

isPrime 算法可以提高

1. from collections import Counter
   
2. import math
   
3. 
   
4. class Solution:
   
5.     def checkPrimeFrequency(self, nums: list[int]) -> bool:
   
6.         def is_prime(n: int) -> bool:
   
7.             if n < 2: return False
   
8.             # 试除法：从 2 检查到 sqrt(n)
   
9.             for i in range(2, int(math.sqrt(n)) + 1):
   
10.                 if n % i == 0:
    
11.                     return False
    
12.             return True
    
13. 
    
14.         # 1. 统计频率
    
15.         counts = Counter(nums)
    
16.         
    
17.         # 2. 遍历频率（只需要频率，不需要 key）
    
18.         for freq in counts.values():
    
19.             if is_prime(freq):
    
20.                 return True
    
21.         
    
22.         return False

复制代码

LC. 3917. Count Indices With Opposite Parity

周赛题目，我的解法

1. class Solution:
   
2.     def countOppositeParity(self, nums: list[int]) -> list[int]:
   
3.         # count from right
   
4.         n_odd, n_even = 0, 0
   
5.         ans = []
   
6. 
   
7.         for i in range(len(nums)-1, -1, -1):
   
8.             
   
9.             if nums[i] % 2 == 1:
   
10.                 ans.append(n_even)
    
11.                 n_odd += 1
    
12.             else:
    
13.                 ans.append(n_odd)
    
14.                 n_even += 1
    
15.         ans.reverse()
    
16.         return ans

复制代码

当然完全可以预先分配数组，然后遍历的时候填写，会更快。

1. class Solution:
   
2.     def countOppositeParity(self, nums: list[int]) -> list[int]:
   
3.         # count from right
   
4.         n_odd, n_even = 0, 0
   
5.         ans = [0] * len(nums)
   
6. 
   
7.         for i in range(len(nums)-1, -1, -1):
   
8.             
   
9.             if nums[i] % 2 == 1:
   
10.                 ans[i] = n_even
    
11.                 n_odd += 1
    
12.             else:
    
13.                 ans[i] = n_odd
    
14.                 n_even += 1
    
15.             
    
16.         return ans

复制代码

LC 3918. Sum of Primes Between Number and Its Reverse

简单题目，就是 isPrime 的代码值得精简下。

1. class Solution:
   
2.     def sumOfPrimesInRange(self, n: int) -> int:
   
3. 
   
4.         def isPrime(n):
   
5.             if n == 1: return False
   
6.             if n == 2: return True
   
7.             if n == 3: return True
   
8. 
   
9.             for i in range(2, int(math.sqrt(n))+1):
   
10.                 if n % i == 0:
    
11.                     return False
    
12.             return True
    
13. 
    
14.         s = [ch for ch in str(n)]
    
15.         s.reverse()
    
16.         r = int("".join(s))
    
17. 
    
18.         start, end = min(n, r), max(n, r)
    
19. 
    
20.         ans = 0
    
21. 
    
22.         for n in range(start, end + 1):
    
23.             if isPrime(n):
    
24.                 ans += n
    
25.         return ans

复制代码

更好的解法，

1. class Solution:
   
2.     def sumOfPrimesInRange(self, n: int) -> int:
   
3.         
   
4.         # 优化后的素数判断
   
5.         def isPrime(num: int) -> bool:
   
6.             if num < 2:
   
7.                 return False
   
8.             # 只需要判断到根号 num 即可
   
9.             for i in range(2, int(num ** 0.5) + 1):
   
10.                 if num % i == 0:
    
11.                     return False
    
12.             return True
    
13. 
    
14.         # Pythonic: 一行实现数字反转
    
15.         r = int(str(n)[::-1])
    
16.         
    
17.         # 确定区间边界
    
18.         start, end = min(n, r), max(n, r)
    
19.         
    
20.         # 遍历区间求和
    
21.         ans = 0
    
22.         for i in range(start, end + 1):
    
23.             if isPrime(i):
    
24.                 ans += i
    
25.                
    
26.         return ans

复制代码

当然这道题目还有进阶的解法，就是如果这个 service 被调用很多次怎么办？

埃氏筛 (Sieve of Eratosthenes) + 前缀和 (Prefix Sum)

1. class PrimeService:
   
2.     def __init__(self, max_n):
   
3.         self.is_prime = [True] * (max_n + 1)
   
4.         self.is_prime[0] = self.is_prime[1] = False
   
5.         
   
6.         # 1. 埃氏筛
   
7.         for i in range(2, int(max_n**0.5) + 1):
   
8.             if self.is_prime[i]:
   
9.                 # 从 i*i 开始标记，因为 2i, 3i 等已经在前面被 2, 3 标记过了
   
10.                 for j in range(i * i, max_n + 1, i):
    
11.                     self.is_prime[j] = False
    
12.         
    
13.         # 2. 预计算前缀和
    
14.         self.prime_sums = [0] * (max_n + 1)
    
15.         current_sum = 0
    
16.         for i in range(max_n + 1):
    
17.             if self.is_prime[i]:
    
18.                 current_sum += i
    
19.             self.prime_sums[i] = current_sum
    
20. 
    
21.     def get_sum_in_range(self, start, end):
    
22.         # O(1) 得到结果
    
23.         if start > end: return 0
    
24.         return self.prime_sums[end] - self.prime_sums[start - 1]
    
25. 
    
26. # 使用示例
    
27. # service = PrimeService(1000)
    
28. # print(service.get_sum_in_range(13, 31))

复制代码

LC  796. Rotate String

这道题目说穿了，就是这种 最左到最右旋转，是 double string/array, A shift on s consists of moving the leftmost character of s to the rightmost position.

1. class Solution:
   
2.     def rotateString(self, s: str, goal: str) -> bool:
   
3.         # edge case
   
4.         if len(s) != len(goal): return False
   
5.         double_s = s + s
   
6.         return double_s.find(goal) != -1

复制代码

LC 61. Rotate List

一开始没想出怎么做，暴力直接拉了数组来做。

1. # Definition for singly-linked list.
   
2. # class ListNode:
   
3. #     def __init__(self, val=0, next=None):
   
4. #         self.val = val
   
5. #         self.next = next
   
6. class Solution:
   
7.     def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
   
8.         ans = []
   
9.         curr = head
   
10.         while curr:
    
11.             ans.append(curr.val)
    
12.             curr = curr.next
    
13.         n = len(ans)
    
14.         ans = ans + ans
    
15.         if n == 0: return head
    
16.         realk = k % n
    
17.         curr = head
    
18. 
    
19.         ans = ans[n-realk:2*n-realk]
    
20. 
    
21.         while curr:
    
22.             curr.val = ans.pop(0)
    
23.             curr = curr.next
    
24.         return head

复制代码

但是更好的方法是下面的，

1. # Definition for singly-linked list.
   
2. # class ListNode:
   
3. #     def __init__(self, val=0, next=None):
   
4. #         self.val = val
   
5. #         self.next = next
   
6. class Solution:
   
7.     def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
   
8.         # 1. 边界条件处理（空链表、只有一个节点的链表、k为0）
   
9.         if not head or not head.next or k == 0:
   
10.             return head
    
11.         
    
12.         # 2. 第一次遍历：计算链表长度 n，并找到当前的尾节点
    
13.         n = 1
    
14.         tail = head
    
15.         while tail.next:
    
16.             n += 1
    
17.             tail = tail.next
    
18.             
    
19.         # 计算实际需要旋转的步数（避免 k 大于 n 的情况）
    
20.         real_k = k % n
    
21.         if real_k == 0:
    
22.             return head # 如果是长度的整数倍，相当于没转，直接返回
    
23.             
    
24.         # 3. 将链表首尾相连，形成闭环
    
25.         tail.next = head
    
26.         
    
27.         # 4. 找到新的尾节点，也就是第 n - real_k 个节点
    
28.         # 从头节点开始，走 n - real_k - 1 步就能到达新尾巴
    
29.         new_tail = head
    
30.         for _ in range(n - real_k - 1):
    
31.             new_tail = new_tail.next
    
32.             
    
33.         # 5. 断开环，并记录新的头节点
    
34.         new_head = new_tail.next
    
35.         new_tail.next = None
    
36.         
    
37.         return new_head

复制代码

LC 3660. Jump Game IX

说实话，好久没做 Jump Game 没想到已经这么变态的难度了。。。

这道题目，先要想到

Jump to index j where j > i is allowed only if nums[j] < nums[i].

Jump to index j where j < i is allowed only if nums[j] > nums[i].

i， j 是互相可以 jump 的，强连通的。

说实话，我就没想到。

下面一步也没想到，

强连通的条件下，那么什么情况下两个区域会彻底断绝联系呢？

当存在一个划分点 $p$，使得左侧区域 $\{0 \dots p\}$ 的最大值 $\leq$ 右侧区域 $\{p+1 \dots n-1\}$ 的最小值时，任何跨越这个边界的跳跃都是不可能的：左跳右：需要右边某个数 $<$ 左边某个数，但现在左边最大都 < 右边最小，不可能。右跳左：需要左边某个数 $>$ 右边某个数，同理，不可能。因此，我们可以把数组切分成若干个独立块（Chunks）。在每一个独立块内部，由于无法再进一步根据上述规则切分，块内的所有元素都是互相可达的。

1. def maxReachableValue(nums):
   
2.     n = len(nums)
   
3.     if n == 0: return []
   
4.    
   
5.     # 1. 预处理前缀最大值
   
6.     pref_max = [0] * n
   
7.     pref_max[0] = nums[0]
   
8.     for i in range(1, n):
   
9.         pref_max[i] = max(pref_max[i-1], nums[i])
   
10.         
    
11.     # 2. 预处理后缀最小值
    
12.     suff_min = [0] * n
    
13.     suff_min[n-1] = nums[n-1]
    
14.     for i in range(n-2, -1, -1):
    
15.         suff_min[i] = min(suff_min[i+1], nums[i])
    
16.         
    
17.     ans = [0] * n
    
18.     start = 0
    
19.    
    
20.     # 3. 线性扫描划分块
    
21.     for i in range(n):
    
22.         # 如果 i 是当前块的结尾（或者是数组最后一个元素）
    
23.         # 划分条件：前缀最大 <= 剩余部分的后缀最小
    
24.         if i == n - 1 or pref_max[i] <= suff_min[i+1]:
    
25.             # 计算当前块 [start, i] 内的最大值
    
26.             # 其实在这个块里，最大值一定就是 pref_max[i]
    
27.             # 因为能在这个块里“混”的，最大值必然被带到了边界
    
28.             current_max = pref_max[i]
    
29.             
    
30.             # 填充该块内所有元素的答案
    
31.             for k in range(start, i + 1):
    
32.                 ans[k] = current_max
    
33.             
    
34.             # 更新下一个块的起点
    
35.             start = i + 1
    
36.             
    
37.     return ans

复制代码

LC. 3629. Minimum Jumps to Reach End via Prime Teleportation

绝对的好题，但是应该是 hard 至少好几个知识点融合在一起。

Leetcode 刷题伴侣
现在，请你把自己想象成一个城市交通规划师，我们从零开始，一步步把这道题（LC 3629）的底层逻辑盘通。

这道题的核心，就是解决“如何在极其复杂的路网中，快速找到从起点到终点的最短路线”。

第一步：认清“路网”的真面目（直观模型）
你站在一条直线上，下标从 0 到 n-1，每一个下标代表一个“小镇”。
从一个小镇出发，你只有两种移动方式：

走路（相邻步）：从 i 走到 i-1 或 i+1。这就像是小镇之间的一条泥土路，走一步算 1 步。

坐高铁（质数传送）：这是本题的重头戏。

如果当前小镇的数字 nums[i] 是一个质数（比如 2），说明这里有一座“2号高铁站”。

这座高铁站可以直达所有数字是 2 的倍数的小镇（比如数字为 4, 6, 8, 10 的小镇）。

关键点：只要你进了“2号高铁站”，出站走到任意一个目标小镇，总共也只算 1 步！

我们的目标：求从 0 镇走到 n-1 镇的最少步数。
算法选择：求最少步数 / 最短路，且每一步代价都是 1，绝对是 BFS（广度优先搜索）的主场。

第二步：为什么暴力的 BFS 会死得很惨？（避坑指南）
如果直接按 BFS 的套路写，你会遇到两个致命的性能瓶颈（TLE）：

死穴 1：每次进高铁站，都要扫一遍全国（O(N
2
) 复杂度）。
假设 nums = [2, 4, 6, 8, ..., 100000]。你在 0 镇遇到质数 2，开启传送门，你需要找全数组里所有 2 的倍数，耗时 O(N)。如果后面又走到一个包含质数 2 的镇子，你又要找一遍。这绝对超时。

破局方法：提前建好全国的高铁路线图！（建立 prime_to_indices 映射表）。

死穴 2：分解质因数太慢了。
要建高铁图，你就得知道每个小镇的数字（比如 12）到底包含哪些质数（2 和 3）。如果用常规的试除法 O(
V

​
) 去分解所有的数字，当数组很长且数字很大（10
6
）时，又会超时。

破局方法：预处理出一个“最小质因子（SPF）”表！ 查表分解，速度飞快。

第三步：算法的三大核心模块（庖丁解牛）
我们把算法拆成三个准备动作和一次正式行动。

模块 1：打造“快速分解机”（SPF 预处理）
我们用“埃氏筛法”的变体，提前准备一个大小为 10
6
+1 的数组 spf。
spf[x] 的意思是：数字 x 最小的质数爹是谁。

比如 spf[12] = 2，spf[15] = 3，spf[7] = 7。

有了这个表，我们要分解 12，就像剥洋葱：12 查表拿到 2 → 变成 6 → 6 查表拿到 2 → 变成 3 → 3 查表拿到 3 → 结束。不用再拿个 for 循环从头试了。

模块 2：绘制全国高铁网（建立映射）
我们遍历一次 nums，把所有小镇都注册到对应的高铁站里。
如果 nums[i] == 12，剥洋葱剥出了 2 和 3。
那我们就把小镇 i 扔进 高铁站 2 和 高铁站 3 的出站名单里。

Python
prime_to_indices[2].append(i)
prime_to_indices[3].append(i)
模块 3：发车！优化的 BFS（防重复核心）
这里是重中之重。我们要用两个备忘录（Set）：

visited_idx：记录哪些小镇已经去过了。去过的小镇绝对不走第二遍（BFS 最短路原则）。

visited_primes：记录哪些高铁站已经开启过了。（这是本题防超时的灵魂！）

为什么？假设你进了“2号高铁站”，你已经把所有 2 的倍数的小镇都加入了 BFS 队列。

如果以后你瞎逛又走到另一个带 2 的小镇，千万不要再进 2号高铁站了！ 因为该去的地方第一波就已经全安排上了，再进只会白费力气。

1. from collections import deque
   
2. 
   
3. class Solution:
   
4.     def minJumps(self, nums: List[int]) -> int:
   
5.         n = len(nums)
   
6.         if n == 1:
   
7.             return 0  # 已经在终点了
   
8.             
   
9.         max_val = max(nums)
   
10.         if max_val < 2:
    
11.             # 如果全是 1，说明没有任何高铁站，只能一步步走
    
12.             pass # 直接靠后面的普通 BFS 就能处理
    
13.         
    
14.         # ==========================================
    
15.         # 模块 1：预处理 SPF (Smallest Prime Factor) 数组
    
16.         # ==========================================
    
17.         spf = list(range(max_val + 1))
    
18.         for i in range(2, int(max_val**0.5) + 1):
    
19.             if spf[i] == i: # i 是质数
    
20.                 # 把 i 的所有倍数的最小质因子设为 i
    
21.                 for j in range(i * i, max_val + 1, i):
    
22.                     if spf[j] == j:
    
23.                         spf[j] = i
    
24. 
    
25.         def is_prime(x):
    
26.             return x >= 2 and spf[x] == x
    
27. 
    
28.         # ==========================================
    
29.         # 模块 2：绘制高铁网 (质数 -> 包含该质因子的下标列表)
    
30.         # ==========================================
    
31.         prime_to_indices = {}
    
32.         for i, val in enumerate(nums):
    
33.             temp = val
    
34.             while temp > 1:
    
35.                 p = spf[temp] # 获取最小质因子
    
36.                
    
37.                 # 如果这个高铁站是第一次遇到，建个新名单
    
38.                 if p not in prime_to_indices:
    
39.                     prime_to_indices[p] = []
    
40.                 prime_to_indices[p].append(i) # 把小镇 i 登记到 p 站
    
41.                
    
42.                 # 把当前的质因子 p 除干净，避免重复登记！
    
43.                 while temp % p == 0:
    
44.                     temp //= p
    
45. 
    
46.         # ==========================================
    
47.         # 模块 3：正式开始 BFS 寻路
    
48.         # ==========================================
    
49.         # 队列里存的是 (当前小镇下标, 已经走过的步数)
    
50.         queue = deque([(0, 0)])
    
51.         
    
52.         visited_idx = {0}       # 记录去过的小镇
    
53.         visited_primes = set()  # 记录开启过的高铁站
    
54.         
    
55.         while queue:
    
56.             curr_idx, steps = queue.popleft()
    
57.             
    
58.             # 找到终点啦！因为是 BFS，第一次找到的一定是最短距离
    
59.             if curr_idx == n - 1:
    
60.                 return steps
    
61.             
    
62.             # 【行动 A：泥土路（相邻走）】
    
63.             for nxt in [curr_idx - 1, curr_idx + 1]:
    
64.                 if 0 <= nxt < n and nxt not in visited_idx:
    
65.                     visited_idx.add(nxt)
    
66.                     queue.append((nxt, steps + 1))
    
67.             
    
68.             # 【行动 B：坐高铁（质数传送）】
    
69.             val = nums[curr_idx]
    
70.             if is_prime(val): # 只有当前数字本身是质数，才能进高铁站
    
71.                 p = val
    
72.                 # 如果这个高铁站之前没开启过，我们才开
    
73.                 if p not in visited_primes:
    
74.                     visited_primes.add(p) # 标记为已开启！
    
75.                     
    
76.                     # 把所有能到的目标小镇，全都塞进队列
    
77.                     if p in prime_to_indices:
    
78.                         for target_idx in prime_to_indices[p]:
    
79.                             if target_idx not in visited_idx:
    
80.                                 visited_idx.add(target_idx)
    
81.                                 queue.append((target_idx, steps + 1))
    
82.                                 
    
83.         # 如果队列空了都还没到终点，说明无路可走
    
84.         return -1

复制代码

补充内容 (2026-05-08 10:38 +08:00):
最后这个题目，看着像 DP 但是其实是 BFS， BFS 可以找最短距离是一个需要知道的结论，还是很常用的。

DP 我也试了，但是你会发现

dp[i]  会有来自 i-1, i+1 已经 primes 的多个来源，而且无法写出递推公式，所以BFS。

LC. 3921. Score Validator

1. class Solution:
   
2.     def scoreValidator(self, events: list[str]) -> list[int]:
   
3.         score, counter = 0, 0
   
4. 
   
5.         for e in events:
   
6.             if counter == 10: break
   
7. 
   
8.             if e in ["0", "1", "2", "3", "4", "6"]:
   
9.                 score += int(e)
   
10.             elif e == "W" :
    
11.                 counter += 1
    
12.             elif e == "WD" or e == "NB":
    
13.                 score += 1
    
14. 
    
15.         return [score, counter]
    

复制代码

补充内容 (2026-05-10 04:05 +08:00):
class Solution:
    def scoreValidator(self, events: list[str]) -> list[int]:
        score, counter = 0, 0
        
        # 定义加分类事件，提高查找效率
        # 这里可以直接用 isdigit() 配合题目给出的合法数字，或者用 set
        numeric_scores = {"0", "1", "2", "3", "4", "6"}
        
        for e in events:
            # 1. 检查终止条件：如果 counter 已经到 10，直接跳出
            if counter >= 10:
                break
               
            # 2. 分类处理事件
            if e in numeric_scores:
                score += int(e)
            elif e == "W":
                counter += 1
                # 细节：如果 counter 变成 10 后需要立即停止，
                # 虽然下一轮循环开头会检查，但在某些变体题里这里可能需要额外逻辑。
            elif e == "WD" or e == "NB":
                score += 1
               
        return [score, counter]

补充内容 (2026-05-10 04:06 +08:00):
优化一下分数列表，完全可以用 set 而且不用每轮都创建，可以设置成常量