刷题记录帖子

LC 3492. Maximum Containers on a Ship

简单题，直接木桶原理，算最短的那个限制。

1. class Solution:
   
2.     def maxContainers(self, n: int, w: int, maxWeight: int) -> int:
   
3.         return min(n * n, maxWeight // w)
   
4.         

复制代码

LC. 3491. Phone Number Prefix

数量级不大，所以可以直接暴力做。

就是一点需要注意是前缀要用 startswith，而不是 in，in 是比较子串。

class Solution:
def phonePrefix(self, numbers: List[str]) -> bool:
        for i, _ in enumerate(numbers):
                for j in range(len(numbers)):
                        if i != j and numbers[j].startswith(numbers):
                                return False

    return True
   

进阶解法，排序

核心思路：排序 (Sorting)
这道题有一个非常巧妙的性质：对于字符串数组，如果按字典序（字母顺序）进行排序，有前缀关系的字符串一定会紧紧挨在一起！

比如数组 ["00153", "15", "001", "007"]。
排序后变成：["001", "00153", "007", "15"]。
你看，"001" 和它的衍生词 "00153" 紧挨着了！

既然它们紧挨着，我们只需要比较相邻的两个字符串即可，完全不需要两层循环！

class Solution:
        def phonePrefix(self, numbers: List[str]) -> bool:
                # 1. 对字符串数组按字典序排序
                numbers.sort()
    # 2. 只需要对比相邻的元素
    for i in range(len(numbers) - 1):
        # 排序后，如果存在前缀关系，短的必定在前面，长的必定紧随其后
        if numbers[i + 1].startswith(numbers[i]):
            return False
            
    return True

更高阶解法

[i](拓展)：如果是超大规模的数据，或者需要频繁插入查询，这题的标准数据结构是 字典树 (Trie)。但这题数据量小，排序法是最优雅、性价比最高的。

1. 定义字典树的节点类

class TrieNode:
        def init(self):
                self.children = {} # 记录子节点，比如 {'3': TrieNode()}
                self.is_end = False # 标记是否是某个号码的结尾

class Solution:
        def phonePrefix(self, numbers: List[str]) -> bool:
                root = TrieNode()

    # 遍历每一个电话号码
    for num in numbers:
        curr = root
        
        # 将当前号码按字符插入字典树
        for char in num:
            # 如果没有这条路径，就建一个新的节点
            if char not in curr.children:
                curr.children[char] = TrieNode()
            
            curr = curr.children[char]
            
            # 【情况 A】路过了一个已经被标记为结尾的节点
            # 说明之前存过的一个短号码，是当前长号码的前缀
            if curr.is_end:
                return False
        
        # 当前号码插入完毕，停在了最后一个节点
        # 【情况 B】如果这个节点还有孩子，说明当前短号码是之前某个长号码的前缀
        if len(curr.children) > 0:
            return False
            
        # 如果都安全，把当前节点的结尾标记为 True
        curr.is_end = True
        
    return True

LC. 4014. Minimum Total Price After Applying Discounts
Solved
Medium
Hint
You are given two integer arrays prices and discounts.

The value prices[i] represents the price of the ith item, and discounts[j] represents a discount percentage.

You may apply discounts subject to the following rules:

Each discount can be applied to at most one item.
Each item can receive at most one discount.
An item may also receive no discount.
If a discount of d percent is applied to an item with price p, its final price becomes (p * (100 - d)) / 100. The final price is not rounded.

Return the minimum possible sum of final prices after assigning discounts optimally. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: prices = [10,30,21], discounts = [50,60]

Output: 32.50000

Explanation:

Apply discounts[1] = 60 to prices[1] = 30, thus 30 * (100 - 60) / 100 = 12.
Apply discounts[0] = 50 to prices[2] = 21, thus 21 * (100 - 50) / 100 = 10.5.
prices[0] = 10 receives no discount, so it stays 10.
The total is 12 + 10.5 + 10 = 32.50000, which is the minimum possible.

Example 2:

Input: prices = [100,70], discounts = [10,40,50]

Output: 92.00000

Explanation:​​​​​​​

Apply discounts[2] = 50 to prices[0] = 100, thus 100 * (100 - 50) / 100 = 50.
Apply discounts[1] = 40 to prices[1] = 70, thus 70 * (100 - 40) / 100 = 42.
The total is 50 + 42 = 92.00000, which is the minimum possible.

Example 3:

Input: prices = [7,3,9], discounts = [100,100]

Output: 3.00000

Explanation:

Apply discounts[0] = 100 to prices[2] = 9, thus 9 * (100 - 100) / 100 = 0.
Apply discounts[1] = 100 to prices[0] = 7, thus 7 * (100 - 100) / 100 = 0.
prices[1] = 3 receives no discount, so it stays 3.
The total is 0 + 0 + 3 = 3.00000, which is the minimum possible.

Constraints:

1 <= prices.length, discounts.length <= 105
1 <= prices[i] <= 105
1 <= discounts[j] <= 100

简单题，直接 Greedy，但是还是要考虑边界条件。

class Solution:
    def minPrice(self, prices: list[int], discounts: list[int]) -> float:
        # greedy
        prices.sort(reverse = True)
        discounts.sort(reverse = True)

        n = min(len(prices), len(discounts))
        ans = 0
   
        for i in range(n):
            ans += (prices[i] * (100 - discounts[i]) * 0.01)

if i < len(prices) - 1:
            for j in range(i+1, len(prices)):
                ans += prices[j]

        return ans

优化后代码

    class Solution:
    def minPrice(self, prices: list[int], discounts: list[int]) -> float:
    # 1. 贪心策略：将价格和折扣都降序排列
    prices.sort(reverse=True)
    discounts.sort(reverse=True)
    n = min(len(prices), len(discounts))
    ans = 0.0

    # 2. 对前 n 个最贵的商品，应用最大的折扣
    for i in range(n):
        # 提示：除以 100.0 比乘 0.01 在某些极端情况下精度更可控
        ans += prices[i] * (100 - discounts[i]) / 100.0

    # 3. 累加剩余没打折的商品
    # 如果 n == len(prices)，range(n, n) 为空，自动不执行，不需要 if 判断
    for j in range(n, len(prices)):
        ans += prices[j]

    return ans

LC 4015. Weighted Sum of a Tree

You are given an integer array parent of length n representing a rooted tree with nodes labeled from 0 to n - 1.

The tree is rooted at node 0, so parent[0] = -1. For each node i where 1 <= i <= n - 1, parent[i] denotes the parent of node i.

You are also given an integer array nums of length n, where nums[i] denotes the value of node i.

The weight of a node i at depth d is nums[i] * (h - d + 1), where h is the height of the tree.

Return the sum of the weights of all nodes in the tree.

The depth of a node is the number of nodes on the path from the root to that node, inclusive, with the root having depth 1.

The height of the tree is the maximum depth among all nodes in the tree.

Example 1:

​​​​​​​

Input: parent = [-1,0,0,0,2,2], nums = [5,2,3,1,4,6]

Output: 37

Explanation:

The height of the tree is 3.

Node nums[i] Depth (d) Weight
0 5 1 5 * (3 - 1 + 1) = 15
1 2 2 2 * (3 - 2 + 1) = 4
2 3 2 3 * (3 - 2 + 1) = 6
3 1 2 1 * (3 - 2 + 1) = 2
4 4 3 4 * (3 - 3 + 1) = 4
5 6 3 6 * (3 - 3 + 1) = 6
The sum of all node weights is 15 + 4 + 6 + 2 + 4 + 6 = 37.

Example 2:

​​​​​​​​​​​​​​

Input: parent = [-1,0,1,2], nums = [1,2,3,4]

Output: 20

Explanation:

The height of the tree is 4.

Node nums[i] Depth (d) Weight
0 1 1 1 * (4 - 1 + 1) = 4
1 2 2 2 * (4 - 2 + 1) = 6
2 3 3 3 * (4 - 3 + 1) = 6
3 4 4 4 * (4 - 4 + 1) = 4
The sum of all node weights is 4 + 6 + 6 + 4 = 20.

Constraints:

1 <= n <= 105
n == parent.length == nums.length
parent[0] == -1
0 <= parent[i] <= n - 1 for all i in [1, n - 1]
1 <= nums[i] <= 106
The input is generated such that the array parent represents a valid tree rooted at node 0.

class Solution:
    def weightedSum(self, parent: list[int], nums: list[int]) -> int:
        n = len(parent)
        indexChildDict = defaultdict(list)

        for i in range(n):
            indexChildDict[i] = list()

        for i in range(1, n):
            indexChildDict[parent[i]].append(i)

        depth = 1
        depth_dict = defaultdict(int)

        stack = [0]

        while stack:
            currLayer = len(stack)
            while currLayer:
                curr = stack.pop(0)
                depth_dict[curr] = depth
                if curr in indexChildDict:
                    for index in indexChildDict[curr]:
                        stack.append(index)
                currLayer -= 1
            depth += 1

        ans = 0
        height = depth - 1

        for i in range(n):
            ans += (nums[i] * (height - depth_dict[i] + 1))

        return ans        

不过这个解法问题很大，需要优化

from collections import defaultdict, deque

class Solution:
    def weightedSum(self, parent: list[int], nums: list[int]) -> int:
        n = len(parent)
        
        # 1. 建树 (只记录子节点即可)
        children = defaultdict(list)
        for i in range(1, n):
            children[parent[i]].append(i)
            
        # 2. BFS 遍历，记录每个节点的深度
        depths = [0] * n  # 使用数组代替字典，下标即节点号，值是深度
        queue = deque([0])  # 正确的队列初始化
        current_depth = 1
        
        while queue:
            level_size = len(queue)
            for _ in range(level_size):
                curr = queue.popleft() # O(1) 出队
                depths[curr] = current_depth
               
                # 直接遍历当前节点的所有子节点
                for child in children[curr]:
                    queue.append(child)
                    
            current_depth += 1
            
        # 此时 current_depth 多加了一次，height 应该是 current_depth - 1
        height = current_depth - 1
        
        # 3. 计算答案
        ans = 0
        for i in range(n):
            ans += nums[i] * (height - depths[i] + 1)
            
        return ans

扩展思考：可以不用 BFS/DFS 吗？
虽然你的 BFS 思路完全没问题，但对于树的父节点数组 parent，其实有一种更进阶的求深度的方法：带记忆化的迭代求解。

因为父节点的值永远指向更上层，我们可以通过向祖先回溯的方式求深度，并通过一个数组记录已经求过的节点，这样连图都不用建，速度非常快：

class Solution:
    def weightedSum(self, parent: list[int], nums: list[int]) -> int:
        n = len(parent)
        depths = [0] * n
        depths[0] = 1
        
        height = 1
        
        # 计算每个节点的深度
        for i in range(1, n):
            # 找当前节点的深度 (向父节点回溯)
            curr = i
            path = []
            while depths[curr] == 0:
                path.append(curr)
                curr = parent[curr]
               
            # 找到了已知深度的祖先，顺藤摸瓜计算沿途节点的深度
            d = depths[curr]
            while path:
                node = path.pop()
                d += 1
                depths[node] = d
               
            height = max(height, depths[i])
            
        # 计算答案
        ans = 0
        for i in range(n):
            ans += nums[i] * (height - depths[i] + 1)
            
        return ans

LC. 3487. Maximum Unique Subarray Sum After Deletion

You are given an integer array nums.

You are allowed to delete any number of elements from nums without making it empty. After performing the deletions, select a subarray of nums such that:

All elements in the subarray are unique.
The sum of the elements in the subarray is maximized.
Return the maximum sum of such a subarray.



Example 1:

Input: nums = [1,2,3,4,5]

Output: 15

Explanation:

Select the entire array without deleting any element to obtain the maximum sum.

Example 2:

Input: nums = [1,1,0,1,1]

Output: 1

Explanation:

Delete the element nums[0] == 1, nums[1] == 1, nums[2] == 0, and nums[3] == 1. Select the entire array [1] to obtain the maximum sum.

Example 3:

Input: nums = [1,2,-1,-2,1,0,-1]

Output: 3

Explanation:

Delete the elements nums[2] == -1 and nums[3] == -2, and select the subarray [2, 1] from [1, 2, 1, 0, -1] to obtain the maximum sum.



Constraints:

1 <= nums.length <= 100
-100 <= nums[i] <= 100

1. class Solution:
   
2.     def maxSum(self, nums: List[int]) -> int:
   
3.         ans = 0
   
4.         numset = set(nums)
   
5.         numlist = sorted(list(numset))
   
6. 
   
7.         if numlist[-1] < 0:
   
8.             return numlist[-1]
   
9.         else:
   
10.             for x in numlist:
    
11.                 if x > 0: ans += x
    
12.             return ans

复制代码

但是我的解法可以优化，就是其实我不需要知道 sorted list，我只需要知道最大值就行，

如果全是负数：因为题目要求至少保留一个元素（不能变为空数组），所以为了让“损失”最小，我们只保留那个最大的负数。

当前的代码：使用了 sorted(list(numset))。虽然题目限制了 N < 100，排序瞬间就能跑完，但在算法面试中，排序的时间复杂度是 O(U log U)（U 是去重后的元素个数）。其实我们并不需要排序，因为我们只是想知道“数组里的最大值是不是小于 0”。优化方向：找最大值只需要 O(N) 的时间。我们可以直接用 Python 内置的 max() 函数，结合集合 set() 和生成器推导式，把代码写得更加优雅和高效。

1. class Solution:
   
2.     def maxSum(self, nums: list[int]) -> int:
   
3.         # 先找出整个数组的最大值
   
4.         max_val = max(nums)
   
5.         
   
6.         # 边界情况：如果最大值都小于 0，说明全是负数。
   
7.         # 为了让和最大且数组不为空，只能选那个最大的负数。
   
8.         if max_val < 0:
   
9.             return max_val
   
10.             
    
11.         # 正常情况：把所有大于 0 的不重复元素加起来
    
12.         unique_nums = set(nums)
    
13.         return sum(x for x in unique_nums if x > 0)

复制代码

LC. 3477. Fruits Into Baskets II
Easy
Topics
conpanies icon
Companies
Hint
You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the ith type of fruit, and baskets[j] represents the capacity of the jth basket.

From left to right, place the fruits according to these rules:

Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.
Each basket can hold only one type of fruit.
If a fruit type cannot be placed in any basket, it remains unplaced.
Return the number of fruit types that remain unplaced after all possible allocations are made.



Example 1:

Input: fruits = [4,2,5], baskets = [3,5,4]

Output: 1

Explanation:

fruits[0] = 4 is placed in baskets[1] = 5.
fruits[1] = 2 is placed in baskets[0] = 3.
fruits[2] = 5 cannot be placed in baskets[2] = 4.
Since one fruit type remains unplaced, we return 1.

Example 2:

Input: fruits = [3,6,1], baskets = [6,4,7]

Output: 0

Explanation:

fruits[0] = 3 is placed in baskets[0] = 6.
fruits[1] = 6 cannot be placed in baskets[1] = 4 (insufficient capacity) but can be placed in the next available basket, baskets[2] = 7.
fruits[2] = 1 is placed in baskets[1] = 4.
Since all fruits are successfully placed, we return 0.



Constraints:

n == fruits.length == baskets.length
1 <= n <= 100
1 <= fruits[i], baskets[i] <= 1000


我的解法直接模拟，

1. class Solution:
   
2.     def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
   
3. 
   
4.         ans = 0
   
5. 
   
6.         for f in fruits:
   
7.       
   
8.             for i, b in enumerate(baskets):
   
9.                 if b >= f:
   
10.                     break
    
11.             delIndex = -1
    
12.             if baskets[i] >= f:
    
13.                 delIndex = i
    
14.             else:
    
15.                 ans += 1
    
16.             
    
17.             if delIndex != -1: baskets.pop(i)
    
18.         
    
19.         return ans
    
20. 
    
21. 
    
22.         

复制代码

优化

隐患 1：循环变量 i 的作用域泄漏 (Scope Leakage)
你写了这样一段逻辑：

Python
for i, b in enumerate(baskets):
    if b >= f:
        break
delIndex = -1
if baskets[i] >= f:  # <--- 这里依赖了循环结束后的 i
在 Python 中，如果循环正常结束（没有被 break 打断），i 会保留最后一个元素的索引。虽然在这里因为 baskets 不会为空，代码碰巧能运行，但如果 baskets 为空，i 将完全未定义，直接抛出 UnboundLocalError。这在面试中会被认为是不好的编程习惯。

隐患 2：在遍历时使用 .pop(i) 物理删除元素
在数组中间使用 .pop(i) 去删除元素，底层会把该索引后面的所有元素全部向前移动一位。这会导致该操作本身的时间复杂度变为 O(N)。
虽然本题数据量极小（N <= 100），怎么写都能过，但如果 N 是 10^5，这种写法会直接导致 Time Limit Exceeded (超时)。

🧠 核心思路：原地标记 (In-place Marking)
面对“元素用过就作废”的场景，与其去物理删除它（修改数组长度和索引），不如在原地给它打个标记。

题目说 baskets[i] >= 1，那么我们只要把用过的篮子容量改成 -1 或者 0，它就自然变成了一个“废弃”的篮子，后续再大的水果也放不进去了。这样既保留了原数组的索引，又省去了删除元素的开销。

1. class Solution:
   
2.     def numOfUnplacedFruits(self, fruits: list[int], baskets: list[int]) -> int:
   
3.         unplaced = 0
   
4.         
   
5.         for f in fruits:
   
6.             # 标记当前水果是否成功放入篮子
   
7.             placed = False
   
8.             
   
9.             for i in range(len(baskets)):
   
10.                 if baskets[i] >= f:
    
11.                     baskets[i] = -1  # 核心技巧：原地标记为 -1，代表该篮子已作废
    
12.                     placed = True
    
13.                     break  # 找到了最左边的，直接停止搜索
    
14.                     
    
15.             # 如果遍历完所有篮子都没放进去，未放置数量 +1
    
16.             if not placed:
    
17.                 unplaced += 1
    
18.                
    
19.         return unplaced

复制代码

补充内容 (2026-08-13 10:25 +08:00):
进阶思路：线段树 (了解即可，应对面试追问)我们可以用一棵线段树来维护

1. baskets

复制代码

数组中每个区间的最大值（Max Capacity）。

• 查找最左边满足条件的篮子：
  当拿到一个大小为 $f$ 的水果时，我们从线段树的根节点（代表整个数组）开始往下找：
• • 先看左半边区间的最大值是不是 $\ge f$？如果是，说明左边一定有合格的篮子，毫不犹豫往左子树走（保证了“最左边”的要求）。
  • 如果左半边不够大，再看右半边区间的最大值是不是 $\ge f$？如果是，往右子树走。
  • 如果整个根节点的最大值都 $< f$，说明所有篮子都装不下，直接跳过。
• 更新（原地作废）：
  找到那个具体的篮子（叶子节点）后，把它所在位置的值更新为
  1. -1

  复制代码
  ，并一路往上更新线段树区间最大值。

每一次查找和更新的时间复杂度都是严格的 $O(\log N)$，整体时间复杂度完美降到 $O(N \log N)$，且完美保留了原数组的顺序。

补充内容 (2026-08-13 10:27 +08:00):
太棒了！你有主动去啃高级数据结构的意识，这在面试大厂（尤其是字节、谷歌这类喜欢考 Hard 题的公司）是非常核心的竞争力。
线段树（Segment Tree）听起来吓人，但只要你看透它的本质，它其实就是一个“自带导航功能的二叉树”。
针对“找最左边大于等于 $f$ 的篮子并更新”这个需求，我带你一步步拆解并手写这棵线段树。

🧠 1. 核心思路：线段树是怎么“导航”的？
线段树的每个节点，代表原数组的一个区间。我们让每个节点记录它所代表区间的 最大值 (Max)。
假设

1. baskets = [3, 6, 1, 4]

复制代码

，对应的线段树是这样的：
               [0-3] 最大值:6
              /              \
       [0-1] 最大值:6      [2-3] 最大值:4
       /          \        /          \
[0]值:3      [1]值:6  [2]值:1      [3]值:4

现在来了一个水果，大小为

1. f = 4

复制代码

，我们从树根（代表整个数组）开始找，核心逻辑如下：

• 看整个数组最大值：根节点最大值是
  1. 6

  复制代码
  ，说明这四个篮子里肯定有能装下
  1. 4

  复制代码
  的篮子。进树！
• 永远先看左边（保证最左原则）：

• 左半区
  1. [0-1]

  复制代码
  的最大值是
  1. 6 >= 4

  复制代码
  ，说明左边够用！毫不犹豫往左走（哪怕右边也有能装的，我们也不管，因为题目要求最左边）。
• 到了
  1. [0-1]

  复制代码
  ，再看它的左孩子
  1. [0]

  复制代码
  ，最大值是
  1. 3 < 4

  复制代码
  ，装不下！
• 那只能看它的右孩子
  1. [1]

  复制代码
  ，最大值是
  1. 6 >= 4

  复制代码
  ，找到了！

• 找到了，原地销毁：

• 把
  1. [1]

  复制代码
  的值改成
  1. -1

  复制代码
  （代表用废了）。
• 最关键的一步：顺藤摸瓜往上回溯，重新计算途径节点的最大值。因为
  1. [1]

  复制代码
  废了，
  1. [0-1]

  复制代码
  的最大值就变成了
  1. 3

  复制代码
  ，根节点的最大值就变成了
  1. 4

  复制代码
  （由右半区的
  1. 4

  复制代码
  撑场面）。

你看，一次查找 + 更新，只走了一条从根到叶子的路径，高度是 $\log N$，所以时间复杂度是 $O(\log N)$！

✨ 2. 面试标准代码实现 (Python)
在面试中，写线段树最稳妥、最干净的做法是用一维数组来模拟树（类似堆的写法：左孩子是

1. 2*node+1

复制代码

，右孩子是

1. 2*node+2

复制代码

）。标准需要开辟

1. 4 * N

复制代码

的空间。
class SegmentTree:
    def __init__(self, arr: list[int]):
        self.n = len(arr)
        # 线段树的标准空间是原数组大小的 4 倍
        self.tree = [0] * (4 * self.n)
        # 构建线段树
        self.build(arr, 0, 0, self.n - 1)
        
    def build(self, arr: list[int], node: int, start: int, end: int):
        """递归构建线段树，维护每个区间的最大值"""
        # 如果到了叶子节点（具体某一个篮子）
        if start == end:
            self.tree[node] = arr[start]
            return
            
        mid = (start + end) // 2
        left_child = 2 * node + 1
        right_child = 2 * node + 2
        
        # 分别构建左半区和右半区
        self.build(arr, left_child, start, mid)
        self.build(arr, right_child, mid + 1, end)
        
        # 当前节点的最大值 = max(左边最大值, 右边最大值)
        self.tree[node] = max(self.tree[left_child], self.tree[right_child])
        
    def query_and_update(self, node: int, start: int, end: int, f: int) -> int:
        """寻找最左边 >= f 的位置，找到后更新为 -1，返回对应的索引"""
        # 1. 如果当前区间的最大值都比 f 小，说明这片区域全都不行，直接返回 -1
        if self.tree[node] < f:
            return -1
            
        # 2. 如果找到了叶子节点，说明这就是我们要找的那个篮子！
        if start == end:
            self.tree[node] = -1  # 原地作废
            return start
            
        mid = (start + end) // 2
        left_child = 2 * node + 1
        right_child = 2 * node + 2
        
        # 3. 核心机制：优先查左边！只要左边的最大值能满足 f，就死死咬住左边往下走
        if self.tree[left_child] >= f:
            res = self.query_and_update(left_child, start, mid, f)
        else:
            # 左边不行，才勉强去右边找
            res = self.query_and_update(right_child, mid + 1, end, f)
            
        # 4. 重点：底下的叶子节点被修改了，所以要向上回溯，更新当前区间的最大值
        self.tree[node] = max(self.tree[left_child], self.tree[right_child])
        
        return res

class Solution:
    def numOfUnplacedFruits(self, fruits: list[int], baskets: list[int]) -> int:
        n = len(fruits)
        # 初始化线段树
        seg_tree = SegmentTree(baskets)
        unplaced = 0
        
        for f in fruits:
            # 在全区间 [0, n-1] 寻找并更新
            # 我们不需要知道具体放到了哪个索引，只需要知道有没有放成功（!= -1）
            res = seg_tree.query_and_update(0, 0, n - 1, f)
            if res == -1:
                unplaced += 1
               
        return unplaced

📊 3. 复杂度分析与面试实战建议

• 时间复杂度：
• 建树：$O(N)$。要把原数组的值放到树的叶子上并向上汇总，遍历整个树的节点。
• 查询并更新：每个水果花费 $O(\log N)$。有 $N$ 个水果，总共 $O(N \log N)$。
• 整体时间：$O(N \log N)$。完美应对 $N = 10^5$ 的数据量！
• 空间复杂度：$O(N)$。
  1. tree

  复制代码
  数组需要 $4N$ 的空间，属于线性空间复杂度。

💡 面试伴侣的小贴士： 在线上面试时，如果遇到类似的题，第一法则永远是先写出 $O(N^2)$ 的暴力解法保证 AC 或拿到基础分（也就是我们上一轮写的代码）。 只有在以下两种情况，你才需要把这套线段树搬出来：

• 题目数据量明确标识了 $N = 10^5$，暴力法绝对会超时。
• 你写完了暴力法，面试官微笑着问：“代码不错，但如果我们想把它优化到 $O(N \log N)$，你有什么思路吗？” 这时你抛出“由于有寻找最左侧限制，普通的排序二分不可行，我们需要维护区间最大值的线段树来定向剪枝”，面试官绝对会眼前一亮！

这个模板你先消化一下，特别是“优先走左孩子”的这个 if 判断，它是解决“最左边”限制的灵魂。有没看懂的地方随时问我！

LC. 3471. Find the Largest Almost Missing Integer

You are given an integer array nums and an integer k.

An integer x is almost missing from nums if x appears in exactly one subarray of size k within nums.

Return the largest almost missing integer from nums. If no such integer exists, return -1.

A subarray is a contiguous sequence of elements within an array.


Example 1:

Input: nums = [3,9,2,1,7], k = 3

Output: 7

Explanation:

1 appears in 2 subarrays of size 3: [9, 2, 1] and [2, 1, 7].
2 appears in 3 subarrays of size 3: [3, 9, 2], [9, 2, 1], [2, 1, 7].
3 appears in 1 subarray of size 3: [3, 9, 2].
7 appears in 1 subarray of size 3: [2, 1, 7].
9 appears in 2 subarrays of size 3: [3, 9, 2], and [9, 2, 1].
We return 7 since it is the largest integer that appears in exactly one subarray of size k.

Example 2:

Input: nums = [3,9,7,2,1,7], k = 4

Output: 3

Explanation:

1 appears in 2 subarrays of size 4: [9, 7, 2, 1], [7, 2, 1, 7].
2 appears in 3 subarrays of size 4: [3, 9, 7, 2], [9, 7, 2, 1], [7, 2, 1, 7].
3 appears in 1 subarray of size 4: [3, 9, 7, 2].
7 appears in 3 subarrays of size 4: [3, 9, 7, 2], [9, 7, 2, 1], [7, 2, 1, 7].
9 appears in 2 subarrays of size 4: [3, 9, 7, 2], [9, 7, 2, 1].
We return 3 since it is the largest and only integer that appears in exactly one subarray of size k.

Example 3:

Input: nums = [0,0], k = 1

Output: -1

Explanation:

There is no integer that appears in only one subarray of size 1.



Constraints:

1 <= nums.length <= 50
0 <= nums[i] <= 50
1 <= k <= nums.length

1. 拆解题意与核心规律题目要求找出一个刚好只在 1 个长度为 $k$ 的子数组中出现过的最大整数。通过分析一个元素会被多少个长度为 $k$ 的子数组覆盖，我们可以得出三种情况（这也是你代码里的核心逻辑）：$k == n$：整个数组就只有 1 个长度为 $k$ 的子数组。所以所有元素都只出现在这 1 个子数组里，直接返回 max(nums) 即可。$k == 1$：子数组长度为 1，意味着如果一个数在 nums 里出现了多次，它就会出现在多个子数组里。所以我们要找的其实就是在原数组中只出现过 1 次的最大元素。$1 < k < n$（重点）：任何在中间位置（索引 $0 < i < n-1$）的元素，必定会被至少两个长度为 $k$ 的子数组覆盖。只有最左边 nums[0] 和最右边 nums[n-1]，且它们在整个数组中全局频次为 1 的情况下，它们才会被刚好 1 个子数组（最左边的子数组 / 最右边的子数组）覆盖。所以这个情况的候选人，只有可能是 nums[0] 和 nums[-1]。你的思路完全正确且是最优的！

1. class Solution:
   
2.     def largestInteger(self, nums: List[int], k: int) -> int:
   
3.         if len(nums) == k: return max(nums)
   
4.         if k == 1:
   
5.             freq = Counter(nums)
   
6.             keys = list(freq.keys())
   
7.             keys.sort()
   
8.             for i in range(len(keys)-1, -1, -1):
   
9.                 if freq[keys[i]] == 1:
   
10.                     return keys[i]
    
11.             return -1
    
12.         freq = Counter(nums)
    
13. 
    
14. 
    
15. 
    
16.         ans = []
    
17. 
    
18.         if freq[nums[0]] == 1: ans.append(nums[0])
    
19.         if freq[nums[-1]] == 1: ans.append(nums[-1])
    
20. 
    
21.         if not ans:
    
22.             return -1
    
23.         else:
    
24.             return max(ans)
    
25.         

复制代码

优化

把求 k==1 时的最大值简化成了一行：max((x for x in freq if freq[x] == 1), default=-1)。不用去排序然后再倒序遍历，max() 底层也是 $O(N)$，而且代码极其清晰。去掉了不必要的 keys 列表转换，减少了空间复杂度。把最后的 ans 列表改为了一个单纯的整数变量比较，逻辑更紧凑。

1. from typing import List
   
2. from collections import Counter
   
3. 
   
4. class Solution:
   
5.     def largestInteger(self, nums: List[int], k: int) -> int:
   
6.         n = len(nums)
   
7.         # 情况 1：k 等于数组长度
   
8.         if k == n:
   
9.             return max(nums)
   
10.             
    
11.         freq = Counter(nums)
    
12.         
    
13.         # 情况 2：k 等于 1，找全局只出现 1 次的最大值
    
14.         if k == 1:
    
15.             # 生成器表达式过滤频次为 1 的数，default=-1 避免报错
    
16.             return max((x for x in freq if freq[x] == 1), default=-1)
    
17. 
    
18.         # 情况 3：1 < k < n，候选人只有 nums[0] 和 nums[-1]
    
19.         ans = -1
    
20.         if freq[nums[0]] == 1:
    
21.             ans = max(ans, nums[0])
    
22.         if freq[nums[-1]] == 1:
    
23.             ans = max(ans, nums[-1])
    
24.             
    
25.         return ans

复制代码

通用解法（滑动窗口 / 暴力模拟）

因为这题数据范围只有 $N \le 50$，暴力模拟每一个滑动窗口其实是 $O(N \cdot K)$ 的复杂度，在 $50 \times 50 = 2500$ 次操作内，这不仅没问题，而且是非常通用的算法模型。通用解法代码：

1. class Solution:
   
2.     def largestInteger(self, nums: List[int], k: int) -> int:
   
3.         n = len(nums)
   
4.         # 统计每个数字出现在了多少个【不同的】子数组中
   
5.         subarray_count = Counter()
   
6.         
   
7.         # 遍历所有长度为 k 的子数组起始点
   
8.         for i in range(n - k + 1):
   
9.             window = nums[i : i+k]
   
10.             # 同一个子数组内的重复元素只算一次，所以用 set 去重
    
11.             for num in set(window):
    
12.                 subarray_count[num] += 1
    
13.                
    
14.         # 找出只出现在 1 个子数组中的最大值
    
15.         return max((num for num, count in subarray_count.items() if count == 1), default=-1)

复制代码

LC. 3467. Transform Array by Parity

You are given an integer array nums. Transform nums by performing the following operations in the exact order specified:

Replace each even number with 0.
Replace each odd numbers with 1.
Sort the modified array in non-decreasing order.
Return the resulting array after performing these operations.



Example 1:

Input: nums = [4,3,2,1]

Output: [0,0,1,1]

Explanation:

Replace the even numbers (4 and 2) with 0 and the odd numbers (3 and 1) with 1. Now, nums = [0, 1, 0, 1].
After sorting nums in non-descending order, nums = [0, 0, 1, 1].
Example 2:

Input: nums = [1,5,1,4,2]

Output: [0,0,1,1,1]

Explanation:

Replace the even numbers (4 and 2) with 0 and the odd numbers (1, 5 and 1) with 1. Now, nums = [1, 1, 1, 0, 0].
After sorting nums in non-descending order, nums = [0, 0, 1, 1, 1].


Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 1000

非常简单，本质上是在求奇偶的个数。

1. class Solution:
   
2.     def transformArray(self, nums: List[int]) -> List[int]:
   
3.         countEven, countOdd = 0, 0
   
4. 
   
5.         for num in nums:
   
6.             if num % 2 == 0:
   
7.                 countEven += 1
   
8.             else:
   
9.                 countOdd += 1
   
10.             
    
11.         return [0] * countEven + [1] * countOdd

复制代码

一个我感觉不算优化的小 trick，

1. class Solution:
   
2.     def transformArray(self, nums: List[int]) -> List[int]:
   
3.         n = len(nums)
   
4.         # 统计奇数（变成 1）的个数
   
5.         # 生成器表达式 x % 2，避免了显式写 for 循环，更加 Pythonic
   
6.         countOdd = sum(x % 2 for x in nums)
   
7.         
   
8.         # 偶数的个数自然就是总长度减去奇数的个数
   
9.         countEven = n - countOdd
   
10.         
    
11.         # 拼装返回
    
12.         return [0] * countEven + [1] * countOdd

复制代码

LC. 3005. Count Elements With Maximum Frequency

You are given an array nums consisting of positive integers.

Return the total frequencies of elements in nums such that those elements all have the maximum frequency.

The frequency of an element is the number of occurrences of that element in the array.



Example 1:

Input: nums = [1,2,2,3,1,4]
Output: 4
Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array.
So the number of elements in the array with maximum frequency is 4.
Example 2:

Input: nums = [1,2,3,4,5]
Output: 5
Explanation: All elements of the array have a frequency of 1 which is the maximum.
So the number of elements in the array with maximum frequency is 5.


Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

我的解法，多变遍历

1. class Solution:
   
2.     def maxFrequencyElements(self, nums: List[int]) -> int:
   
3.         freq = Counter(nums)
   
4.         max_freq = max(freq.values())
   
5. 
   
6.         ans = 0
   
7. 
   
8.         for v in freq:
   
9.             if freq[v] == max_freq:
   
10.                 ans += max_freq
    
11.         
    
12.         return ans
    
13.         

复制代码

优化的同样思路的写法

1. from collections import Counter
   
2. from typing import List
   
3. 
   
4. class Solution:
   
5.     def maxFrequencyElements(self, nums: List[int]) -> int:
   
6.         freq = Counter(nums)
   
7.         max_freq = max(freq.values())
   
8.         
   
9.         # 生成器表达式：遍历所有频次，如果等于最大频次，就累加
   
10.         return sum(f for f in freq.values() if f == max_freq)

复制代码

更加优化的写法， 一次遍历！

核心思路：在遍历数组、累加频率的同时，动态维护当前的 max_freq 和 ans。

如果发现某个数字的频率 大于 当前的 max_freq，说明之前的 ans 都作废了，我们要更新 max_freq，并且把 ans 重置为当前频率。

如果发现某个数字的频率 等于 当前的 max_freq，说明它也是最大频率的候选人，把它的频率累加到 ans 中。

一次遍历代码实现

1. class Solution:
   
2.     def maxFrequencyElements(self, nums: List[int]) -> int:
   
3.         freq = {}
   
4.         max_freq = 0
   
5.         ans = 0
   
6.         
   
7.         for num in nums:
   
8.             # 1. 更新当前数字的频次
   
9.             freq[num] = freq.get(num, 0) + 1
   
10.             cur_freq = freq[num]
    
11.             
    
12.             # 2. 动态维护最大频次和答案
    
13.             if cur_freq > max_freq:
    
14.                 max_freq = cur_freq
    
15.                 ans = cur_freq       # 出现更大的频次，之前的 ans 作废，重新洗牌
    
16.             elif cur_freq == max_freq:
    
17.                 ans += cur_freq      # 和当前最大频次一样，累加到 ans 中
    
18.                
    
19.         return ans

复制代码

LC. 3465. Find Products with Valid Serial Numbers
Easy
Topics
SQL Schema
Pandas Schema
Table: products

+--------------+------------+
| Column Name  | Type       |
+--------------+------------+
| product_id   | int        |
| product_name | varchar    |
| description  | varchar    |
+--------------+------------+
(product_id) is the unique key for this table.
Each row in the table represents a product with its unique ID, name, and description.
Write a solution to find all products whose description contains a valid serial number pattern. A valid serial number follows these rules:

It starts with the letters SN (case-sensitive).
Followed by exactly 4 digits.
It must have a hyphen (-) followed by exactly 4 digits.
The serial number must be within the description (it may not necessarily start at the beginning).
Return the result table ordered by product_id in ascending order.

The result format is in the following example.



Example:

Input:

products table:

+------------+--------------+------------------------------------------------------+
| product_id | product_name | description                                          |
+------------+--------------+------------------------------------------------------+
| 1          | Widget A     | This is a sample product with SN1234-5678            |
| 2          | Widget B     | A product with serial SN9876-1234 in the description |
| 3          | Widget C     | Product SN1234-56789 is available now                |
| 4          | Widget D     | No serial number here                                |
| 5          | Widget E     | Check out SN4321-8765 in this description            |
+------------+--------------+------------------------------------------------------+
   
Output:

+------------+--------------+------------------------------------------------------+
| product_id | product_name | description                                          |
+------------+--------------+------------------------------------------------------+
| 1          | Widget A     | This is a sample product with SN1234-5678            |
| 2          | Widget B     | A product with serial SN9876-1234 in the description |
| 5          | Widget E     | Check out SN4321-8765 in this description            |
+------------+--------------+------------------------------------------------------+
   
Explanation:

Product 1: Valid serial number SN1234-5678
Product 2: Valid serial number SN9876-1234
Product 3: Invalid serial number SN1234-56789 (contains 5 digits after the hyphen)
Product 4: No serial number in the description
Product 5: Valid serial number SN4321-8765
The result table is ordered by product_id in ascending order.

1. 
   
2. 
   
3. SELECT product_id, product_name, description
   
4. FROM products
   
5. WHERE REGEXP_LIKE(description, '\\bSN[0-9]{4}-[0-9]{4}\\b', 'c')
   
6. ORDER BY product_id ASC;
   
7. 
   

复制代码

How it Works:
REGEXP_LIKE() is used to perform a regular expression match on the description column.

'\\b' specifies a word boundary. This ensures we don't accidentally match strings where the pattern is embedded within a longer sequence (e.g., it prevents matching "ASN1234-5678" or "SN1234-56789").

SN matches the literal characters "SN".

[0-9]{4} ensures there are exactly 4 digits before the hyphen.

- matches the literal hyphen.

[0-9]{4} ensures exactly 4 digits follow the hyphen.

'c' is passed as the third argument to force the match to be case-sensitive, strictly ensuring it looks for a capital "SN" and not "sn".

ORDER BY product_id ASC sorts the final output exactly as requested.