刷题记录帖子

Myron2017

LC. 3894. Traffic Signal Color

简单题。

class Solution:
def trafficSignal(self, timer: int) -> str:
if timer == 0: return "Green"
elif timer == 30: return "Orange"
elif timer > 30 and timer <= 90: return "Red"
else:
return "Invalid"

复制代码

Myron2017

LC.3895. Count Digit Appearances

String Solution

class Solution:
def countDigitOccurrences(self, nums: list[int], digit: int) -> int:
d = str(digit)
ans = 0
for num in nums:
ans += str(num).count(d)
return ans

复制代码

No-String Solution

class Solution:
def countDigitOccurrences(self, nums: list[int], digit: int) -> int:
ans = 0
for num in nums:
# We use a while loop to check each digit from right to left
while num > 0:
# Check if the last digit matches the target digit
if num % 10 == digit:
ans += 1
# Remove the last digit
num //= 10
return ans

复制代码

Myron2017

LC. 3896. Minimum Operations to Transform Array into Alternating Prime

class Solution:
def minOperations(self, nums: list[int]) -> int:
# 1. 确定搜索范围：nums[i] 最大 10^5，需要稍微多预留一点空间找下一个素数
LIMIT = 100003 + 10 # 100003 是 10^5 之后第一个素数
is_prime = [True] * LIMIT
is_prime[0] = is_prime[1] = False
# 埃氏筛预处理
for p in range(2, int(LIMIT**0.5) + 1):
if is_prime[p]:
for i in range(p * p, LIMIT, p):
is_prime[i] = False
# 2. 收集所有素数，方便用二分法（或直接从 is_prime 查找）
primes = [i for i, val in enumerate(is_prime) if val]
import bisect
ans = 0
for idx, val in enumerate(nums):
if idx % 2 == 0:
# 偶数下标 -> 需要素数
if not is_prime[val]:
# 寻找第一个大于等于 val 的素数
# bisect_left 在有序列表中找到插入位置
pos = bisect.bisect_left(primes, val)
ans += (primes[pos] - val)
else:
# 奇数下标 -> 需要非素数
if is_prime[val]:
# 如果当前是素数，必须变大。最小的非素数变化通常是 +1
# 比如 2 变 4 (2->3也是素数), 3 变 4, 5 变 6
# 唯一需要注意的是，所有素数 +1 之后一定是非素数吗？
# 除了素数 2 变 3 还是素数外，其他素数都是奇数，+1 变偶数一定是合数。
# 所以：如果 val 是 2，变到下一个非素数是 4（步数 2）；
# 如果 val > 2，变到下一个非素数就是 val + 1（步数 1）。
if val == 2:
ans += 2
else:
ans += 1
return ans

复制代码

Myron2017

LC . 2515. Shortest Distance to Target String in a Circular Array

虽然是简单题，但是还是可以优化。

我做的预处理完全没有必要，当然当时做的时候没想到。还是要学习一个！

class Solution:
def closestTarget(self, words: List[str], target: str, startIndex: int) -> int:
w_index = defaultdict(list)
n = len(words)
for ind, val in enumerate(words):
w_index[val].append(ind)
if target not in w_index:
return -1
else:
ans = float('inf')
for i in w_index[target]:
d1 = abs(startIndex - i)
ans = min(ans, d1, n - d1)
return ans

复制代码

优化 code

class Solution:
def closestTarget(self, words: List[str], target: str, startIndex: int) -> int:
n = len(words)
res = n # 初始化为一个不可能达到的最大步数
for i in range(n):
if words[i] == target:
# 直接距离
dist = abs(i - startIndex)
# 比较：当前步数 vs 顺时针步数 vs 逆时针步数
# n - dist 即为绕一圈回来的另一种走法
res = min(res, dist, n - dist)
return res if res < n else -1

复制代码

Myron2017

LC 3663. Find The Least Frequent Digit

简单题，但是可以优化代码。

我的答案

class Solution:
def getLeastFrequentDigit(self, n: int) -> int:
freq = defaultdict(int)
for c in str(n):
freq[int(c)] += 1
f = []
for k, v in freq.items():
f.append(v)
ans = min(f)
key = sorted(freq.keys())
for k in key:
if freq[k] == ans:
return k

复制代码

可以用 Counter 统计频率。
先找了最小频率 ans，又排序了 keys，再循环找结果。其实可以在一次遍历或排序中搞定。

优化代码

class Solution:
def getLeastFrequentDigit(self, n: int) -> int:
# 1. 统计频率：Counter 会帮你把 '1553322' 变成 {'5':2, '3':2, '2':2, '1':1}
freq = Counter(str(n))
# 2. 找到最小的出现次数
min_freq = min(freq.values())
# 3. 找出所有满足最小次数的数字，转成 int 以便排序
candidates = [int(digit) for digit, count in freq.items() if count == min_freq]
# 4. 返回其中最小的数字
return min(candidates)

复制代码

也可以利用元组排序

class Solution:
def getLeastFrequentDigit(self, n: int) -> int:
from collections import Counter
counts = Counter(str(n))
# 我们把字典项转成 (频率, 数字) 的列表
# 注意：这里数字要转成 int，否则 '10' 会排在 '2' 前面（字符串排序 vs 数字排序）
items = []
for digit, freq in counts.items():
items.append((freq, int(digit)))
# 默认升序：先按频率升序，频率相同按数字升序
# 排序后的第一个元素就是我们要的
items.sort()
return items[0][1]

复制代码

Myron2017

3662. Filter Characters by Frequency
Solved
Easy
Topics
Hint
You are given a string s consisting of lowercase English letters and an integer k.

Your task is to construct a new string that contains only those characters from s which appear fewer than k times in the entire string. The order of characters in the new string must be the same as their order in s.

Return the resulting string. If no characters qualify, return an empty string.

Note: Every occurrence of a character that occurs fewer than k times is kept.

Example 1:

Input: s = "aadbbcccca", k = 3

Output: "dbb"

Explanation:

Character frequencies in s:

'a' appears 3 times
'd' appears 1 time
'b' appears 2 times
'c' appears 4 times
Only 'd' and 'b' appear fewer than 3 times. Preserving their order, the result is "dbb".

Example 2:

Input: s = "xyz", k = 2

Output: "xyz"

Explanation:

All characters ('x', 'y', 'z') appear exactly once, which is fewer than 2. Thus the whole string is returned.

Constraints:

1 <= s.length <= 100
s consists of lowercase English letters.
1 <= k <= s.length

from collections import Counter
class Solution:
def filterCharacters(self, s: str, k: int) -> str:
# 第一遍：统计频率
freq = Counter(s)
ans = []
# 第二遍：根据频率过滤，同时利用 list 维持顺序
for ch in s:
if freq[ch] < k:
ans.append(ch)
# 最后合并成字符串，比 += 字符串性能更好
return "".join(ans)

复制代码

Myron2017

LC 3488. Closest Equal Element Queries

这道题（LC 3488）虽然被标记为 Medium，但它是理解搜索空间压缩和环形结构建模的绝佳案例。通过这道题，你可以沉淀以下四个核心维度的知识：1. 搜索空间的“极度压缩”这是本题最高级的直觉：在有序集合中，最近的元素一定是相邻的。启发：当题目要求寻找“最近”、“最小差值”时，如果能把候选索引提取出来并排序，你的搜索范围就从“整个数组”缩减到了“左右邻居”。通用模型：以后遇到“找同类中最近的”，第一反应应该是：哈希表存下标列表 + 二分查找邻居。2. 环形数组（Circular Array）的两种处理套路环形数组是面试常客，这道题涵盖了环形结构的两个层面：物理层面的环（索引）：如何在列表首尾实现“无缝对接”？技巧：使用取模运算 % m。它能优雅地把 0 的左边变成 m-1，把 m-1 的右边变成 0。这比写一堆 if-else 判断边界要专业得多。逻辑层面的环（距离）：两个点 $i$ 和 $j$ 在长度为 $n$ 的环上的距离。公式： $dist = \min(|i - j|, n - |i - j|)$。理解：一个是“直接走”的距离，一个是“绕一圈”的距离。3. 从 $O(\log N)$ 到 $O(1)$ 的优化思维在解决这道题的过程中，我们经历了三种复杂度的演进：暴力解法 $O(Q \times N)$：遍历所有相同数字。二分优化 $O(Q \log N)$：利用 bisect 在有序下标中定位。完全预处理 $O(Q)$：通过一个 idx_to_pos 数组提前存好每个索引在 v_list 里的位置。收获：只要查询次数 $Q$ 足够大，任何能通过空间换时间省掉的 $\log N$ 都是值得的。在面试中，主动提出从 $O(\log N)$ 优化到 $O(1)$ 会非常加分。4. 易错点与防御性编程索引 vs 元素：你在之前的 debug 中犯的错误（用 pos 减 q）非常典型。要时刻提醒自己：我现在操作的是“列表的索引”还是“原数组的索引”？特例处理：这种找“另一个”元素的问题，必须优先检查 len(v_list) == 1 的情况，避免死循环或无效计算。

raw code

class Solution:
def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
valIndDict = defaultdict(list)
for ind, val in enumerate(nums):
valIndDict[val].append(ind)
ans = []
n = len(nums)
for q in queries:
v = nums[q]
if len(valIndDict[v]) == 1:
ans.append(-1)
else:
# has multiple v
v_list = valIndDict[v]
pos = bisect.bisect_left(v_list, q)
m = len(v_list)
minD = float('inf')
for k in [ v_list[(pos+1)%m], v_list[(pos-1)%m] ]:
minD = min(minD, abs(k - q), n - abs(k-q))
ans.append(minD)
return ans

复制代码

优化后代码

from collections import defaultdict
import bisect
from typing import List
class Solution:
def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
n = len(nums)
# 1. 预处理：记录每个值对应的所有下标
val_to_indices = defaultdict(list)
# 2. 预处理：记录每个原数组下标 i 在它对应的 indices 列表里的位置（排名）
idx_to_pos = [0] * n
for i, v in enumerate(nums):
idx_to_pos[i] = len(val_to_indices[v])
val_to_indices[v].append(i)
ans = []
for q in queries:
v = nums[q]
v_list = val_to_indices[v]
m = len(v_list)
if m == 1:
ans.append(-1)
continue
# 直接通过预处理的数组拿到排名，省去 bisect_left 的 O(log N)
pos = idx_to_pos[q]
# 只检查左右邻居（含环形首尾）
res = float('inf')
# 这里的 k 是 v_list 里的元素，即原数组的下标
for k in [v_list[(pos - 1) % m], v_list[(pos + 1) % m]]:
diff = abs(k - q)
# 环形距离公式
dist = min(diff, n - diff)
if dist < res:
res = dist
ans.append(res)
return ans

复制代码

Myron2017

LC. 3658. GCD of Odd and Even Sums

简单题，但是考察了辗转相除法，不搜索下我也忘记了。。。

还是要提高自己的知识水平！

class Solution:
def gcdOfOddEvenSums(self, n: int) -> int:
sumOdd, sumEven = n * n, (n+1) * n
def GCD(a, b):
if b > a: a, b = b, a
r = a % b
if r == 0: return b
else:
return GCD(b, r)
return GCD(sumOdd, sumEven)

复制代码

Myron2017

LC 3761. Minimum Absolute Distance Between Mirror Pairs

虽然过了但是还是有很多可以优化的地方。

class Solution:
def minMirrorPairDistance(self, nums: List[int]) -> int:
n = len(nums)
val_ind_dict = defaultdict(list)
for ind,val in enumerate(nums):
val_ind_dict[val].append(ind)
ans = float('inf')
for ind,num in enumerate(nums):
s_num = str(num)
start = len(s_num) - 1
while s_num[start] == '0':
start -= 1
reversed_s_num = s_num[start::-1]
if int(reversed_s_num) in val_ind_dict:
pos = bisect.bisect_left(val_ind_dict[int(reversed_s_num)], ind)
m = len(val_ind_dict[int(reversed_s_num)])
pos_list = [pos+1, pos-1, pos]
for p in pos_list:
if p >= 0 and p < m and val_ind_dict[int(reversed_s_num)][p] > ind:
print(val_ind_dict[int(reversed_s_num)][p])
ans = min(ans, abs(val_ind_dict[int(reversed_s_num)][p]-ind))
if ans == float('inf'):
return -1
else:
return ans

复制代码

做的时候，我已经发现了 i < j 了，其实这个就带来了单调性。但是当时没有深入思考，其实这就是说明，你如果让 i 从右向左走，只需要考虑右边的已经看到的最近的 reversed 之后数的 index 就行了，我这个是考虑没有 i < j 的方案。

一次遍历：时间复杂度由 $O(N \log N)$ 降到了 $O(N)$（假设整数长度固定，字符串转换是常数级）。空间优化：last_seen 只存一个整数下标，而不是下标列表，空间更省。面试加分：利用“逆向遍历”解决“寻找右侧最近”的问题，是非常经典的面试套路，展示了你对数组题目深厚的理解。

class Solution:
def minMirrorPairDistance(self, nums: List[int]) -> int:
# last_seen 记录数字 x 在当前位置右侧“最近”出现的下标
last_seen = {}
min_dist = float('inf')
n = len(nums)
# 从右往左遍历，这样当我们遇到 nums[i] 时，
# last_seen 里存的都是 i 之后的下标 j
for i in range(n - 1, -1, -1):
num = nums[i]
# 1. 核心逻辑：计算当前数字反转后的目标值
# int(str(num)[::-1]) 会自动处理 120 -> "021" -> 21 的逻辑
target = int(str(num)[::-1])
# 2. 如果目标值在右边出现过，更新最小距离
if target in last_seen:
dist = last_seen[target] - i
if dist < min_dist:
min_dist = dist
# 3. 记录/更新当前数字出现的位置
# 因为是从右往左，这里记录的是该数字目前为止最靠左（离左边最近）的位置
last_seen[num] = i
return min_dist if min_dist != float('inf') else -1

复制代码

当然有个小语法的地方也要注意，如何在 Python 中翻转字符串。

Myron2017

LC 3633. Earliest Finish Time for Land and Water Rides I

简单题，但是还是可以优化。

我的解法，暴力 loop

class Solution:
def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
ans = float('inf')
for ls, ld in zip(landStartTime, landDuration):
for ws, wd in zip(waterStartTime, waterDuration):
if ws <= (ls+ld):
ans = min(ans, ls+ld+wd)
else:
ans = min(ans, ws+wd)
for ws, wd in zip(waterStartTime, waterDuration):
for ls, ld in zip(landStartTime, landDuration):
if ls <= (ws+wd):
ans = min(ans, ws+wd+ld)
else:
ans = min(ans, ls+ld)
return ans

复制代码

但是，其实不用可以贪心，无论陆地还是水面，你都挑选最早结束那个项目作为第一个项目一定是不亏的。
然后剩下就是 best-land 和 best-water 对后面分别接 water 还是 land 循环。

复杂度一下子从 O(N x M). == > O(N + M)

from typing import List
class Solution:
def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
# 1. 预处理：找到最早结束的陆地项目和最早结束的水上项目
# 因为无论你选哪个作为第一项，结束时间越早，对第二项越有利。
best_land_end = min(s + d for s, d in zip(landStartTime, landDuration))
best_water_end = min(s + d for s, d in zip(waterStartTime, waterDuration))
ans = float('inf')
# 2. 情况一：先陆后水
# 我们已经知道陆地最快在 best_land_end 结束
# 那么对于所有的水上项目，我们选一个能让我们最快结束的
for ws, wd in zip(waterStartTime, waterDuration):
# 结束时间 = max(第一项结束时间, 第二项开始时间) + 第二项持续时间
finish_time = max(best_land_end, ws) + wd
if finish_time < ans:
ans = finish_time
# 3. 情况二：先水后陆
for ls, ld in zip(landStartTime, landDuration):
finish_time = max(best_water_end, ls) + ld
if finish_time < ans:
ans = finish_time
return ans

复制代码

刷题记录帖子

浏览过的版块