刷题记录帖子

LC. 2126. Destroying Asteroids

You are given an integer mass, which represents the original mass of a planet. You are further given an integer array asteroids, where asteroids[i] is the mass of the ith asteroid.

You can arrange for the planet to collide with the asteroids in any arbitrary order. If the mass of the planet is greater than or equal to the mass of the asteroid, the asteroid is destroyed and the planet gains the mass of the asteroid. Otherwise, the planet is destroyed.

Return true if all asteroids can be destroyed. Otherwise, return false.



Example 1:

Input: mass = 10, asteroids = [3,9,19,5,21]
Output: true
Explanation: One way to order the asteroids is [9,19,5,3,21]:
- The planet collides with the asteroid with a mass of 9. New planet mass: 10 + 9 = 19
- The planet collides with the asteroid with a mass of 19. New planet mass: 19 + 19 = 38
- The planet collides with the asteroid with a mass of 5. New planet mass: 38 + 5 = 43
- The planet collides with the asteroid with a mass of 3. New planet mass: 43 + 3 = 46
- The planet collides with the asteroid with a mass of 21. New planet mass: 46 + 21 = 67
All asteroids are destroyed.
Example 2:

Input: mass = 5, asteroids = [4,9,23,4]
Output: false
Explanation:
The planet cannot ever gain enough mass to destroy the asteroid with a mass of 23.
After the planet destroys the other asteroids, it will have a mass of 5 + 4 + 9 + 4 = 22.
This is less than 23, so a collision would not destroy the last asteroid.


Constraints:

1 <= mass <= 105
1 <= asteroids.length <= 105
1 <= asteroids[i] <= 105

1. class Solution:
   
2.     def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
   
3.         asteroids.sort()
   
4.         curr = mass
   
5. 
   
6.         for a in asteroids:
   
7.             if curr >= a:
   
8.                 curr += a
   
9.             else:
   
10.                 return False
    
11. 
    
12.         return True

复制代码

LC. 2144. Minimum Cost of Buying Candies With Discount

简单题，贪心策略求解。

1. class Solution:
   
2.     def minimumCost(self, cost: List[int]) -> int:
   
3.         # sort costs
   
4.         # from right to left buying first and second to the right
   
5.         #     get the third to the right for free
   
6.         cost.sort()
   
7. 
   
8.         ans = 0
   
9.         group_by_3 = 0
   
10. 
    
11.         for i in range(len(cost)-1, -1, -1):
    
12.             if group_by_3 < 2:
    
13.                 ans += cost[i]
    
14.                 group_by_3 += 1
    
15.             elif group_by_3 == 2:
    
16.                 group_by_3 = 0
    
17.         
    
18.         return ans
    
19. 
    
20.         

复制代码

当然非要说改进下我的写法，其实 group_by_3 这个计数器并不需要，直接模 3 就行。

1. class Solution:
   
2.     def minimumCost(self, cost: list[int]) -> int:
   
3.         # 降序排序，最贵的在前面
   
4.         cost.sort(reverse=True)
   
5.         ans = 0
   
6.         
   
7.         # 遍历所有糖果
   
8.         for i in range(len(cost)):
   
9.             # 索引为 0, 1 的掏钱，索引为 2 的免单 (i % 3 == 2)
   
10.             # 索引为 3, 4 的掏钱，索引为 5 的免单...
    
11.             if i % 3 != 2:
    
12.                 ans += cost[i]
    
13.                
    
14.         return ans

复制代码

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

我是暴力求解，N x M.

分两种情况讨论（先陆地再水上，或者先水上再陆地），同时处理“到达时项目还没开”与“到达时项目已经开了”的时间重叠问题。

1. class Solution:
   
2.     def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
   
3.         ans = float('inf')
   
4. 
   
5.         for ls, ld in zip(landStartTime, landDuration):
   
6.             for ws, wd in zip(waterStartTime, waterDuration):
   
7.                 if ws <= (ls+ld):
   
8.                     ans = min(ans, ls+ld+wd)
   
9.                 else:
   
10.                     ans = min(ans, ws+wd)
    
11. 
    
12.         for ws, wd in zip(waterStartTime, waterDuration):
    
13.             for ls, ld in zip(landStartTime, landDuration):
    
14.                 if ls <= (ws+wd):
    
15.                     ans = min(ans, ws+wd+ld)
    
16.                 else:
    
17.                     ans = min(ans, ls+ld)
    
18. 
    
19. 
    
20.         return ans
    

复制代码

但是其实，不需要外面的那个循环，换句话说可以 N + M 而不是相乘。

假设先玩项目 A 再玩项目 B：项目 A 的最早结束时间 = A_start + A_duration项目 B 的游玩总结束时间 = max(项目 A 的结束时间, B_start) + B_duration你的代码其实就是在穷举所有的 (i, j) 组合来套用这个公式。

1. from typing import List
   
2. 
   
3. class Solution:
   
4.     def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
   
5.         # 1. 预计算单项项目的全局最早结束时间 —— O(n) 和 O(m)
   
6.         min_land_end = min(s + d for s, d in zip(landStartTime, landDuration))
   
7.         min_water_end = min(s + d for s, d in zip(waterStartTime, waterDuration))
   
8.         
   
9.         ans = float('inf')
   
10.         
    
11.         # 2. 情况一：先陆地，后水上 —— O(m)
    
12.         # 陆地直接派代表 min_land_end 出战即可
    
13.         for ws, wd in zip(waterStartTime, waterDuration):
    
14.             current_finish = max(min_land_end, ws) + wd
    
15.             if current_finish < ans:
    
16.                 ans = current_finish
    
17.                
    
18.         # 3. 情况二：先水上，后陆地 —— O(n)
    
19.         # 水上直接派代表 min_water_end 出战即可
    
20.         for ls, ld in zip(landStartTime, landDuration):
    
21.             current_finish = max(min_water_end, ls) + ld
    
22.             if current_finish < ans:
    
23.                 ans = current_finish
    
24.                
    
25.         return ans

复制代码

补充内容 (2026-06-03 10:23 +08:00):
改进方法可以做 LC. 3635. Earliest Finish Time for Land and Water Rides II

这个进阶就是把数据规模扩大到 10^4 所以必须用 N + M。

LC. 3751. Total Waviness of Numbers in Range I

暴力枚举（Brute Force），时间复杂度是 $O(N \cdot L)$，其中 $N$ 是区间内数字的个数（最大 $10^5$），$L$ 是数字的最大长度（最大 6）。总操作次数在 $6 \times 10^5$ 级别，对于 Python 来说只需零点几秒，非常稳。

1. class Solution:
   
2.     def totalWaviness(self, num1: int, num2: int) -> int:
   
3.         def findPeakValleysInNum(num):
   
4.             num = str(num)
   
5.             if len(num) < 3:
   
6.                 return 0
   
7.             else:
   
8.                 ans = 0
   
9.                 for i in range(1, len(num)-1):
   
10.                     if num[i] > num[i-1] and num[i] > num[i+1]:
    
11.                         ans += 1
    
12.                     if num[i] < num[i-1] and num[i] < num[i+1]:
    
13.                         ans += 1
    
14.                 return ans
    
15. 
    
16.         
    
17.         ans = 0
    
18.         for num in range(num1, num2+1):
    
19.             ans += findPeakValleysInNum(num)
    
20.         return ans

复制代码

优化

1. class Solution:
   
2.     def totalWaviness(self, num1: int, num2: int) -> int:
   
3.         ans = 0
   
4.         for num in range(num1, num2 + 1):
   
5.             s = str(num)
   
6.             # Python 的字符串支持直接迭代和索引，且长度小于 3 时，range(1, 0) 为空，自动跳过循环
   
7.             for i in range(1, len(s) - 1):
   
8.                 # 将判断合并，减少不必要的 if 分支跳转
   
9.                 if (s[i] > s[i-1] and s[i] > s[i+1]) or (s[i] < s[i-1] and s[i] < s[i+1]):
   
10.                     ans += 1
    
11.         return ans

复制代码

更进一步

数位 DP（Digit DP）

遇到求区间 [L, R] 内满足某种规则的数字个数或属性和，且数据范围极大时，我们需要使用 数位 DP（Digit DP）。

简单题，但是还是可以提高的，主要是学习下如何把所有计算放在一个 Loop 里面。

我的解法

1. class Solution:
   
2.     def leftRightDifference(self, nums: List[int]) -> List[int]:
   
3.         allSum = sum(nums)
   
4.         
   
5.         ans = []
   
6.         left = 0
   
7.         right = allSum - nums[0]
   
8.         ans.append(abs(right - left))
   
9. 
   
10.         for i in range(1, len(nums)):
    
11.             left += nums[i-1]
    
12.             right -= nums[i]
    
13.             ans.append(abs(left - right))
    
14. 
    
15.         return ans

复制代码

当时，其实只要变化下更新 left，right 的时间就可以把 index = 0 统一进 Loop 处理。

1. class Solution:
   
2.     def leftRightDifference(self, nums: List[int]) -> List[int]:
   
3.         left = 0
   
4.         right = sum(nums)  # 初始时，假设当前位置在数组最左侧的外面，右侧和就是整个数组的和
   
5.         ans = []
   
6. 
   
7.         for num in nums:
   
8.             # 1. 当指针指向 num 时，num 属于当前位置，不再属于"右侧"
   
9.             right -= num
   
10.             
    
11.             # 2. 计算当前位置左右两侧的差值绝对值
    
12.             ans.append(abs(left - right))
    
13.             
    
14.             # 3. 离开当前位置前，将 num 划入"左侧"，为下一个元素做准备
    
15.             left += num
    
16. 
    
17.         return ans

复制代码

3950. Exactly One Consecutive Set Bits Pair

这个是必须有两个 11 在 binary 表达式里面，而且不能有多于两个 11 的连续 1.

1. class Solution:
   
2.     def consecutiveSetBits(self, n: int) -> bool:
   
3.         binN = bin(n)
   
4. 
   
5.         return (binN.count('11') == 1 and not '111' in binN)

复制代码

或者考察 bit 运算

1. class Solution:
   
2.     def consecutiveSetBits(self, n: int) -> bool:
   
3.         # 1. 提取出所有相邻的 11 对。
   
4.         # 如果 n 的二进制中有连续的 11，那么 x 对应的位置就会是 1
   
5.         x = n & (n >> 1)
   
6.         
   
7.         # 2. 判断 x 中是否刚好只有一个 1
   
8.         # (x & (x - 1)) == 0 是抹去最低位 1 的神仙操作
   
9.         return x > 0 and (x & (x - 1)) == 0

复制代码

x & (x - 1) 的核心物理意义就是：无条件抹去二进制中最右边的那个 1。

如果是 2 的幂： 比如 2 (10), 4 (100), 8 (1000)。它们在二进制下的特征是全身上下只有唯一的一个 1。当你用 x & (x - 1) 抹掉这唯一的 1 后，它自然就彻底变成了 0。

如果不是 2 的幂： 比如你举例的 7 (111)。它身上有多个 1。当你抹掉最右边的一个 1 后，左边还会剩下其他的 1（变成了 110），结果当然就不会等于 0 啦。

1. 抹除最低位的 1：x & (x - 1)这是位运算里出场率最高的神技。核心逻辑： 任何一个数 x，当你把它减去 1 时，它的二进制表示中，最低位的 1 会变成 0，而它右边的所有 0 都会变成 1。举个例子： x = 6 (二进制 110)x - 1 = 5 (二进制 101)x & (x - 1) = 110 & 101 = 100 (也就是 4)你看，原来 110 最右边的那个 1 被抹掉了。经典应用场景：LC 191. 位 1 的个数： 怎么数一个数有几个 1？每次执行 x = x & (x - 1)，执行了几次 x 变成 0，就有几个 1。LC 231. 2 的幂： 2 的幂的特征是二进制只有一个 1。所以 x > 0 and (x & (x - 1)) == 0 就能一步判定。2. 提取最低位的 1 (lowbit)：x & -x这个技巧是高级数据结构“树状数组 (Fenwick Tree)”的基石，但在日常刷题中也极为好用。核心逻辑： 在计算机里，负数是用补码表示的，-x 等价于 ~x + 1（按位取反再加一）。这个“加一”的操作，会产生进位，直到遇到原本最右边的那个 1 为止。结果就是，x 和 -x 只有最低位的 1 是一样的，其余位全反。举个例子： x = 6 (二进制 ...00110)-x = -6 (二进制 ...11010)x & -x = 00110 & 11010 = 00010 (也就是 2)经典应用场景：LC 260. 只出现一次的数字 III： 数组里有两个数字出现了一次，其他都出现了两次。先把所有数异或起来得到 xor_sum，然后用 xor_sum & -xor_sum 找出这两个数字在二进制上第一处不同的那一位，从而把数组分成两组单独求解。3. 异或 (^) 的消消乐魔法异或（XOR）的本质是“不进位的加法”。它有两个极其重要的性质：自己跟自己异或是 0： a ^ a = 0任何数跟 0 异或是它自己： a ^ 0 = a经典应用场景：LC 136. 只出现一次的数字： 数组里除了一个数字，其他数字都出现了两次。你只需要把所有数字挨个 ^ 起来，成对的数字全都变成了 0，最后剩下的那个结果，就是落单的数字！不需要用哈希表，空间复杂度直接降为 $O(1)$。不使用额外变量交换两个数：Pythona = a ^ b
b = a ^ b
a = a ^ b
4. 状态压缩（Bitmask）基础操作在回溯题或者动态规划（状态压缩 DP）里，我们经常把一个长度为 32 以内的布尔数组，直接压缩成一个整数（每一位是 0 或 1）。假设我们要操作第 i 位（i 从 0 开始算）：检查第 i 位是不是 1： (x >> i) & 1 （把第 i 位推到最右边，看看是不是 1）把第 i 位置为 1： x | (1 << i) （1 << i 就是生成一个只有第 i 位是 1 的数，用或运算把它“贴”上去）翻转第 i 位： x ^ (1 << i) （利用异或 1 会翻转的特性）经典应用场景：LC 78. 子集： 长度为 n 的数组有 2^n 个子集。我们可以直接从 0 遍历到 2^n - 1，每个数字的二进制表示就对应一种选或不选的方案。

LC. 3936. Minimum Swaps to Move Zeros to End

我写代码糊涂了，居然忘了加上 Break， 左右指针找到对应的目标值后应该 break；同时交换必须维护好 L < R 才能进行交换。

1. class Solution:
   
2.     def minimumSwaps(self, nums: list[int]) -> int:
   
3.         ans = 0
   
4.         L = 0
   
5.         N = len(nums)
   
6.         R = N - 1
   
7.         
   
8.         while L < R:            
   
9.             while L < N:
   
10.                 if nums[L] != 0:
    
11.                     L += 1
    
12.                 else:
    
13.                     break
    
14.             while R >= 0:
    
15.                 if nums[R] == 0:
    
16.                     R -= 1
    
17.                 else:
    
18.                     break
    
19.             # swap
    
20.             if L < N and R >= 0 and L < R:
    
21.                 nums[L], nums[R] = nums[R], nums[L]
    
22.                 ans += 1
    
23. 
    
24.         return ans
    
25.         
    
26.         
    

复制代码

当然，可以提高

两个可以提升代码“质感”的细节：

合并判断条件： 既然 nums[L] != 0 的时候才继续走，不如直接把它写进 while 的条件里，这样代码更短，阅读起来也更连贯。

交换后直接迈步： 在你成功交换了 nums[L] 和 nums[R] 之后，这两个位置上的数字肯定已经不需要再被检查了。所以可以在交换后直接写上 L += 1 和 R -= 1，帮下一轮循环省去一次多余的判断。

1. class Solution:
   
2.     def minimumSwaps(self, nums: list[int]) -> int:
   
3.         ans = 0
   
4.         N = len(nums)
   
5.         L = 0
   
6.         R = N - 1
   
7.         
   
8.         while L < R:            
   
9.             # 直接把判断条件放进 while 里，替代 if/else: break
   
10.             while L < N and nums[L] != 0:
    
11.                 L += 1
    
12.                
    
13.             while R >= 0 and nums[R] == 0:
    
14.                 R -= 1
    
15.                
    
16.             # swap：只需确保左右指针没有交错
    
17.             if L < R:
    
18.                 nums[L], nums[R] = nums[R], nums[L]
    
19.                 ans += 1
    
20.                
    
21.                 # 交换完后，主动让指针往前迈一步，加速循环
    
22.                 L += 1
    
23.                 R -= 1
    
24. 
    
25.         return ans

复制代码

当然更进一步，可以思考这道题目的本质是

如果数组里一共有 K 个 0。
那么最终完美状态下，数组的最后 K 个位置，必须全都是 0。
反过来说，想要步数最少，我们只需要看：数组的前 N - K 个位置里，目前混进了多少个 0？
因为每一次交换，我们都能精准地把前排的一个 0，和后排的一个非 0 互换。前排有几个 0，就需要换几次。

两个 Python 的 counts 加上切片即可解决。

1. class Solution:
   
2.     def minimumSwaps(self, nums: list[int]) -> int:
   
3.         zero_count = nums.count(0)
   
4.         
   
5.         # 如果没有 0，直接返回 0，避免切片越界
   
6.         if zero_count == 0:
   
7.             return 0
   
8.             
   
9.         # 统计前面部分（不包含最后 zero_count 个位置）里有几个 0
   
10.         # nums[:-zero_count] 的意思就是截取掉末尾 zero_count 长度的切片
    
11.         return nums[:-zero_count].count(0)

复制代码

2196. Create Binary Tree From Descriptions

这道题目的核心藏在一句话里面

a binary tree of unique values

所以可以放心的用 node val 作为 Node ID。

别忘记最后把不在 child value 里的 node 设置成 root。

1. # Definition for a binary tree node.
   
2. # class TreeNode:
   
3. #     def __init__(self, val=0, left=None, right=None):
   
4. #         self.val = val
   
5. #         self.left = left
   
6. #         self.right = right
   
7. class Solution:
   
8.     def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
   
9.         node_dict = dict()
   
10.         children_set = set()
    
11.         all_values_set = set()
    
12. 
    
13.         for parent, child, isLeft in descriptions:
    
14.             if parent not in node_dict:
    
15.                 node_dict[parent] = TreeNode(val=parent)
    
16.             
    
17.             if child not in node_dict:
    
18.                 node_dict[child] = TreeNode(val=child)
    
19. 
    
20.             if isLeft == 1:
    
21.                 node_dict[parent].left = node_dict[child]
    
22.             else:
    
23.                 node_dict[parent].right = node_dict[child]
    
24. 
    
25.             children_set.add(child)
    
26.             all_values_set.add(child)
    
27.             all_values_set.add(parent)
    
28. 
    
29.         for val in all_values_set:
    
30.             if val not in children_set:
    
31.                 root_val = val
    
32.                 break
    
33. 
    
34.         return node_dict[root_val]
    
35. 
    
36. 
    
37. 
    

复制代码

那么如果允许重复值呢？

如果在面试中，面试官突然把 “unique values” 这个条件删掉，问你：“如果节点的值可以重复，该怎么做？”

千万别慌，这其实是一个绝佳的展现你沟通能力（Clarification）和架构思维的机会。因为一旦值可以重复，原题的输入格式会直接导致歧义（Ambiguity），程序甚至无法唯一确定一棵树。

1. 为什么“值不唯一”时原题无解？（向面试官提问的点）
如果值不唯一，我们单纯用 parent_val 和 child_val 是无法区分不同的节点的。

举个栗子：
假设输入是：[[20, 10, 1], [20, 15, 1], [50, 20, 1]]

第一条线：一个值为 20 的节点，左孩子是 10。

第二条线：一个值为 20 的节点，左孩子是 15。（因为二叉树一个节点只能有一个左孩子，所以这一定是另一个值为 20 的不同节点）。

第三条线：一个值为 50 的节点，左孩子是 20。

Bug 来了： 这里的 50 连着的 20，到底是“有孩子 10 的那个 20”，还是“有孩子 15 的那个 20”？
只看值，我们根本无法分辨。

2. 面试官可能的两种“改题”方向
当你指出这个逻辑漏洞后，面试官通常会修改输入条件。常见的改法有两种：

方向 A：引入唯一的 Node ID（最常见）
面试官会说：“好，那我给你增加一个唯一标识。输入变成 [parent_id, child_id, parent_val, child_val, isLeft]。”

这时候我们的解题核心逻辑完全不变，只需要把哈希表的 Key 从“值”改成 “ID”，而 TreeNode 里面存的依然是“值”。

Python
# 核心伪代码调整：
nodes = {}       # key: node_id, value: TreeNode
children = set() # 存的是 child_id

for p_id, c_id, p_val, c_val, is_left in descriptions:
    if p_id not in nodes:
        nodes[p_id] = TreeNode(p_val) # 用 id 做索引，用 val 实例化
    if c_id not in nodes:
        nodes[c_id] = TreeNode(c_val)
        
    # 建立连接
    if is_left == 1:
        nodes[p_id].left = nodes[c_id]
    else:
        nodes[p_id].right = nodes[c_id]
        
    children.add(c_id)

# 找根节点：看哪个 p_id 不在 children 集合里
方向 B：输入本身就是树的某种序列化结果
面试官可能会说：“输入不再是离散的父子关系了，而是像 LeetCode 官方那样的层序遍历列表（比如 [50, 20, 80, 15, 17, None, 19]），值可以重复。”

如果是这种输入，那就变成了另一道经典题：LC 297. 二叉树的序列化与反序列化。我们需要用队列（Queue）进行 BFS（广度优先搜索）来重建二叉树，这时候就完全不需要哈希表去 match 父子关系了。

总结
在实际面试中，遇到不确定或者看似有漏洞的条件：

先举反例：用一个极简的例子向面试官证明“如果值重复，会产生歧义”。

给出推导：说明为什么需要 ID 或者其他的输入格式。

快速重构：在代码里用 id 代替 val 作为字典的键。

LC. 415. Add Strings

Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.



Example 1:

Input: num1 = "11", num2 = "123"
Output: "134"
Example 2:

Input: num1 = "456", num2 = "77"
Output: "533"
Example 3:

Input: num1 = "0", num2 = "0"
Output: "0"


Constraints:

1 <= num1.length, num2.length <= 104
num1 and num2 consist of only digits.
num1 and num2 don't have any leading zeros except for the zero itself.


我的解法

1. class Solution:
   
2.     def addStrings(self, num1: str, num2: str) -> str:
   
3.         ans = deque([])
   
4.         n1 = len(num1)
   
5.         n2 = len(num2)
   
6. 
   
7.         carry = 0
   
8.         ind1 = n1-1
   
9.         ind2 = n2-1
   
10. 
    
11.         while ind1 >= 0 and ind2 >= 0:
    
12.             dsum = int(num1[ind1]) + int(num2[ind2]) + carry
    
13.             ans.appendleft(str(dsum % 10))
    
14.             carry = dsum // 10
    
15.             ind1 -= 1
    
16.             ind2 -= 1
    
17. 
    
18.         while ind1 >= 0:
    
19.             dsum = int(num1[ind1]) + carry
    
20.             ans.appendleft(str(dsum % 10))
    
21.             carry = dsum // 10
    
22.             ind1 -= 1
    
23. 
    
24.         while ind2 >= 0:
    
25.             dsum = int(num2[ind2]) + carry
    
26.             ans.appendleft(str(dsum % 10))
    
27.             carry = dsum // 10
    
28.             ind2 -= 1
    
29.         
    
30.         if carry:
    
31.             ans.appendleft(str(carry))
    
32.         
    
33.         return "".join(ans)

复制代码

Gemini 的评价还挺中肯的

2. 你的代码可以怎样优化？ (Debug / 优化点)

你目前的写法是分了三个 while 循环：两个都没越界时。num1 没越界时。num2 没越界时。优化技巧：单循环合并我们完全可以把这三个循环合并成一个循环。只要 ind1 还没走完，或者 ind2 还没走完，或者最后还有进位 carry，我们就继续算。如果谁提前走完了，那个位置的数字就默认当做 0。


关于 int() 转换的严谨性：题目要求“不能直接把输入转成整数 (not convert the inputs to integers directly)”。你用 int(num1[ind1]) 转换的是单个字符，大多数面试官是可以接受的。但如果遇到极其严格的面试官（或者 C++/Java 背景的面试官），他们可能希望你连单个字符都不用内置强转。这时候可以使用 ASCII 码的偏移量来计算：ord(char) - ord('0')，这在 Python 中是 100% 符合“不依赖内置大数/转换库”要求的硬核写法。


关于 deque vs list：虽然 deque.appendleft() 是 $O(1)$，但在 Python 中，更常规且底层的执行效率更高的写法是：使用普通列表 list.append() 添加到尾部，最后一次性反转列表 ans[::-1]。因为普通列表的连续内存追加和切片反转在 CPython 底层优化得极其高效。

优化代码

1. class Solution:
   
2.     def addStrings(self, num1: str, num2: str) -> str:
   
3.         ans = []
   
4.         ind1, ind2 = len(num1) - 1, len(num2) - 1
   
5.         carry = 0
   
6. 
   
7.         while ind1 >= 0 or ind2 >= 0 or carry:
   
8.             # 严格模式：将字符转为数字
   
9.             x = ord(num1[ind1]) - ord('0') if ind1 >= 0 else 0
   
10.             y = ord(num2[ind2]) - ord('0') if ind2 >= 0 else 0
    
11.             
    
12.             total = x + y + carry
    
13.             
    
14.             # 严格模式：将计算出的单数字符（0-9）转回字符串形式
    
15.             digit = total % 10
    
16.             ans.append(chr(digit + ord('0')))
    
17.             
    
18.             carry = total // 10
    
19.             
    
20.             ind1 -= 1
    
21.             ind2 -= 1
    
22.         
    
23.         return "".join(ans[::-1])

复制代码

359. Logger Rate Limiter

简单题，但是这道题目可以 follow up。

AI 的 follow up 还是挺好的，学习了。

code

1. class Logger:
   
2. 
   
3.     def __init__(self):
   
4.         self.logger = dict()
   
5. 
   
6.     def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
   
7.         if message not in self.logger:
   
8.             self.logger[message] = timestamp + 10
   
9.             return True
   
10.         else:
    
11.             if timestamp >= self.logger[message]:
    
12.                 self.logger[message] = timestamp + 10
    
13.                 return True
    
14.             else:
    
15.                 return False
    
16. 
    
17. 
    
18. 
    
19. # Your Logger object will be instantiated and called as such:
    
20. # obj = Logger()
    
21. # param_1 = obj.shouldPrintMessage(timestamp,message)

复制代码

改进

其实我不是特别喜欢合并这个写法，因为这样虽然代码短了，但是两个判断合并了，其实并不清晰。

我们可以把“第一次遇到这个单词”和“遇到了但已经过了10秒冷却期”这两种可以打印的情况合并。

如果 message 不在字典里，或者当前时间 timestamp >= 字典里记录的时间，说明可以打印。

否则，说明还在冷却期内，不能打印。

1. class Logger:
   
2. 
   
3.     def __init__(self):
   
4.         # 记录每个 message 下一次允许打印的时间戳
   
5.         self.msg_earliest_time = {}
   
6. 
   
7.     def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
   
8.         # 如果当前时间还没到允许打印的时间，直接拒绝
   
9.         if message in self.msg_earliest_time and timestamp < self.msg_earliest_time[message]:
   
10.             return False
    
11.             
    
12.         # 否则（不在字典里，或者已经过了冷却期），更新时间并允许打印
    
13.         self.msg_earliest_time[message] = timestamp + 10
    
14.         return True

复制代码

如果面试官看你秒杀了这道题，通常会抛出下面这个 Follow-up（追问）：面试官： “如果这个 Logger 运行了很久，有海量的不同 message 进来，你的 Dict 会越来越大，导致内存撑爆（OOM）。由于题目说了 timestamp 是递增进来的，你该怎么优化内存？”💡 破题思路：既然 timestamp 是单调递增的，那些已经过了很久的日志（比如几小时前的），我们其实不需要一直存在字典里。解法： 我们可以配合使用一个 双端队列（collections.deque） 来按时间顺序存储 (timestamp, message)。每次调用 shouldPrintMessage 时，先看队列头部，把那些 timestamp <= 当前时间 - 10 的过期垃圾数据从队列和字典中彻底删除（Clean up）。这样字典里就永远只保留最近 10 秒的数据，内存直接降为 $O(1)$ 常数级别！

简单来说：deque 负责帮你找出“谁过期了”，然后你根据 deque 提供的信息，手动去把 dict 里对应的记录删掉。


我们可以把原本存时间戳的 dict，简化成一个 set（哈希集合），专门用来存放“当前处于 10 秒冷却期内的日志”。

💡 清理机制是怎么运作的？

deque 维护时间顺序：队列里只存 允许打印 的日志，格式为 (timestamp, message)。因为题目保证了时间戳是递增进来的，所以队头（左侧）永远是最老的数据。

set 维护 $O(1)$ 查询：集合里存放当前还在队列里的 message。联动清理（核心所在）：每次来一条新日志，在判断它能不能打印之前，先去检查 deque 的队头。如果队头日志的时间已经 $\ge 10$ 秒了，就把它从 deque 里 popleft() 弹出来，同时！拿弹出来的那个 message 去把 set 里的记录 remove 掉。

1. from collections import deque
   
2. 
   
3. class Logger:
   
4.     def __init__(self):
   
5.         # set 用来做 O(1) 的快速查找，记录“当前处于冷却期的 message”
   
6.         self.msg_set = set()
   
7.         # deque 用来记录打印历史，格式: (timestamp, message)
   
8.         self.msg_queue = deque()
   
9. 
   
10.     def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
    
11.         # 1. 核心清理逻辑：从队头检查，把 10 秒前的“老古董”全部扔掉
    
12.         while self.msg_queue and timestamp - self.msg_queue[0][0] >= 10:
    
13.             old_timestamp, old_message = self.msg_queue.popleft()
    
14.             # ★ 就在这一步！利用从 deque 拿到的 old_message，去清理 set（相当于清理 dict）
    
15.             self.msg_set.remove(old_message)
    
16.             
    
17.         # 2. 判断当前 message 是否还在 set 里（是否还在冷却期）
    
18.         if message in self.msg_set:
    
19.             return False
    
20.             
    
21.         # 3. 如果允许打印，加入队列和集合，开始它自己的 10 秒冷却期
    
22.         self.msg_set.add(message)
    
23.         self.msg_queue.append((timestamp, message))
    
24.         return True

复制代码