刷题记录帖子

Myron2017

本帖最后由 Myron2017 于 2026-2-5 10:32 编辑

LC 2789. Largest Element in an Array after Merge Operations

仔细读题，理解题干。

这个所谓的合并，归根到底就是如果右比左大，就向右合并。

为什么需要最后的更新？ pythonmax_val = max(max_val, current)

两个原因：

循环可能一次都不进入 else

所有元素都能合并
max_val 从未更新，还是初始值
最后的累积可能是最大值

即使进入过 else
最后一段累积可能更大
记忆技巧
循环内更新 → 遇到障碍时记录循环外更新 → 最后的成果也要记录

两次检查，确保万无一失！

class Solution:
def maxArrayValue(self, nums: List[int]) -> int:
"""
从右往左贪心合并
核心思想：
- 右边的元素作为"吸收者"
- 左边的元素如果 ≤ 累积和，就被吸收
- 遇到无法吸收的元素，重新开始累积
"""
n = len(nums)
# 从最右边开始
current = nums[-1] # 当前累积和（右边的"吸收池"）
max_val = current # 记录最大值
# 从右往左遍历
for i in range(n - 2, -1, -1):
if nums[i] <= current:
# 可以合并：nums[i] 被吸收
current += nums[i]
else:
# 不能合并：nums[i] 太大，无法被吸收
# 更新最大值，nums[i] 成为新的起点
max_val = max(max_val, current)
current = nums[i]
# 别忘了最后的累积和

复制代码

Myron2017

LC 110. Balanced Binary Tree

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

平衡条件：
左子树平衡
右子树平衡
左右子树差值不超过 1

class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
# 返回值含义：
# >= 0 : 当前子树的高度
# -1 : 当前子树已经不平衡（提前终止）
def height(node):
# 空节点高度为 0，是平衡的
if not node:
return 0
# 递归计算左子树高度
left = height(node.left)
# 如果左子树已经不平衡，直接向上返回 -1
# 不再继续计算（剪枝，避免无意义计算）
if left == -1:
return -1
# 递归计算右子树高度
right = height(node.right)
# 如果右子树已经不平衡，直接向上返回 -1
if right == -1:
return -1
# 当前节点的平衡性判断：
# 左右子树高度差 > 1，则整棵子树不平衡
if abs(left - right) > 1:
return -1
# 当前节点是平衡的
# 返回当前子树高度 = max(左, 右) + 1
return max(left, right) + 1
# 如果整棵树返回的不是 -1，说明是平衡二叉树
return height(root) != -1

复制代码

Myron2017

LC 692. Top K Frequent Words

先统计每个单词 Freq
然后把单词压入堆栈

class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
# 1️⃣ 统计每个单词出现的频率
# Counter 返回一个 dict: {单词: 出现次数}
count = Counter(words)
# 2️⃣ 构建一个 heap（优先队列）
# heap 元素格式：(-频率, 单词)
# 频率取负号，是为了让 Python 的最小堆行为变成“最大堆”，
# 这样出现次数多的单词会排在堆顶
heap = [(-freq, word) for word, freq in count.items()]
heapq.heapify(heap) # 原地将列表 heap 转化为堆
# 3️⃣ 从堆中依次取出 k 个最频繁的单词
ans = []
while len(ans) < k:
# heappop 弹出堆顶元素
# 因为我们存的是 (-频率, 单词)，堆顶就是当前出现次数最多的单词
# [1] 取单词部分
ans.append(heapq.heappop(heap)[1])
# 4️⃣ 返回最终结果列表
return ans

复制代码

Myron2017

735. Asteroid Collision

这道题目之前面试见过，结果今天我还是不会，大方向对了，但是细节还是需要自己理清。
说实话，写 code 的时候，可以积极加上注释，注释反而会帮助你理清思路和要点。

核心思路

用栈模拟：

栈顶保存最近向右的行星

遇到向左行星才可能发生碰撞

栈顶比当前小 → 栈顶爆炸 → 当前行星继续碰撞

栈顶比当前大 → 当前行星爆炸 → break

栈顶相等 → 两颗爆炸 → break

栈空或没有碰撞 → 当前行星存活 → 入栈

class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
for a in asteroids:
# 当前行星可能爆炸
while stack and stack[-1] > 0 and a < 0:
if stack[-1] < -a:
# 栈顶行星比当前小 → 栈顶爆炸，继续比较下一颗
stack.pop()
continue
elif stack[-1] == -a:
# 栈顶与当前相等 → 两颗都爆炸
stack.pop()
# 当前行星爆炸或者两颗相等 → 不入栈，退出循环
break
else:
# 栈为空或者栈顶不是向右行星 → 当前行星存活，入栈
stack.append(a)
return stack

复制代码

Myron2017

LC 1648. Sell Diminishing-Valued Colored Balls

不能一个个求解，利用库存格，整块，整层求解。

class Solution:
def maxProfit(self, inventory: List[int], orders: int) -> int:
MOD = 10**9 + 7
# 1. 降序排序库存，方便每次卖最大的球
inventory.sort(reverse=True)
inventory.append(0) # 哨兵，方便处理最后一批球
ans = 0
n = len(inventory)
for i in range(len(inventory) - 1):
# 当前库存值
cur_val = inventory[i]
# 下一个库存值
next_val = inventory[i+1]
# 当前层以上（包括自己）所有大于下一层的库存格都参与卖球
width = i + 1 # i+1库存格可以同时卖
# 当前库存层可以卖多少球
cnt = width * (cur_val - next_val)
if orders >= cnt:
# 可以一次卖掉这一层的全部球
# 求连续整数和公式：sum = (cur_val + next_val + 1) * (cur_val - next_val) // 2
total = width * (cur_val + next_val + 1) * (cur_val - next_val) // 2
ans = (ans + total) % MOD
orders -= cnt
else:
# 卖不完整层，卖 orders 个球
full_rows = orders // width # 完整递减行
remainder = orders % width # 剩下的零散球
# 卖完整行的球
total = width * (cur_val + cur_val - full_rows + 1) * full_rows // 2
ans = (ans + total) % MOD
# 卖剩下的零散球，每颗价值 = cur_val - full_rows
ans = (ans + remainder * (cur_val - full_rows)) % MOD
return ans # 所有订单卖完，直接返回
return ans

复制代码

TLE 解法注意

"""
TLE
if len(inventory) == 1:
ans = ((inventory[0] - orders + 1) + inventory[0]) * orders // 2
return ans % (10**9+7)
#inventory = ordered(inventory, reverse=True)
k = 0
ans = 0
heap = [-i for i in inventory]
heapq.heapify(heap)
while k < orders:
curr = heapq.heappop(heap)
k += 1
ans += -curr
ans %= (10**9+7)
heapq.heappush(heap, curr + 1)
return ans
"""

复制代码

Myron2017

LC 567. Permutation in String

字典指纹比对法

class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
freq_s1 = Counter(s1)
n1 = len(s1)
for i in range(len(s2)-n1+1):
#print(i)
freq_curr = Counter(s2[i:i+n1])
#print(freq_curr, freq_s1)
if freq_curr == freq_s1: return True
return False

复制代码

滑动窗口比对法

class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
s2_len, s1_len = len(s2), len(s1)
if s1_len > s2_len:
return False
s1_char_freq_arr = [0] * 26
s2_window_char_freq_arr = [0] * 26
for index in range(s1_len):
s1_char_freq_arr[ord(s1[index]) - ord('a')] += 1
s2_window_char_freq_arr[ord(s2[index]) - ord('a')] += 1
if s1_char_freq_arr == s2_window_char_freq_arr:
return True
for index in range(s2_len - s1_len):
s2_window_char_freq_arr[ord(s2[index]) - ord('a')] -= 1
s2_window_char_freq_arr[ord(s2[index + s1_len]) - ord('a')] += 1
if s1_char_freq_arr == s2_window_char_freq_arr:
return True
return False

复制代码

Myron2017

LC 438. Find All Anagrams in a String

类似上面解法 HashMap 做字符串指纹

class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
freq = Counter(p)
n_s = len(s)
n_p = len(p)
ans = []
for i in range(n_s - n_p + 1):
curr_freq = Counter(s[i:i+n_p])
if curr_freq == freq: ans.append(i)
return ans

复制代码

Myron2017

LC 1027. Longest Arithmetic Subsequence

LC 1027. 最长等差数列总结1. 核心模型：动态规划 (DP)状态定义： dp[i][diff] 表示以 nums[i] 结尾、公差为 diff 的最长等差子序列的长度。转移方程： dp[i][diff] = dp[j][diff] + 1 （其中 $j < i, diff = nums[i] - nums[j]$）。初始化：所有可能的序列长度至少为 $2$（两个数即可成数列）。2. 实现技巧容器选择：字典版： dp = [{} for _ in range(n)]。代码简洁，自动处理负数 diff。数组版： dp = [[1] * 1001 for _ in range(n)]。性能更高，需加 OFFSET = 500 防止索引越界。复杂度：时间：$O(n^2)$空间：$O(n \cdot \text{Range})$，其中 $\text{Range}$ 是公差的取值范围。3. 易错点 & 坑子序列不连续：记得这不是子数组，必须遍历 $i$ 之前所有的 $j$，而不是只看 $i-1$。公差正负：等差数列可以递增（$diff > 0$）、递减（$diff < 0$）或全等（$diff = 0$）。最值更新：在转移过程中实时维护一个 max_length。4. 复习口诀定结尾，定公差；双层循环 $i$ 找 $j$；查旧表，加一数；数组记得加 Offset。这一类“最长子序列”问题通常都要定义“以 $i$ 结尾”来破局。需要我为你推荐一道类似的题目（比如 LC 300 最长递增子序列）来巩固这个思维吗？

class Solution:
def longestArithSeqLength(self, nums: list[int]) -> int:
n = len(nums)
if n <= 2:
return n
# dp[i] 是一个字典，key 是公差 diff，value 是该公差下的最长长度
dp = [{} for _ in range(n)]
max_length = 0
# 遍历数组中的每一个数作为当前的结尾
for i in range(n):
# 遍历 i 之前的所有数，寻找可以接上的前序节点
for j in range(i):
diff = nums[i] - nums[j]
# 如果 j 处已经存在公差为 diff 的序列，则长度 +1
# 否则，nums[j] 和 nums[i] 构成一个长度为 2 的新序列
# dict.get(key, default) 是面试中常用的简洁写法
dp[i][diff] = dp[j].get(diff, 1) + 1
# 记录全局最大值
if dp[i][diff] > max_length:
max_length = dp[i][diff]
return max_length

复制代码

Myron2017

本帖最后由 Myron2017 于 2026-2-5 17:27 编辑

LC 300. Longest Increasing Subsequence

类似上一题，

这一类“最长子序列”问题通常都要定义“以 i 结尾”来破局。
程序员视角下的“解题直觉”
看到子序列 ===> 优先想 DP。
看到子数组 ===> 优先想滑动窗口、双指针或贪心。

class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# dp[i] longest increasing subsequence ending with i
# if nums[i] > nums[j]: dp[i] = max(dp[j] + 1, dp[i])
n = len(nums)
dp = [1] * n
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[j]+1, dp[i])
return max(dp)

复制代码

Myron2017

LC 424. Longest Repeating Character Replacement

这道题可以总结为以下几句“通关口诀”，帮你快速在大脑中建立索引：核心逻辑：窗口的本质是 “众数 + 替换额度”。窗口长度减去出现次数最多的字符频率，就是你需要替换的次数。滑动策略：窗口采用 “只扩不缩” 的贪心策略。合法时，右指针右移扩大窗口；非法时，左右指针同步右移，维持当前最大窗口进行平移。性能关键：不需要实时寻找当前窗口的绝对众数，只需维护一个 “历史最高频次” (max_freq)。因为只有出现更高频次的字符，才可能突破当前记录，产生更长的结果。一句话概括：用滑动窗口框住一个区间，只要“非众数”的个数不超过 k，窗口就可以继续野蛮生长。

from collections import defaultdict
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
freq_w = defaultdict(int)
l, r = 0, 0
max_len = 0
# 优化点：维护一个变量记录历史窗口中的最高频次
# 这样就不需要每次都去遍历字典找最大值了
max_freq_ch = 0
while r < len(s):
# 1. 进窗：先把右边的字符加入统计
freq_w[s[r]] += 1
# 实时更新最高频次 (O(1) 时间复杂度)
max_freq_ch = max(max_freq_ch, freq_w[s[r]])
# 计算当前窗口状态
len_w = r - l + 1
changes = len_w - max_freq_ch
# 2. 分情况讨论
if changes <= k:
# 情况A：替换 k 次以内能搞定 -> 窗口合法
# 策略：更新结果，并尝试扩大窗口 (只动 r)
max_len = max(max_len, len_w)
r += 1
else:
# 情况B：替换 k 次也不够 -> 窗口非法
# 策略：窗口整体平移 (l 和 r 都动)
# 既然是平移，左边出去一个，右边进来一个（右边进来的逻辑在下一轮循环开头）
freq_w[s[l]] -= 1 # 左边移出，计数减一
l += 1 # 左指针右移
r += 1 # 右指针右移,不用统计，在while开头统计
return max_len

复制代码

刷题记录帖子

浏览过的版块