codeforces-go 题解:LeetCode 1742「盒子中小球的最大数量」——从暴力枚举到数位 DP 的三级进阶
codeforces-go 题解:LeetCode 1742「盒子中小球的最大数量」——从暴力枚举到数位 DP 的三级进阶
导读
本篇基于 codeforces-go 仓库中 leetcode/weekly/226/a/1742.md 的官方题解,完整拆解 LeetCode 第 226 场周赛 A 题「盒子中小球的最大数量」的三套解法:暴力枚举、预处理前缀和、上下界数位 DP。文章不仅逐行讲解三种做法的思路与复杂度,还会结合仓库内同题目的 Go 实现 a.go、自动化测试 a_test.go 以及 copypasta/dp.go 中的数位 DP 通用模板,让你既能快速 AC 本题,也能把"枚举数位和 + 计数"的套路迁移到 10^18 级别的进阶场景。
题目回顾
你在一家生产小球的玩具厂工作。有
n个小球,编号从lowLimit到highLimit(即编号为lowLimit, lowLimit+1, ..., highLimit)。无限个盒子,编号从1到无穷。将第i个小球放入编号为i的数位和对应的盒子中(如编号321的小球放入盒子3+2+1=6)。返回被放入小球数量最多的盒子中有几个小球。
题目的数据范围是 1 <= lowLimit <= highLimit <= 10^5。关键观察在于:数位和的范围是有限的——99999 的数位和最大,为 45,因此盒子编号只需要关心 1..45,这为三种解法都奠定了基础。
仓库中本题的测试数据见 a_test.go,包含 [1,10] → 2、[5,15] → 2、[19,28] → 2 三组样例,并留有"测试入参最小的情况"的 TODO。
方法一:暴力枚举
思路:遍历 [lowLimit, highLimit] 中的每个整数 i,计算 i 的数位和 s,用数组(或哈希表)统计 s 的出现次数 cnt[s]。最后返回 cnt[s] 的最大值。
计算数位和有两种方式:
- 转成字符串:
sum(map(int, str(i))),Python 写法最简洁; - 逐位除以 10:不断把
i除以10直到0,例如123 → 12 → 1 → 0,这个过程中把个位数(模10)相加,就是数位和。这是 Java/C++/Go 的通用写法,避免了字符串分配的开销。
class Solution:
def countBalls(self, lowLimit: int, highLimit: int) -> int:
cnt = Counter(
sum(map(int, str(i))) for i in range(lowLimit, highLimit + 1)
)
return max(cnt.values())
class Solution {
public int countBalls(int lowLimit, int highLimit) {
int ans = 0;
int[] cnt = new int[46]; // 99999 的数位和 = 45
for (int i = lowLimit; i <= highLimit; i++) {
int s = 0;
for (int x = i; x > 0; x /= 10) {
s += x % 10;
}
cnt[s]++;
ans = Math.max(ans, cnt[s]);
}
return ans;
}
}
class Solution {
public:
int countBalls(int lowLimit, int highLimit) {
int cnt[46]{}; // 99999 的数位和 = 45
for (int i = lowLimit; i <= highLimit; i++) {
int s = 0;
for (int x = i; x > 0; x /= 10) {
s += x % 10;
}
cnt[s]++;
}
return ranges::max(cnt);
}
};
func countBalls(lowLimit, highLimit int) (ans int) {
cnt := [46]int{} // 99999 的数位和 = 45
for i := lowLimit; i <= highLimit; i++ {
s := 0
for x := i; x > 0; x /= 10 {
s += x % 10
}
cnt[s]++
ans = max(ans, cnt[s])
}
return
}
仓库 a.go 中的 countBalls1 与上述 Go 解法完全一致:维护 cnt[46] 统计每个数位和的频次,边统计边用 max 更新答案。
复杂度分析:
- 时间复杂度:
O((highLimit - lowLimit) · log(highLimit))。每个数需要O(log highLimit)的时间计算数位和; - 空间复杂度:
O(D · log highLimit),其中D = 9。这是cnt需要的空间(实际固定为46个元素)。
方法二:预处理前缀和
前置知识:一维前缀和,即把区间查询转化为两个前缀查询之差。
思路:定义 s[i][j] 表示 [0, i] 中的数位和为 j 的数字个数。那么 [lowLimit, highLimit] 中的数位和为 j 的数字个数为:
s[highLimit][j] - s[lowLimit-1][j]
枚举数位和 j,答案为:
max over j=1..45 of (s[highLimit][j] - s[lowLimit-1][j])
其中上界 45 是因为在本题数据范围下,99999 的数位和最大,为 45。
由于 highLimit <= 10^5,可以在程序启动时一次性预处理出 s(各语言分别利用全局 static 块、init() 或 auto init 完成),查询时 O(1) 级完成。
s = [[0] * 46]
for i in range(1, 100_001):
s.append(s[i - 1][:])
s[i][sum(map(int, str(i)))] += 1
class Solution:
def countBalls(self, lowLimit: int, highLimit: int) -> int:
return max(s[highLimit][j] - s[lowLimit - 1][j] for j in range(1, len(s[0])))
class Solution {
private final static int[][] s = new int[100_001][46];
static {
for (int i = 1; i < s.length; i++) {
System.arraycopy(s[i - 1], 0, s[i], 0, s[i].length);
int sum = 0;
for (int x = i; x > 0; x /= 10) {
sum += x % 10;
}
s[i][sum]++;
}
}
public int countBalls(int lowLimit, int highLimit) {
int ans = 0;
for (int j = 1; j < s[0].length; j++) {
ans = Math.max(ans, s[highLimit][j] - s[lowLimit - 1][j]);
}
return ans;
}
}
const int MX = 100'001;
array<int, 46> s[MX];
auto init = [] {
for (int i = 1; i < MX; i++) {
s[i] = s[i - 1];
int sum = 0;
for (int x = i; x > 0; x /= 10) {
sum += x % 10;
}
s[i][sum]++;
}
return 0;
}();
class Solution {
public:
int countBalls(int lowLimit, int highLimit) {
int ans = 0;
for (int j = 1; j < s[0].size(); j++) {
ans = max(ans, s[highLimit][j] - s[lowLimit - 1][j]);
}
return ans;
}
};
var s [100_001][46]int
func init() {
for i := 1; i < len(s); i++ {
s[i] = s[i-1]
sum := 0
for x := i; x > 0; x /= 10 {
sum += x % 10
}
s[i][sum]++
}
}
func countBalls(lowLimit, highLimit int) (ans int) {
for j := 1; j < len(s[0]); j++ {
ans = max(ans, s[highLimit][j]-s[lowLimit-1][j])
}
return
}
仓库 a.go 中的 countBalls2 即此实现:包级变量 s [100_001][46]int 在 init() 中按"先复制上一行,再在对应数位和上加 1"的方式递推完成预处理,随后每次查询只枚举 j = 1..45 取最大值。
实现要点:
- 第二维固定为
46,因为数位和上界是45; - 查询区间
[lowLimit-1, highLimit]时,若lowLimit = 1,则lowLimit - 1 = 0,s[0]恰好全为0,不会越界。
复杂度分析:预处理的时间和空间忽略不计。
- 时间复杂度:
O(D · log highLimit),其中D = 9。代码用了固定的上界45; - 空间复杂度:
O(1)(查询函数本身不额外申请空间)。
方法三:数位 DP(进阶)
进阶问题:如果 highLimit 更大,大到 10^18 这个数量级,要怎么做?
方法二的做法就行不通了——s 表的大小与 highLimit 同量级,无法再全量预处理。本题的进阶做法是数位 DP,这也是 copypasta/dp.go 中「数位 DP」章节的核心技法(仓库内同时收录了 v1.0 / v2.0 的模板视频讲解链接,以及 2719. 统计整数数目、788. 旋转数字 等十余道数位统计练习题;本题被标注为「*非暴力做法 枚举数位和+DP」)。
核心思路:枚举数位和 j = 1, 2, 3, ..., 45,计算 [lowLimit, highLimit] 中的数位和为 j 的数字个数。
定义 dfs(i, j, limitLow, limitHigh) 表示构造第 i 位及其之后数位的合法方案数,其余参数的含义为:
j表示剩余数字的数位和必须恰好等于j;limitHigh表示当前是否受到了highLimit的约束(构造的数字不能超过highLimit)。若为真,则第i位填入的数字至多为highLimit[i],否则至多为9,这个数记作hi。如果在受到约束的情况下填了highLimit[i],那么后续填入的数字仍会受到highLimit的约束。例如highLimit = 123,那么i = 0填的是1的话,i = 1的这一位至多填2;limitLow表示当前是否受到了lowLimit的约束(构造的数字不能低于lowLimit)。若为真,则第i位填入的数字至少为lowLimit[i],否则至少为0,这个数记作lo。如果在受到约束的情况下填了lowLimit[i],那么后续填入的数字仍会受到lowLimit的约束。
设 n 为 highLimit 的十进制长度。
- 递归终点:
dfs(n, 0, *, *) = 1,表示成功构造出一个合法数字;其余dfs(n, j, *, *) = 0; - 递归入口:
dfs(0, j, true, true),从最高位开始枚举,一开始必须受到lowLimit和highLimit的约束(否则就可以随意填了)。
答疑:为什么可以只记忆化 (i, j)?
问:记忆化四个状态有点麻烦,能不能只记忆化 (i, j)?
答:可以的。比如 highLimit = 234,我们第一位填 2,第二位填 3,后面无论怎么递归,都不会重复递归到"第一位填 2、第二位填 3"的情况,所以不需要记录。对于 lowLimit 也同理。
根据这个例子,我们可以只记录不受到 lowLimit 或 highLimit 约束时的状态 (i, j)。或者说,我们记忆化的是 (i, j, false, false),因为其它状态只会递归访问一次,不会重复递归访问。
class Solution:
def countBalls(self, lowLimit: int, highLimit: int) -> int:
high_s = str(highLimit)
n = len(high_s)
low_s = str(lowLimit).zfill(n) # 补前导零,和 high_s 对齐
@cache # 缓存装饰器,避免重复计算 dfs 的结果(一行代码实现记忆化)
def dfs(i: int, j: int, limit_low: bool, limit_high: bool) -> int:
if i == n: # 填完了
return 0 if j else 1
lo = int(low_s[i]) if limit_low else 0
hi = int(high_s[i]) if limit_high else 9
res = 0
for d in range(lo, min(hi, j) + 1): # 枚举当前数位填 d,但不能超过 j
res += dfs(i + 1, j - d, limit_low and d == lo, limit_high and d == hi)
return res
mx = int(high_s[0]) + (n - 1) * 9 # 数位和的上界
return max(dfs(0, j, True, True) for j in range(1, mx + 1))
class Solution {
public int countBalls(int lowLimit, int highLimit) {
String highS = String.valueOf(highLimit);
int n = highS.length();
String lowS = String.valueOf(lowLimit);
lowS = "0".repeat(n - lowS.length()) + lowS; // 补前导零,和 highS 对齐
int m = highS.charAt(0) - '0' + (n - 1) * 9; // 数位和的上界
int[][] memo = new int[n][m + 1];
for (int[] row : memo) {
Arrays.fill(row, -1); // -1 表示没有计算过
}
int ans = 0;
for (int j = 1; j <= m; j++) {
ans = Math.max(ans, dfs(0, j, true, true, lowS.toCharArray(), highS.toCharArray(), memo));
}
return ans;
}
private int dfs(int i, int j, boolean limitLow, boolean limitHigh, char[] lowS, char[] highS, int[][] memo) {
if (i == highS.length) { // 填完了
return j == 0 ? 1 : 0;
}
if (!limitLow && !limitHigh && memo[i][j] != -1) { // 之前计算过
return memo[i][j];
}
int lo = limitLow ? lowS[i] - '0' : 0;
int hi = limitHigh ? highS[i] - '0' : 9;
int res = 0;
for (int d = lo; d <= Math.min(hi, j); d++) { // 枚举当前数位填 d,但不能超过 j
res += dfs(i + 1, j - d, limitLow && d == lo, limitHigh && d == hi, lowS, highS, memo);
}
if (!limitLow && !limitHigh) {
memo[i][j] = res; // 记忆化
}
return res;
}
}
class Solution {
public:
int countBalls(int lowLimit, int highLimit) {
string high_s = to_string(highLimit);
int n = high_s.size();
string low_s = to_string(lowLimit);
low_s = string(n - low_s.size(), '0') + low_s; // 补前导零,和 high_s 对齐
int m = high_s[0] - '0' + (n - 1) * 9; // 数位和的上界
vector memo(n, vector<int>(m + 1, -1)); // -1 表示没有计算过
auto dfs = & -> int {
if (i == n) { // 填完了
return j == 0;
}
if (!limit_low && !limit_high && memo[i][j] != -1) { // 之前计算过
return memo[i][j];
}
int lo = limit_low ? low_s[i] - '0' : 0;
int hi = limit_high ? high_s[i] - '0' : 9;
int res = 0;
for (int d = lo; d <= min(hi, j); d++) { // 枚举当前数位填 d,但不能超过 j
res += dfs(i + 1, j - d, limit_low && d == lo, limit_high && d == hi);
}
if (!limit_low && !limit_high) {
memo[i][j] = res; // 记忆化
}
return res;
};
int ans = 0;
for (int j = 1; j <= m; j++) {
ans = max(ans, dfs(0, j, true, true));
}
return ans;
}
};
func countBalls(lowLimit, highLimit int) (ans int) {
highS := strconv.Itoa(highLimit)
n := len(highS)
lowS := strconv.Itoa(lowLimit)
lowS = strings.Repeat("0", n-len(lowS)) + lowS // 补前导零,和 num2 对齐
m := int(highS[0]-'0') + (n-1)*9 // 数位和的上界
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, m+1)
for j := range memo[i] {
memo[i][j] = -1 // -1 表示没有计算过
}
}
var dfs func(int, int, bool, bool) int
dfs = func(i, j int, limitLow, limitHigh bool) (res int) {
if i == n {
if j == 0 { // 合法
return 1
}
return
}
if !limitLow && !limitHigh {
p := &memo[i][j]
if *p >= 0 { // 之前计算过
return *p
}
defer func() { *p = res }() // 记忆化
}
lo := 0
if limitLow {
lo = int(lowS[i] - '0')
}
hi := 9
if limitHigh {
hi = int(highS[i] - '0')
}
for d := lo; d <= min(hi, j); d++ { // 枚举当前数位填 d,但不能超过 j
res += dfs(i+1, j-d, limitLow && d == lo, limitHigh && d == hi)
}
return
}
for j := 1; j <= m; j++ {
ans = max(ans, dfs(0, j, true, true))
}
return
}
仓库 a.go 中的 countBalls 即这一版本,也是周赛提交的最终解法。值得注意的实现细节:
- 用
strings.Repeat("0", n-len(lowS)) + lowS给lowLimit补前导零,与highS对齐,保证两位字符串下标一一对应; - 数位和上界
m = int(highS[0]-'0') + (n-1)*9:最高位不超过highS[0],其余n-1位最多各取9; - 记忆化时通过
defer在返回前回写memo[i][j],代码简洁且不易遗漏(与 Java/C++ 在递归返回后显式赋值的效果一致)。
复杂度分析:
- 时间复杂度:
O(D² · log² highLimit),其中D = 10。由于每个状态只会计算一次,动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题i有O(log highLimit)个,j有O(D · log highLimit)个,所以状态个数为O(D · log² highLimit),单个状态的计算时间为O(D),总复杂度为O(D² · log² highLimit); - 空间复杂度:
O(D · log² highLimit)。保存多少状态,就需要多少空间。
与仓库数位 DP 模板的对照
copypasta/dp.go 中收录了「上下界数位 DP · 计数型(v2.1 模板)」digitDP,其结构与本解完全同源:
dfs(i, cnt0, limitLow, limitHigh)同样是"位置 + 剩余约束"的四参数搜索;lo/hi的计算方式一致:limitLow为真时取lowS对应位,否则取0;limitHigh为真时取highS对应位,否则取9;- 记忆化同样只发生在
!limitLow && !limitHigh分支,并复用memo[i][...]; - 模板额外处理了前导零问题(
diffLH与i < diffLH分支),而本题由于"数位和计数"天然不受前导零影响(补零不影响数位和),本解无需该分支——这也是题解代码比通用模板更精简的原因。
此外,模板注释中还给出了一条通用技巧:若题目要求计算 < high 的方案数(high 为字符串),可在递归到 i = n 时判断 limitHigh 是否为 true,若是则说明填入的数字恰好等于 high,返回 0(参见 copypasta/dp.go)。
三种方法对比与选型
| 方法 | 思路 | 时间复杂度 | 空间复杂度 | 适用上限 |
|---|---|---|---|---|
| 暴力枚举 | 逐个数计算数位和并计数 | O((high-low) · log high) |
O(1) 量级 |
high ≤ 10^5 够用 |
| 预处理前缀和 | 全量预处理 s[i][j],差分查询 |
O(D · log high) |
O(1)(预处理不计) |
high ≤ 10^5 且多次查询场景更优 |
| 数位 DP | 枚举数位和 + 记忆化搜索 | O(D² · log² high) |
O(D · log² high) |
high 可达 10^18 量级 |
选型建议:
- 面试/周赛快速 AC 选方法一,代码量最小;
- 如果同一题会有多次区间查询,或想练习前缀和的二维变体,选方法二;
- 当
highLimit放大到10^9、10^18时,前两种方法全部失效,必须使用方法三数位 DP。这也是本题在 copypasta/dp.go 中被标记为「*非暴力做法 枚举数位和+DP」的原因。
如何在本仓库中复现与验证
- 查看实现:三种解法分别对应 a.go 中的
countBalls1(暴力)、countBalls2(前缀和)、countBalls(数位 DP),源码头部标注了题目来源github.com/EndlessCheng/codeforces-go; - 运行测试:在仓库根目录执行
go test ./leetcode/weekly/226/a即可跑通 a_test.go 中的三组样例。该测试文件由 copypasta/template/leetcode/generator_test.go 自动生成,内部通过 leetcode/testutil/leetcode.go 的RunLeetCodeFuncWithExamples反射调用目标函数:先解析输入/输出样例,再对每个用例执行函数并比对结果,还支持targetCaseNum指定单用例调试与超时检测(DebugTLE); - 横向拓展:在 copypasta/dp.go 的数位 DP 章节中,可以找到与本题同类的练习题,例如 2719. 统计整数数目(模板入门)、233. 数字 1 的个数、1012. 至少有 1 位重复的数字,以及数位和专题的 数位和 digsum(n)|n 等,形成"由浅入深"的刷题路径。
小结
本题表面上是简单计数,实际串起了三条递进的技术路线:暴力枚举适合小数据快速出解;二维前缀和把"区间查询"抽象成"差分相减",适合预处理后多次查询;上下界数位 DP 则把复杂度压到与数字长度相关,是应对超大范围数据的标准解法。掌握"枚举数位和 + 记忆化搜索"这个组合后,遇到"统计某范围内满足数位性质的数字个数"一类题目,都可以直接套用 copypasta/dp.go 中的 v2.1 模板快速建模。