codeforces-go 题解:LeetCode 1742「盒子中小球的最大数量」——从暴力枚举到数位 DP 的三级进阶

原创2026-10-09 12:23:161,934 阅读
文章标签:开发工具

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] 的最大值。

计算数位和有两种方式:

  1. 转成字符串:sum(map(int, str(i))),Python 写法最简洁;
  2. 逐位除以 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」的原因。

如何在本仓库中复现与验证

  1. 查看实现:三种解法分别对应 a.go 中的 countBalls1(暴力)、countBalls2(前缀和)、countBalls(数位 DP),源码头部标注了题目来源 github.com/EndlessCheng/codeforces-go;
  2. 运行测试:在仓库根目录执行 go test ./leetcode/weekly/226/a 即可跑通 a_test.go 中的三组样例。该测试文件由 copypasta/template/leetcode/generator_test.go 自动生成,内部通过 leetcode/testutil/leetcode.go 的 RunLeetCodeFuncWithExamples 反射调用目标函数:先解析输入/输出样例,再对每个用例执行函数并比对结果,还支持 targetCaseNum 指定单用例调试与超时检测(DebugTLE);
  3. 横向拓展:在 copypasta/dp.go 的数位 DP 章节中,可以找到与本题同类的练习题,例如 2719. 统计整数数目(模板入门)、233. 数字 1 的个数、1012. 至少有 1 位重复的数字,以及数位和专题的 数位和 digsum(n)|n 等,形成"由浅入深"的刷题路径。

小结

本题表面上是简单计数,实际串起了三条递进的技术路线:暴力枚举适合小数据快速出解;二维前缀和把"区间查询"抽象成"差分相减",适合预处理后多次查询;上下界数位 DP 则把复杂度压到与数字长度相关,是应对超大范围数据的标准解法。掌握"枚举数位和 + 记忆化搜索"这个组合后,遇到"统计某范围内满足数位性质的数字个数"一类题目,都可以直接套用 copypasta/dp.go 中的 v2.1 模板快速建模。

登录后查看全文
codeforces-go