刷题记录帖子

Myron2017

LC. 3823. Reverse Letters Then Special Characters in a String

优化就是 stack 如何反转，其实直接 pop 就行，不需要 revese + pop(0)

在 Python 中，list.pop(0) 会导致后续所有元素向前移动，这是一个 O(N) 的操作。如果字符串很长，整个循环就会变成 O(N^2)。

class Solution:
def reverseByType(self, s: str) -> str:
letters = []
special = []
for ch in s:
if ch.isalpha():
letters.append(ch)
else:
special.append(ch)
#letters.reverse()
#special.reverse()
ans = []
for ch in s:
if ch.isalpha():
ans.append(letters.pop())
else:
ans.append(special.pop())
return "".join(ans)

复制代码

补充内容 (2026-03-15 00:15 +08:00):

我们依然保持思路的清晰性，但通过从后弹出（
pop()
复制代码
）来保证 $O(1)$ 的处理效率。

Myron2017

LC. 3813. Vowel-Consonant Score

一次遍历：只需要扫描一遍字符串 s，时间复杂度 $O(N)$。可读性高：逻辑分层清晰——先判断是不是字母，再判断是哪种字母。健壮性：ch.isalpha() 自动过滤了数字、空格和特殊符号，不管题目增加多少种非字母字符，这段逻辑依然稳健。

class Solution:
def vowelConsonantScore(self, s: str) -> int:
vowels_set = {'a', 'e', 'i', 'o', 'u'}
v = 0
c = 0
for ch in s:
# 只处理英文字母
if ch.isalpha():
if ch in vowels_set:
v += 1
else:
c += 1
# 按照题目要求的逻辑：c > 0 才计算，否则返回 0
return v // c if c > 0 else 0

复制代码

Myron2017

LC 1622. Fancy Sequence

构造费马小定理的证明，可以跳过，直接记忆上面的结论。

考察对“大数处理”的敏感度

在分布式系统或后端开发中，经常会遇到数值溢出的问题。

为什么要
1. modulo 10^9 + 7
复制代码
？
为什么不能直接
1. val / mult
复制代码
？

如果你直接用浮点数除法，在 $10^{18}$ 级别的运算中，精度丢失会让你求出来的结果差之毫厘、谬以千里。在模运算下使用逆元，是计算机处理大数除法时唯一保持 100% 精确的方法。

class Fancy:
def __init__(self):
      self.nums = []
      self.add = 0
      self.mult = 1
      self.mod = 10**9 + 7

def append(self, val: int) -> None:
      # 我们存入的是一个“抵消”了当前 add 和 mult 影响的原始值
      # 逆运算：(val - add) / mult
      # 在模运算下，除法变乘法逆元
      # 使用 pow(a, -1, mod) 是 Python 3.8+ 推荐的高效写法，内部实现是扩展欧几里得
      inv_mult = pow(self.mult, self.mod - 2, self.mod)
      self.nums.append(((val - self.add) * inv_mult) % self.mod)

def addAll(self, inc: int) -> None:
      self.add = (self.add + inc) % self.mod

def multAll(self, m: int) -> None:
      self.mult = (self.mult * m) % self.mod
      self.add = (self.add * m) % self.mod

def getIndex(self, idx: int) -> int:
      if idx >= len(self.nums):
         return -1
      # 取出时，应用当前的全局变换公式
      return (self.nums[idx] * self.mult + self.add) % self.mod

Myron2017

LC . 3870. Count Commas in Range

贡献法：不用去算每个区间到底有多少个数，而是算“第 1 个逗号”出现了多少次，“第 2 个逗号”出现了多少次。

class Solution:
def countCommas(self, n: int) -> int:
total_commas = 0
# start 是每个阶段产生更多逗号的起始点
# 1,000 (1个), 1,000,000 (2个), 1,000,000,000 (3个)...
start = 1000
while n >= start:
# 每一个大于等于 start 的数，都至少贡献了“一个额外的逗号”
# 比如 1,000,001 既大于 1,000，也大于 1,000,000
# 它在这两次判断中各贡献 1 个，加起来正好是 2 个逗号
total_commas += (n - start + 1)
start *= 1000
return total_commas

复制代码

class Solution:
def countCommas(self, n: int) -> int:
if n < 1000:
return 0
return n - 1000 + 1

复制代码

Myron2017

LC 3866. First Unique Even Element

核心算法模型：两次遍历法
第一次遍历：用哈希表（可以用 dict 或 collections.Counter）统计所有数字出现的次数。

第二次遍历：按顺序检查原数组中的每个元素，看它是否满足“偶数”且“计数为 1”。第一个满足的直接返回。

from collections import Counter
class Solution:
def firstUniqueEven(self, nums: list[int]) -> int:
# 1. 统计频率
freq = Counter(nums)
# 2. 直接遍历原数组 nums，保证“First”（索引最早）
for n in nums:
# 直接在字典里查频率，O(1) 速度极快
if n % 2 == 0 and freq[n] == 1:
return n
# 3. 遍历完没找到，说明不存在
return -1

复制代码

Myron2017

LC. 3803. Count Residue Prefixes

class Solution:
def residuePrefixes(self, s: str) -> int:
ans = 0
seen = set()
for i, char in enumerate(s):
# 增量更新 set
seen.add(char)
# 当前前缀的长度
length = i + 1
# 不同字符的个数
distinct_count = len(seen)
# 核心判断逻辑
if distinct_count == length % 3:
ans += 1
return ans

复制代码

Myron2017

LC. 3798. Largest Even Number

class Solution:
def largestEven(self, s: str) -> str:
n = len(s)
r = n - 1
while r >= 0:
if s[r] == '1':
r -= 1
else:
break
if r < 0: return ""
else:
return s[:r+1]

复制代码

更加 Python 的写法

class Solution:
def largestEven(self, s: str) -> str:
# rstrip('1') 会移除字符串右侧所有的 '1'
# 剩下的字符串末尾一定是 '2'（或者是空串）
return s.rstrip('1')

复制代码

s.rstrip('1')：从右边开始删，直到遇到不是 '1' 的字符为止。

如果删完后剩下了东西，最后一个字肯定是 '2'，满足偶数要求。

中间的 '1' 和 '2' 都会被保留，保证了长度最长，数值最大。

Myron2017

LC 3794. Reverse String Prefix

在 Python 切片 s[:n] 中，n 直接代表了你想取出的字符个数。
想取前 k 个，直接写 [:k]；想取前 5 个，直接写 [:5]。

class Solution:
def reversePrefix(self, s: str, k: int) -> str:
stack = []
for ch in s[:k]:
stack.append(ch)
ans = ""
for i in range(k):
ans += stack.pop()
if k == len(s): return ans
else:
return ans + s[k:]

复制代码

优化点 A：利用 Python 切片的翻转步长Python 的切片支持 [::-1]，这可以直接翻转一个序列。优化点 B：减少字符串拼接在 Python 中，字符串是不可变的。频繁地 ans += stack.pop() 会创建很多临时字符串对象。虽然这题 $n=100$ 没影响，但如果是 $n=10^6$，代码会慢得离谱。

class Solution:
def reversePrefix(self, s: str, k: int) -> str:
# s[:k][::-1] -> 取前 k 个并翻转
# s[k:] -> 取剩下的部分
return s[:k][::-1] + s[k:]

复制代码

为什么这更好？

切片翻转 [::-1]：由 Python 底层 C 语言实现，速度极快。

语义清晰：一眼就能看出是在翻转前 k 位。

不用判断 if k == len(s)：如果 k 等于长度，s[k:] 会自动返回空字符串 ""，拼接起来完全没问题。

Myron2017

LC .3783. Mirror Distance of an Integer

Python 直接 num 反转

reversed_n = int(str(n)[::-1])

class Solution:
def mirrorDistance(self, n: int) -> int:
# str(n)[::-1] 直接得到反转后的字符串
reversed_n = int(str(n)[::-1])
return abs(n - reversed_n)

复制代码

补充内容 (2026-03-16 11:36 +08:00):
class Solution:
def mirrorDistance(self, n: int) -> int:
      original_n = n
      reversed_n = 0
      temp = n

      while temp > 0:
         # 每次取出最后一位，加到 reversed_n 的末尾
         reversed_n = reversed_n * 10 + (temp % 10)
         temp //= 10

      return abs(original_n - reversed_n)

Myron2017

LC. 3774. Absolute Difference Between Maximum and Minimum K Elements

A. 排序法 (你的解法)思路：排序后取两头。复杂度：时间 $O(n \log n)$，空间 $O(1)$ 或 $O(n)$（取决于排序实现）。适用场景：$n$ 较小，或者需要多次查询不同 $k$ 值。B. 堆 (Heap) 法思路：维护一个大小为 $k$ 的大顶堆找最小 $k$ 个数，一个小顶堆找最大 $k$ 个数。复杂度：时间 $O(n \log k)$。适用场景：$n$ 非常大（如几百万），而 $k$ 很小（如前 10 名）。C. 快速选择 (Quick Select)思路：类似快排的分治思想，可以在不完全排序的情况下找到第 $k$ 小的数。复杂度：平均时间 $O(n)$。适用场景：极致的性能追求。

import heapq
class Solution:
def absDifference(self, nums: List[int], k: int) -> int:
# 直接获取最大的 k 个数和最小的 k 个数
max_k = heapq.nlargest(k, nums)
min_k = heapq.nsmallest(k, nums)
return sum(max_k) - sum(min_k)

复制代码

class Solution:
def absDifference(self, nums: List[int], k: int) -> int:
nums.sort() # 1. 升序排序
# 2. 前 k 个是最小的，后 k 个是最大的
return abs(sum(nums[:k]) - sum(nums[len(nums) - k:]))

复制代码

刷题记录帖子

浏览过的版块