刷题记录帖子

346. Moving Average from Data Stream

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the MovingAverage class:

MovingAverage(int size) Initializes the object with the size of the window size.
double next(int val) Returns the moving average of the last size values of the stream.


Example 1:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3


Constraints:

1 <= size <= 1000
-105 <= val <= 105
At most 104 calls will be made to next.


这道题目还是挺简单的，我一开始想的是中位数，做到一半发现是 avg 那就简单了。

Using Dequeue

1. class MovingAverage:
   
2. 
   
3.     def __init__(self, size: int):
   
4.         self.size = size
   
5.         self.nums = deque([])
   
6.         self.sumALL = 0
   
7. 
   
8.     def next(self, val: int) -> float:
   
9.         self.sumALL += val
   
10.         self.nums.append(val)
    
11. 
    
12.         if len(self.nums) > self.size:
    
13.             removed_val = self.nums.popleft()
    
14.             self.sumALL -= removed_val
    
15. 
    
16. 
    
17.         return self.sumALL / len(self.nums)
    
18. 
    
19. 
    
20. # Your MovingAverage object will be instantiated and called as such:
    
21. # obj = MovingAverage(size)
    
22. # param_1 = obj.next(val)

复制代码

优化，不是用 Dequeue， 使用数组。

用一个大小固定的列表 + 指针取模来模拟 Dequeue

1. class MovingAverage:
   
2.     def __init__(self, size: int):
   
3.         self.size = size
   
4.         self.queue = [0] * size  # 初始化一个固定大小的数组
   
5.         self.window_sum = 0
   
6.         self.count = 0           # 记录总共接收到的数字个数
   
7. 
   
8.     def next(self, val: int) -> float:
   
9.         self.count += 1
   
10.         
    
11.         # 计算当前要插入或覆盖的索引位置 (通过取模实现环形)
    
12.         tail = (self.count - 1) % self.size
    
13.         
    
14.         # 减去旧值，加上新值
    
15.         self.window_sum = self.window_sum - self.queue[tail] + val
    
16.         
    
17.         # 更新数组
    
18.         self.queue[tail] = val
    
19.         
    
20.         # 计算分母：在没填满之前除以 count，填满后除以 size
    
21.         return self.window_sum / min(self.size, self.count)

复制代码

补充内容 (2026-06-12 10:30 +08:00):
min(self.count, self.size)

是很高明的技巧，这样省去了判断是不是数组填满的问题。

LC. 836. Rectangle Overlap

这个就是很经典的 AABB 碰撞检测（Axis-Aligned Bounding Box）在 Object detection 中也是常用的，不过我完全忘了。

也不是完全忘了，我知道不能去列举 BBox 到底是怎么排列的，但是还是没想出来最优的解法。

囧！

思路 1: 反向思维（排除法）—— 推荐！思路： 证明两个矩形“重叠”很难，但证明它们“不重叠”非常简单！两个矩形在什么情况下绝对碰不到？只有四种情况：rec1 在 rec2 的左侧完全错开：rec1 的右边缘 $\le$ rec2 的左边缘 (rec1[2] <= rec2[0])rec1 在 rec2 的右侧完全错开：rec1 的左边缘 $\ge$ rec2 的右边缘 (rec1[0] >= rec2[2])rec1 在 rec2 的下方完全错开：rec1 的上边缘 $\le$ rec2 的下边缘 (rec1[3] <= rec2[1])rec1 在 rec2 的上方完全错开：rec1 的下边缘 $\ge$ rec2 的上边缘 (rec1[1] >= rec2[3])只要这四种情况有一种发生，就不重叠。反之，就必定重叠。

1. class Solution:
   
2.     def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
   
3.         # rec1: [x1, y1, x2, y2]
   
4.         # rec2: [x3, y3, x4, y4]
   
5.         
   
6.         # 判断四个"不重叠"的条件
   
7.         # 注意: 题目说 touching (贴边) 不算重叠，所以用 <= 或 >=
   
8.         is_left   = rec1[2] <= rec2[0] # rec1 完全在 rec2 左边
   
9.         is_right  = rec1[0] >= rec2[2] # rec1 完全在 rec2 右边
   
10.         is_bottom = rec1[3] <= rec2[1] # rec1 完全在 rec2 下边
    
11.         is_top    = rec1[1] >= rec2[3] # rec1 完全在 rec2 上边
    
12.         
    
13.         # 如果以上任意一个成立，就不重叠；全部不成立，才重叠。
    
14.         return not (is_left or is_right or is_bottom or is_top)

复制代码

思路 2: 正向思维（投影法 / 降维打击）思路： 两个 2D 矩形如果重叠，意味着它们在 X 轴上的投影是重叠的，并且在 Y 轴上的投影也是重叠的。这样就把复杂的 2D 问题变成了两个简单的 1D 线段交集问题。对于 X 轴线段 $[x_{1}, x_{2}]$ 和 $[x_{3}, x_{4}]$，重叠的条件是：左端点的最大值 < 右端点的最小值。Y 轴同理。

1. class Solution:
   
2.     def isRectangleOverlap(self, rec1: list[int], rec2: list[int]) -> bool:
   
3.         # X 轴投影有重叠: max(左端点) < min(右端点)
   
4.         x_overlap = max(rec1[0], rec2[0]) < min(rec1[2], rec2[2])
   
5.         
   
6.         # Y 轴投影有重叠: max(下端点) < min(上端点)
   
7.         y_overlap = max(rec1[1], rec2[1]) < min(rec1[3], rec2[3])
   
8.         
   
9.         # 必须 X 轴和 Y 轴都有重叠，矩形才会重叠
   
10.         return x_overlap and y_overlap

复制代码

就这道题而言，解法 1 更加简单直接，但是从更加广泛应用的角度，其实 2 更好。

因为它可以直接用到 223. Rectangle Area 上。


Given the coordinates of two rectilinear rectangles in a 2D plane, return the total area covered by the two rectangles.

The first rectangle is defined by its bottom-left corner (ax1, ay1) and its top-right corner (ax2, ay2).

The second rectangle is defined by its bottom-left corner (bx1, by1) and its top-right corner (bx2, by2).



Example 1:

Rectangle Area
Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45
Example 2:

Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
Output: 16


Constraints:

-104 <= ax1 <= ax2 <= 104
-104 <= ay1 <= ay2 <= 104
-104 <= bx1 <= bx2 <= 104
-104 <= by1 <= by2 <= 104

223. Rectangle Area
Given the coordinates of two rectilinear rectangles in a 2D plane, return the total area covered by the two rectangles.

The first rectangle is defined by its bottom-left corner (ax1, ay1) and its top-right corner (ax2, ay2).

The second rectangle is defined by its bottom-left corner (bx1, by1) and its top-right corner (bx2, by2).



Example 1:

Rectangle Area
Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45
Example 2:

Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
Output: 16


Constraints:

-104 <= ax1 <= ax2 <= 104
-104 <= ay1 <= ay2 <= 104
-104 <= bx1 <= bx2 <= 104
-104 <= by1 <= by2 <= 104

核心原则：永远不要让负数的宽和高参与乘法运算。 要解决这个问题，不要在最后乘出来再去判断，而是要在计算宽和高的阶段，就把负数“掐死”在摇篮里。技巧：套一个 max(0, 值)。

1. class Solution:
   
2.     def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:
   
3.         # 1. 计算重叠的宽和高
   
4.         # 技巧：用 max(0, ...) 兜底。如果没重叠算出来是负数，直接强制归零
   
5.         """
   
6.         核心原则：永远不要让负数的宽和高参与乘法运算。 要解决这个问题，不要在最后乘出来再去判断，而是要在计算宽和高的阶段，就把负数“掐死”在摇篮里。技巧：套一个 max(0, 值)。
   
7.         """
   
8.         overlap_width = max(0, min(ax2, bx2) - max(ax1, bx1))
   
9.         overlap_height = max(0, min(ay2, by2) - max(ay1, by1))
   
10.         
    
11.         # 2. 计算重叠面积
    
12.         # 此时 overlap_width 和 overlap_height 最少也是 0，绝对不会出现"负负得正"
    
13.         interArea = overlap_width * overlap_height
    
14.         
    
15.         # 3. 计算各自的独立面积
    
16.         totalArea = (ay2 - ay1) * (ax2 - ax1) + (by2 - by1) * (bx2 - bx1)
    
17. 
    
18.         # 4. 直接返回结果，无需 if-else
    
19.         # 因为如果没有重叠，interArea 自然就是 0，减去 0 没有任何影响
    
20.         return totalArea - interArea

复制代码

LC. 3612. Process String with Special Operations I
Hint
You are given a string s consisting of lowercase English letters and the special characters: *, #, and %.

Build a new string result by processing s according to the following rules from left to right:

If the letter is a lowercase English letter append it to result.
A '*' removes the last character from result, if it exists.
A '#' duplicates the current result and appends it to itself.
A '%' reverses the current result.
Return the final string result after processing all characters in s.



Example 1:

Input: s = "a#b%*"

Output: "ba"

Explanation:

i        s[i]        Operation        Current result
0        'a'        Append 'a'        "a"
1        '#'        Duplicate result        "aa"
2        'b'        Append 'b'        "aab"
3        '%'        Reverse result        "baa"
4        '*'        Remove the last character        "ba"
Thus, the final result is "ba".

Example 2:

Input: s = "z*#"

Output: ""

Explanation:

i        s[i]        Operation        Current result
0        'z'        Append 'z'        "z"
1        '*'        Remove the last character        ""
2        '#'        Duplicate the string        ""
Thus, the final result is "".



Constraints:

1 <= s.length <= 20
s consists of only lowercase English letters and special characters *, #, and %.

其实我觉得是简单题，当然它还有 II 那个就是 hard 了。

因为数据量翻倍才是考察能力的时候，需要上技巧。

这个数据量可以直接 simulation，因为撑满了，2^19 次方个字符，每次都翻倍。

1. class Solution:
   
2.     def processStr(self, s: str) -> str:
   
3.         res = []
   
4. 
   
5.         for ch in s:
   
6.             if ch == '*':
   
7.                 if res: res.pop()
   
8.             elif ch == '#':
   
9.                 if res: res += res
   
10.             elif ch == '%':
    
11.                 if res: res.reverse()
    
12.             else:
    
13.                 res.append(ch)
    
14.         
    
15.         return "".join(res)

复制代码

LC. 3614. Process String with Special Operations II

Hint
You are given a string s consisting of lowercase English letters and the special characters: '*', '#', and '%'.

You are also given an integer k.

Build a new string result by processing s according to the following rules from left to right:

If the letter is a lowercase English letter append it to result.
A '*' removes the last character from result, if it exists.
A '#' duplicates the current result and appends it to itself.
A '%' reverses the current result.
Return the kth character of the final string result. If k is out of the bounds of result, return '.'.



Example 1:

Input: s = "a#b%*", k = 1

Output: "a"

Explanation:

i        s[i]        Operation        Current result
0        'a'        Append 'a'        "a"
1        '#'        Duplicate result        "aa"
2        'b'        Append 'b'        "aab"
3        '%'        Reverse result        "baa"
4        '*'        Remove the last character        "ba"
The final result is "ba". The character at index k = 1 is 'a'.

Example 2:

Input: s = "cd%#*#", k = 3

Output: "d"

Explanation:

i        s[i]        Operation        Current result
0        'c'        Append 'c'        "c"
1        'd'        Append 'd'        "cd"
2        '%'        Reverse result        "dc"
3        '#'        Duplicate result        "dcdc"
4        '*'        Remove the last character        "dcd"
5        '#'        Duplicate result        "dcddcd"
The final result is "dcddcd". The character at index k = 3 is 'd'.

Example 3:

Input: s = "z*#", k = 0

Output: "."

Explanation:

i        s[i]        Operation        Current result
0        'z'        Append 'z'        "z"
1        '*'        Remove the last character        ""
2        '#'        Duplicate the string        ""
The final result is "". Since index k = 0 is out of bounds, the output is '.'.



Constraints:

1 <= s.length <= 105
s consists of only lowercase English letters and special characters '*', '#', and '%'.
0 <= k <= 1015
The length of result after processing s will not exceed 1015.

I 中，因为数据量极小，我们直接操作数组就搞定了。但在这道 II 里，s 的长度到了 10^5，而 k 和最终长度更是高达 10^15。这意味着：任何试图真正在内存里拼接字符串的解法，都会直接 OOM（内存超限）或 TLE（超时）。

LC. 1344. Angle Between Hands of a Clock

直接模拟，注意时针并不是在12个时的整点位置上。

1. class Solution:
   
2.     def angleClock(self, hour: int, minutes: int) -> float:
   
3.         # hour to angle
   
4.         hour_angle = hour * 30.0 + minutes * 0.5
   
5.         # minutes to angle
   
6.         minutes_angle = minutes * 6.0
   
7. 
   
8.         inner_angle = min( abs(hour_angle - minutes_angle), 360 - abs(hour_angle - minutes_angle))
   
9. 
   
10.         return inner_angle
    
11.         

复制代码

优化，就是 hour 可以取值 到 12， 所以会出现超出物理意义的答案但是不影响答案，因为是求差。

为了让数据在物理意义上更严谨（即指针角度永远保持在 [0, 360) 之间），我们可以对 hour 做一次 % 12 的取模操作。把 12 点映射为 0 点，这样计算出的角度永远不会超过 360 度。

LC. 1732. Find the Highest Altitude

1. class Solution:
   
2.     def largestAltitude(self, gain: List[int]) -> int:
   
3.         ans = 0
   
4.         curr_h = 0
   
5. 
   
6.         for g in gain:
   
7.             curr_h += g
   
8.             ans = max(curr_h, ans)
   
9.         
   
10.         return ans
    
11.         

复制代码

LC. 1833. Maximum Ice Cream Bars

发现这道题我当年刷过，不过其实是不对的思路。有了 AI 之后，辅助学习还是效率很高的。

我的思路，sort 然后贪心，尽可能买最便宜的。

1. class Solution:
   
2.     def maxIceCream(self, costs: List[int], coins: int) -> int:
   
3.         costs.sort()
   
4.         ans = 0
   
5.         for cost in costs:
   
6.             if coins >= cost:
   
7.                 coins -= cost
   
8.                 ans += 1
   
9.             else:
   
10.                 break # 买不起当前最便宜的了，后面的更贵，直接退出
    
11.         return ans

复制代码

但是这个题目其实有个条件

"You must solve the problem by counting sort." (你必须使用计数排序来解决此问题)

为什么要强制要求计数排序 (Counting Sort)？

我们看一眼数据范围（Constraints）：costs.length == n 且 n 最大是 100,000。costs[i] 的最大值也是 100,000。常规排序的时间复杂度是 $O(N \log N)$。但是，当数组中元素的最大值不大时，使用基于数组下标的“计数排序”，可以将时间复杂度降到惊人的 $O(N + M)$（$M$ 是雪糕的最大价格）。这就是这道题真正的考点。

解法思路

3. 核心思路：计数排序模型
既然知道每个雪糕的价格不超过 100,000，我们可以创建一个数组（或者 Python 的哈希表/Counter），把价格作为下标，把这个价格的雪糕数量作为值。

具体步骤：

找出雪糕里的最高价格（为了确定计数数组的大小）。

遍历 costs，统计每个价格的雪糕有多少根。

从价格 1 开始从小到大遍历：

如果当前价格的雪糕有货，并且我们手里的 coins 还够买，就尽可能多地买。

计算我们最多能买几根（受限于“存货量”和“我们手里的钱”）。

扣除相应的钱，增加购买数量。

如果钱不够买哪怕一根当前价格的雪糕了，说明后面的更买不起，直接结束。

1. class Solution:
   
2.     def maxIceCream(self, costs: List[int], coins: int) -> int:
   
3.         if not costs: return 0
   
4.         
   
5.         # 1. 找到最大价格，初始化计数数组
   
6.         max_cost = max(costs)
   
7.         # freq[i] 表示价格为 i 的雪糕数量
   
8.         freq = [0] * (max_cost + 1)
   
9.         
   
10.         # 2. 统计每个价格的雪糕数量
    
11.         for cost in costs:
    
12.             freq[cost] += 1
    
13.             
    
14.         ans = 0
    
15.         
    
16.         # 3. 从最便宜的雪糕（价格为 1）开始贪心购买
    
17.         for price in range(1, max_cost + 1):
    
18.             count = freq[price]
    
19.             
    
20.             if count == 0:
    
21.                 continue # 这个价格没有雪糕，看下一个价格
    
22.                
    
23.             if coins < price:
    
24.                 break # 连一根当前价格的雪糕都买不起了，直接结束
    
25.                
    
26.             # 计算当前价格下，我们最多能买几根
    
27.             # 要么把存货全买了 (count)，要么把钱花光能买多少买多少 (coins // price)
    
28.             buy = min(count, coins // price)
    
29.             
    
30.             # 更新已买数量和剩余的钱
    
31.             ans += buy
    
32.             coins -= buy * price
    
33.             
    
34.         return ans

复制代码

计数排序是用空间换时间的经典体现。对于这道题的数据规模（$N=10^5, M=10^5$），$O(N + M)$ 大约是 $2 \times 10^5$ 次操作，远远少于 $O(N \log N)$ 的大约 $1.6 \times 10^6$ 次操作，在运行速度上有质的飞跃。

LC. 1189. Maximum Number of Balloons

简单题，从一个 string 中找出能 form 一个 target 单词的最大数目。

1. class Solution:
   
2.     def maxNumberOfBalloons(self, text: str) -> int:
   
3.         freq = {'b': 0, 'a': 0, 'l':0, 'o': 0, 'n':0}
   
4. 
   
5.         for ch in text:
   
6.             if ch in freq:
   
7.                 freq[ch] += 1
   
8.         
   
9.         ans = float('inf')
   
10. 
    
11.         for ch in freq.keys():
    
12.             if ch in ['b', 'a', 'n']:
    
13.                 ans = min(freq[ch], ans)
    
14.             else:
    
15.                 ans = min(freq[ch] // 2, ans)
    
16.         
    
17.         return ans
    
18.             

复制代码

不过，可以优化，直接用 Collections 来统计 freq。虽然比我的方法会更多一点空间，但是字母也就只有 26 个。所以多不了太多。

然后其实不用变量 ans 来统计，直接统计最大公约的freq。

1. from collections import Counter
   
2. 
   
3. class Solution:
   
4.     def maxNumberOfBalloons(self, text: str) -> int:
   
5.         # Counter 会自动统计 text 中所有字符的出现次数
   
6.         # 如果某个字符不存在，比如 count['b']，它会自动返回 0，而不会报错 (KeyError)
   
7.         count = Counter(text)
   
8.         
   
9.         # 直接在一行内求出所有必备条件中的最小值
   
10.         return min(
    
11.             count['b'],
    
12.             count['a'],
    
13.             count['l'] // 2,
    
14.             count['o'] // 2,
    
15.             count['n']
    
16.         )

复制代码

LC. 2287. Rearrange Characters to Make Target String

Hint
You are given two 0-indexed strings s and target. You can take some letters from s and rearrange them to form new strings.

Return the maximum number of copies of target that can be formed by taking letters from s and rearranging them.



Example 1:

Input: s = "ilovecodingonleetcode", target = "code"
Output: 2
Explanation:
For the first copy of "code", take the letters at indices 4, 5, 6, and 7.
For the second copy of "code", take the letters at indices 17, 18, 19, and 20.
The strings that are formed are "ecod" and "code" which can both be rearranged into "code".
We can make at most two copies of "code", so we return 2.
Example 2:

Input: s = "abcba", target = "abc"
Output: 1
Explanation:
We can make one copy of "abc" by taking the letters at indices 0, 1, and 2.
We can make at most one copy of "abc", so we return 1.
Note that while there is an extra 'a' and 'b' at indices 3 and 4, we cannot reuse the letter 'c' at index 2, so we cannot make a second copy of "abc".
Example 3:

Input: s = "abbaccaddaeea", target = "aaaaa"
Output: 1
Explanation:
We can make one copy of "aaaaa" by taking the letters at indices 0, 3, 6, 9, and 12.
We can make at most one copy of "aaaaa", so we return 1.


Constraints:

1 <= s.length <= 100
1 <= target.length <= 10
s and target consist of lowercase English letters.


和上一题基本完全一致，但是这次 target 也是变化的，所以也需要统计 target 的字母频率。

得益于 Counter 的特性，如果 s 里面根本没有 target 里的某个字符，count[ch] 会直接返回 0。此时 0 // freq[ch] 也是 0，ans 顺理成章变为 0，没有任何 KeyError 的风险。

1. from collections import Counter
   
2. 
   
3. class Solution:
   
4.     def rearrangeCharacters(self, s: str, target: str) -> int:
   
5.         
   
6. 
   
7.         # Counter 会自动统计 text 中所有字符的出现次数
   
8.         # 如果某个字符不存在，比如 count['b']，它会自动返回 0，而不会报错 (KeyError)
   
9.         count = Counter(s)
   
10.         freq = Counter(target)
    
11.         
    
12.         ans = float('inf')
    
13.         for ch in freq.keys():
    
14.             ans = min(ans, count[ch] // freq[ch])
    
15. 
    
16.         return ans

复制代码

当然了，你要是喜欢 Pythonic 的代码，我们可以把最后的 for 循环找最小值的过程，利用 Python 的生成器表达式（Generator Expression）结合 min() 函数，写得更优雅一点。

另外，在 Python 中遍历字典的 key 时，直接写 for ch in freq: 即可，不需要写 .keys()，这也是一个小小的代码洁癖优化。

1. from collections import Counter
   
2. 
   
3. class Solution:
   
4.     def rearrangeCharacters(self, s: str, target: str) -> int:
   
5.         count = Counter(s)
   
6.         freq = Counter(target)
   
7.         
   
8.         # 使用生成器表达式，一行求出所有必备条件中的最小值
   
9.         return min(count[ch] // freq[ch] for ch in freq)

复制代码