刷题记录帖子

卡车数量有限且要求正好装满（状态压缩 DP / 背包问题）—— LeetCode Hard 难度

在真实的高难度面试中（比如类似 LC 698. 划分为k个相等的子集 或 LC 1723. 完成所有工作的最短时间），面试官会加一个限制：“切出来的碎块必须正好能被现有的卡车装下，不能存在剩下一小截木头找不到卡车装的死局”。

此时，单纯的贪心可能会陷入局部最优解（比如贪心切了一个最大块，导致剩下的碎片太零散，没法放进剩余的小卡车里）。

状态压缩 DP（Bitmask DP）是解决 NP-Hard 数组划分、资源分配、旅行商问题（TSP） 的终极武器。当贪心算法因为“局部最优解导致空间死锁”而失效时，位运算结合动态规划是唯一能在面试中写出绝对正确解的方法。
我们用与上一讲“卡车装木头”完美契合的经典高频面试题——LeetCode 698. 划分为k个相等的子集（Partition to K Equal Sum Subsets），来彻底讲透二进制状压 DP 的模型与标准代码。

1. 拆解题意 & 避坑指南

题目复盘（LC 698）
给你一个整数数组

1. nums

复制代码

和一个正整数

1. k

复制代码

，找出是否有可能把这个数组分成

1. k

复制代码

个非空子集，其总和都相等。
怎么看出来要用 Bitmask DP？（最强信号）
在 LeetCode 和大厂面试中，只要看到以下两个特征同时出现，100% 是状态压缩 DP 或回溯搜索：

• 数据规模极小：数组长度 N  < 20（本题 N < 16）。
• 每个元素只有“选”或“不选”两种状态，且需要做全局最优组合。

因为 2^{16} = 65536，状态数非常少，用一个 16 位的二进制整数（

1. 0

复制代码

到

1. 65535

复制代码

）就能完美记录所有数字被装入卡车（子集）的情况！

容易踩的坑

• 贪心失效：不能每次凑满一个桶再凑下一个。比如
  1. nums = [4, 3, 2, 3, 5, 2, 1], k = 4

  复制代码
  ，如果先用贪心凑
  1. 5+1=6

  复制代码
  和
  1. 4+2=6

  复制代码
  ，剩下的
  1. 3, 3, 2

  复制代码
  就彻底死锁了。必须同时维护全局组合状态。
• 位运算优先级：在 Python 中，位运算（如
  1. <<

  复制代码
  ,
  1. &

  复制代码
  ,
  1. |

  复制代码
  ）的优先级低于比较运算符（如
  1. ==

  复制代码
  ,
  1. <=

  复制代码
  ）。写代码时务必给位运算加上括号，例如
  1. (mask & (1 << i)) == 0

  复制代码
  ，否则很容易产生极难排查的 Bug。

核心算法模型与状态定义二进制如何映射数组？

假设 nums = [4, 3, 2, 3]（长度 $N=4$）：

二进制 0000（十进制 0）：代表一个数字都没拿。
二进制 0101（十进制 5）：代表拿了第 0 个和第 2 个数字（从右往左第 0 位和第 2 位是 1）。
二进制 1111（十进制 15）：代表所有数字都被装进了桶里。

状态转移方程我们不需要记录当前填到第几个桶，只需要记录“当前正在填的这个桶，已经累计了多少容量”。

定义一维数组 dp[mask]：表示在使用了组合状态为 mask 的数字后，当前未填满的那个桶里，累计的数字和是多少。

如果 dp[mask] == -1，说明这个组合状态本身是绝对不可行的（无法由前面的合法状态转移过来）。

转移逻辑：

遍历当前状态 mask 下所有还没被选择的数字 nums[i]（即 mask 的第 i 位为 0）：如果 dp[mask] + nums[i] <= target（当前桶还能装下）：

新状态 new_mask = mask | (1 << i)
dp[new_mask] = (dp[mask] + nums[i]) % target（如果正好等于 target，取模后变成 0，自动代表开始填下一个新桶）。

from typing import List

class Solution: def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:

    total_sum = sum(nums)

    # 1. 基础特判与数学剪枝
    if total_sum % k != 0:
        return False
    target = total_sum // k
   
    # 降序排序是位运算 DP 和回溯最关键的剪枝！
    # 让最大的数字先尝试装桶，如果太远超 target 可以迅速退出，大幅减少无效状态
    nums.sort(reverse=True)
    if nums[0] > target:
        return False
        
    n = len(nums)
    # 共有 2^n 种二进制状态，0 表示全不选，(1<<n)-1 表示全选
    # dp[mask] 存储当前状态下，正在填的桶已经占用的容量。-1 表示该状态不可达。
    dp = [-1] * (1 << n)
   
    # 初始状态：什么都没选，当前桶占用容量为 0
    dp[0] = 0
   
    # 2. 状态压缩 DP 核心循环
    for mask in range(1 << n):
        # 如果当前状态不可达，直接跳过
        if dp[mask] == -1:
            continue
            
        # 尝试在当前状态的基础上，再多拿一个数字 nums[i]
        for i in range(n):
            # 检查 mask 的第 i 位是否为 0 (代表 nums[i] 还没被用过)
            if not (mask & (1 << i)):
                # 如果把 nums[i] 放进当前桶不会溢出
                if dp[mask] + nums[i] <= target:
                    # 产生新的状态：利用按位或 (|) 把第 i 位置为 1
                    new_mask = mask | (1 << i)
                    
                    # 重点技巧：通过 % target，当恰好填满一个桶时，占用容量自动归零，
                    # 从而平滑地开启下一个新桶的拼接
                    dp[new_mask] = (dp[mask] + nums[i]) % target
                else:
                    # 因为 nums 已经降序排序，如果当前 nums[i] 放不下，
                    # 那么再后面的数字肯定更小，也许能放下，不能 break，要继续看下一个 i
                    pass
                    
    # 最终检查全选状态 ((1 << n) - 1) 是否可达，且最后容量归零（正好分完 k 个桶）
    return dp[(1 << n) - 1] == 0

3550. Smallest Index With Digit Sum Equal to Index

Python 解法

1. class Solution:
   
2.     def smallestIndex(self, nums: List[int]) -> int:
   
3.         def getDigitsSum(n):
   
4.             return sum(int(ch) for ch in str(n))
   
5.         
   
6.         for i in range(len(nums)):
   
7.             if i == getDigitsSum(nums[i]):
   
8.                 return i
   
9.         
   
10.         return -1
    
11.         
    

复制代码

当然纯数学的解法

1. class Solution:
   
2.     def smallestIndex(self, nums: List[int]) -> int:
   
3.         def getDigitsSum(n: int) -> int:
   
4.             if n == 0:
   
5.                 return 0
   
6.             total = 0
   
7.             while n > 0:
   
8.                 total += n % 10  # 取出当前最右边的一位（个位）
   
9.                 n //= 10         # 砍掉最右边的一位
   
10.             return total
    
11. 
    
12.         for i, num in enumerate(nums):
    
13.             if i == getDigitsSum(num):
    
14.                 return i
    
15.         return -1

复制代码

LC. 3550. Smallest Index With Digit Sum Equal to Index

You are given an integer array nums.

Return the smallest index i such that the sum of the digits of nums[i] is equal to i.

If no such index exists, return -1.



Example 1:

Input: nums = [1,3,2]

Output: 2

Explanation:

For nums[2] = 2, the sum of digits is 2, which is equal to index i = 2. Thus, the output is 2.
Example 2:

Input: nums = [1,10,11]

Output: 1

Explanation:

For nums[1] = 10, the sum of digits is 1 + 0 = 1, which is equal to index i = 1.
For nums[2] = 11, the sum of digits is 1 + 1 = 2, which is equal to index i = 2.
Since index 1 is the smallest, the output is 1.
Example 3:

Input: nums = [1,2,3]

Output: -1

Explanation:

Since no index satisfies the condition, the output is -1.


Constraints:

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

很有意思的题目，发现 Leetcode 老题目确实比新题目有意思。
情况 A（全是正数）：既然全是正数，那么最大的三个数 nums[-1] * nums[-2] * nums[-3] 一定比最小的三个数乘积更大。

情况 B（全是负数）：三个负数相乘结果是负数。在负数世界里，绝对值越小的值越大（比如 $-6 > -720$）。因此，最靠近 0 的三个最大负数 nums[-1] * nums[-2] * nums[-3] 一定大于最靠左的三个最小负数。

情况 C（有正有负）：如果一正两负，或者两正一负，nums[0] * nums[1] * nums[-1]（两个最小负数 $\times$ 最大正数）一定比三个靠左的数相乘更大或更优。

1. class Solution:
   
2.     def maximumProduct(self, nums: List[int]) -> int:
   
3.         nums.sort()
   
4.         # 结果只可能在两组候选人中产生：
   
5.         # 1. 最大的三个数相乘
   
6.         # 2. 最小的两个数（可能为大负数）* 最大的一个数
   
7.         return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])

复制代码

LC. 3545. Minimum Deletions for At Most K Distinct Characters

贪心算法，统计频率，删掉最少的频率即可。

不过我写的时候不太顺手，这里需要考虑不少数据结构到底是怎么样的，做到心中有数。

1. class Solution:
   
2.     def minDeletion(self, s: str, k: int) -> int:
   
3.         freq = Counter(s)
   
4. 
   
5.         freq_list = [freq[key] for key in freq]
   
6.         freq_list.sort(reverse = True)
   
7. 
   
8.         return sum(freq_list[f] for f in range(k, len(freq_list)))
   

复制代码

不过代码可以简化

比如，freq.values() 可以直接取出字典所有的 values

1. from collections import Counter
   
2. 
   
3. class Solution:
   
4.     def minDeletion(self, s: str, k: int) -> int:
   
5.         # 1. 统计每个字符的出现频率
   
6.         freq = Counter(s)
   
7.         
   
8.         # 2. 将频率从大到小排序
   
9.         freq_list = sorted(freq.values(), reverse=True)
   
10.         
    
11.         # 3. 保留前 k 个高频字符，其余低频字符全部删光
    
12.         return sum(freq_list[k:])

复制代码

LC. 1481. Least Number of Unique Integers after K Removals
Solved
Medium
Topics
conpanies icon
Companies
Hint
Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.



Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.
Example 2:
Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.


Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length

和上一题类似，只不过逻辑反过来，算最少的 freq 这样保留尽可能多的 freq 的相同 element

1. class Solution:
   
2.     def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
   
3.         freq = Counter(arr)
   
4.         freq_values = sorted(freq.values())
   
5.         n = len(freq_values)
   
6.         tmp = 0
   
7.         ans = 0
   
8. 
   
9.         for v in freq_values:
   
10.             tmp += v
    
11.             if tmp <= k:
    
12.                 ans += 1
    
13. 
    
14.             if tmp >= k: break
    
15. 
    
16.         return n - ans            
    
17. 
    

复制代码

不过我的代码可以精简

1. from collections import Counter
   
2. from typing import List
   
3. 
   
4. class Solution:
   
5.     def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
   
6.         # 1. 统计每个数字的出现频率
   
7.         freq = Counter(arr)
   
8.         
   
9.         # 2. 将频率从小到大排序（优先处理出现次数少的）
   
10.         freq_values = sorted(freq.values())
    
11.         
    
12.         # 3. 贪心消耗 k
    
13.         removed_types = 0
    
14.         for count in freq_values:
    
15.             if k >= count:
    
16.                 k -= count          # 消耗 k 删光当前数字
    
17.                 removed_types += 1  # 成功消灭一个种类
    
18.             else:
    
19.                 break               # k 不够删光当前数字了，直接终止
    
20.                
    
21.         # 4. 剩余种类 = 总种类 - 已消灭种类
    
22.         return len(freq_values) - removed_types

复制代码

这个统计代码删除类的方式比我的简洁明了

1. removed_types = 0
   
2.         for count in freq_values:
   
3.             if k >= count:
   
4.                 k -= count          # 消耗 k 删光当前数字
   
5.                 removed_types += 1  # 成功消灭一个种类
   
6.             else:
   
7.                 break               # k 不够删光当前数字了，直接终止

复制代码

LC. 3541. Find Most Frequent Vowel and Consonant

1. class Solution:
   
2.     def maxFreqSum(self, s: str) -> int:
   
3.         vowel_dict = defaultdict(int)
   
4.         conso_dict = defaultdict(int)
   
5.         max_v, max_c = 0, 0
   
6. 
   
7. 
   
8.         for ch in s:
   
9.             if ch in ('a', 'e', 'i', 'o', 'u'):
   
10.                 vowel_dict[ch] += 1
    
11.                 max_v = max(max_v, vowel_dict[ch])
    
12.             else:
    
13.                 conso_dict[ch] += 1
    
14.                 max_c = max(max_c, conso_dict[ch])
    
15. 
    
16.         return max_v + max_c        
    

复制代码

优化下另外一种解法，

在 Python 刷题和实际开发中，遇到“词频统计”需求，我们最常用的是 collections.Counter。面试中如果你想用更 Pythonic 的方式，可以先全局统计，再分流处理：

1. from collections import Counter
   
2. 
   
3. class Solution:
   
4.     def maxFreqSum(self, s: str) -> int:
   
5.         counts = Counter(s)  # 一次性统计所有字符的频次
   
6.         vowels = set("aeiou")
   
7.         
   
8.         max_v = 0
   
9.         max_c = 0
   
10.         
    
11.         # 遍历统计完的字典，字典大小最多 26，速度极快
    
12.         for ch, freq in counts.items():
    
13.             if ch in vowels:
    
14.                 max_v = max(max_v, freq)
    
15.             else:
    
16.                 max_c = max(max_c, freq)
    
17.                
    
18.         return max_v + max_c

复制代码

LC. 3536. Maximum Product of Two Digits
Solved
Easy
Topics
conpanies icon
Companies
Hint
You are given a positive integer n.

Return the maximum product of any two digits in n.

Note: You may use the same digit twice if it appears more than once in n.



Example 1:

Input: n = 31

Output: 3

Explanation:

The digits of n are [3, 1].
The possible products of any two digits are: 3 * 1 = 3.
The maximum product is 3.
Example 2:

Input: n = 22

Output: 4

Explanation:

The digits of n are [2, 2].
The possible products of any two digits are: 2 * 2 = 4.
The maximum product is 4.
Example 3:

Input: n = 124

Output: 8

Explanation:

The digits of n are [1, 2, 4].
The possible products of any two digits are: 1 * 2 = 2, 1 * 4 = 4, 2 * 4 = 8.
The maximum product is 8.


Constraints:

10 <= n <= 109

我的解法

1. class Solution:
   
2.     def maxProduct(self, n: int) -> int:
   
3.         slist = [int(ch) for ch in str(n)]
   
4.         slist.sort()
   
5.         return slist[-1] * slist[-2]

复制代码

优化，可以动态维护 first， second 变量，

1. class Solution:
   
2. 
   
3.     def maxProduct(self, n: int) -> int:
   
4.         first, second = 0, 0
   
5. 
   
6.         for ch in str(n):
   
7.             digit = int(ch)
   
8.             if digit > first:
   
9.                 # 遇到比最大值还大的，把旧的最大值移位给次大值
   
10.                 second = first
    
11.                 first = digit
    
12.             elif digit > second:
    
13.                 # 介于最大值和次大值之间
    
14.                 second = digit
    
15. 
    
16.         return first * second

复制代码

或者不能用 string 的时候手动写整除 10， 和取余数。

1. class Solution:
   
2. 
   
3.     def maxProduct(self, n: int) -> int:
   
4.         first, second = 0, 0
   
5. 
   
6.         while n > 0:
   
7.             digit = n % 10  # 取最右边一位
   
8.             n //= 10  # 砍掉最右边一位
   
9. 
   
10.             if digit > first:
    
11.                 second = first
    
12.                 first = digit
    
13.             elif digit > second:
    
14.                 second = digit
    
15. 
    
16.         return first * second

复制代码

LC. 3516. Find Closest Person
Solved
Easy
Topics
conpanies icon
Companies
Hint
You are given three integers x, y, and z, representing the positions of three people on a number line:

x is the position of Person 1.
y is the position of Person 2.
z is the position of Person 3, who does not move.
Both Person 1 and Person 2 move toward Person 3 at the same speed.

Determine which person reaches Person 3 first:

Return 1 if Person 1 arrives first.
Return 2 if Person 2 arrives first.
Return 0 if both arrive at the same time.
Return the result accordingly.



Example 1:

Input: x = 2, y = 7, z = 4

Output: 1

Explanation:

Person 1 is at position 2 and can reach Person 3 (at position 4) in 2 steps.
Person 2 is at position 7 and can reach Person 3 in 3 steps.
Since Person 1 reaches Person 3 first, the output is 1.

Example 2:

Input: x = 2, y = 5, z = 6

Output: 2

Explanation:

Person 1 is at position 2 and can reach Person 3 (at position 6) in 4 steps.
Person 2 is at position 5 and can reach Person 3 in 1 step.
Since Person 2 reaches Person 3 first, the output is 2.

Example 3:

Input: x = 1, y = 5, z = 3

Output: 0

Explanation:

Person 1 is at position 1 and can reach Person 3 (at position 3) in 2 steps.
Person 2 is at position 5 and can reach Person 3 in 2 steps.
Since both Person 1 and Person 2 reach Person 3 at the same time, the output is 0.



Constraints:

1 <= x, y, z <= 100

我的解法

1. class Solution:
   
2.     def findClosest(self, x: int, y: int, z: int) -> int:
   
3.         s1 = abs(x - z)
   
4.         s2 = abs(y - z)
   
5. 
   
6.         if s1 < s2:
   
7.             return 1
   
8.         elif s1 > s2:
   
9.             return 2
   
10.         else:
    
11.             return 0

复制代码

变体写法：用减法判定（数学等价）
有的程序员喜欢用两距离之差来做条件判断, 不算优化，但是是一种写法。

1. class Solution:
   
2.     def findClosest(self, x: int, y: int, z: int) -> int:
   
3.         diff = abs(x - z) - abs(y - z)
   
4.         if diff < 0:
   
5.             return 1
   
6.         elif diff > 0:
   
7.             return 2
   
8.         return 0

复制代码

LC. 3512. Minimum Operations to Make Array Sum Divisible by K
Solved
Easy
Topics
conpanies icon
Companies
Hint
You are given an integer array nums and an integer k. You can perform the following operation any number of times:

Select an index i and replace nums[i] with nums[i] - 1.
Return the minimum number of operations required to make the sum of the array divisible by k.

Example 1:

Input: nums = [3,9,7], k = 5

Output: 4

Explanation:

Perform 4 operations on nums[1] = 9. Now, nums = [3, 5, 7].
The sum is 15, which is divisible by 5.
Example 2:

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

Output: 0

Explanation:

The sum is 8, which is already divisible by 4. Hence, no operations are needed.
Example 3:

Input: nums = [3,2], k = 6

Output: 5

Explanation:

Perform 3 operations on nums[0] = 3 and 2 operations on nums[1] = 2. Now, nums = [0, 0].
The sum is 0, which is divisible by 6.

Constraints:

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

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        s = sum(nums)
        n = s // k

        return s - n * k        

优化， 其实这个就是取模 % 的定义公式，

s - (s // k) * k

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        return sum(nums) % k

LC. 4000. Largest Integer With Given Digit Sum

挺有意思一道题目, 贪心（Greedy），需要考虑边界 edge case，然后其实就是根据 digital sum，填 9 和小 9 的数直接到首位，然后长度不够填 0.

题目目标：构造一个最多包含 n 位数，且各位数字之和恰好为 s 的最大整数。

贪心策略：
要让一个数字最大，我们需要满足两个条件：

位数尽可能多：题目说“最多 n 位”，那我们就把它拉满到 n 位。位数越长，数字越大（比如 90 > 9）。

高位尽可能大：从最高位（最左边）开始，尽量填入最大的数字 9。

1. class Solution:
   
2.     def largestInteger(self, n: int, s: int) -> int:
   
3.         if s == 0: return 0
   
4.         if 9 * n < s: return -1
   
5.         ans = []
   
6.         
   
7.         while s > 0:
   
8.             if s >= 9:
   
9.                 ans.append('9')
   
10.                 s -= 9
    
11.             else:
    
12.                 ans.append(str(s))
    
13.                 s = 0
    
14.         
    
15.         while len(ans) < n:
    
16.             ans.append('0')
    
17.         
    
18.         return int("".join(ans))
    
19.         
    

复制代码

在 Python 中，我们可以利用数学运算（整除和取余）以及字符串乘法，把代码写得更加优雅和紧凑，这在面试中能展现出你对语言特性的熟练度。

1. class Solution:
   
2.     def largestInteger(self, n: int, s: int) -> int:
   
3.         # 特判：如果 s 为 0，直接返回 0
   
4.         if s == 0:
   
5.             return 0
   
6.         
   
7.         # 如果 s 超过了 n 位数能表示的最大和，无解
   
8.         if s > 9 * n:
   
9.             return -1
   
10.         
    
11.         # 计算需要多少个 '9'，以及最后一位非 '9' 的数字是什么
    
12.         # 例如 s = 20, 20 // 9 = 2 个 '9', 20 % 9 = 2
    
13.         count_9 = s // 9
    
14.         remainder = s % 9
    
15.         
    
16.         # 拼接字符串：先放满 '9'
    
17.         ans = "9" * count_9
    
18.         
    
19.         # 如果有余数，拼接到后面
    
20.         if remainder > 0:
    
21.             ans += str(remainder)
    
22.             
    
23.         # 剩下的位数，全部用 '0' 补齐
    
24.         ans += "0" * (n - len(ans))
    
25.         
    
26.         return int(ans)

复制代码