LeetCode 1399 统计最大组的数目:从暴力枚举到数位 DP,以 codeforces-go 仓库源码为范例
LeetCode 1399 统计最大组的数目:从暴力枚举到数位 DP,以 codeforces-go 仓库源码为范例
本篇技术指南以力扣第 23 场双周赛第 1 题 1399. 统计最大组的数目(Count Largest Group) 为切入点,系统讲解"按十进制数位和分组、统计最大组的组数"这一经典计数问题的两种解法——暴力枚举与数位 DP(Digit DP)。文章不仅完整给出 Python / Java / C++ / Go 四种语言的题解与复杂度分析,还结合算法竞赛模板库 codeforces-go 仓库中的 a.go 实现、a_test.go 测试用例以及 copypasta/dp.go 中的通用数位 DP 模板,展示从"会做这一题"到"掌握一类题"的完整进阶路径。读完本文,你将掌握:数位和分组的暴力计数思路、"最大组"的在线维护技巧、上界约束(limitHigh)数位 DP 的状态设计与记忆化优化,以及它在 级数据下的应用方法。
题目回顾:什么是"最大组"
给你一个整数 。请你先求出从 到 的每个整数 进制表示下的数位和(每一位上的数字相加),然后把数位和相等的数字放到同一个组中。 请你统计每个分组中的数字数目,并返回数字数目并列最多的组有多少个。
用示例 1()来说明:
- 的数位和为 ,一组;
- 的数位和为 ,一组;
- 的数位和为 ,一组;
- 的数位和为 ,一组;
- 的数位和分别为 ,各自单独成组。
统计得到 cnt = {1: 2, 2: 2, 3: 2, 4: 2, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1}。其中最大的组大小为 ,而大小为 的组有 个(数位和为 的四组),因此答案为 。
这里的关键信息有两点:
- 数位和的上限:若 有 位,则数位和至多为 (每一位都填 )。这决定了哈希表/数组的开辟大小。
- 答案是"并列最多的组的个数",即最大组大小出现次数,而不是最大组大小本身。
在 a_test.go 中,仓库收录了 4 组官方样例(13→4、2→2、15→6、24→5),由 testutil 驱动比对,可作为本地验证答案的正确性基准。
方法一:暴力枚举 + 哈希表/数组计数
思路
枚举 中的整数 ,计算 的数位和 ,用一个哈希表(或者数组) 统计 及其出现次数。
统计 中的最大 value(出现次数)的出现次数。比如示例 1 的最大 value 为 ,我们需要统计 中有多少个 value 等于 ,这一共有 个。
一个常被忽视的细节是:最大值与最大值的出现次数可以在枚举过程中同步维护,无需遍历完 后再扫描一遍 。每当 更新后:
- 若 :出现了新的最大组,重置答案为 ;
- 若 :出现了并列的最大组,答案自增 ;
- 若 :不影响答案。
代码实现(四种语言)
class Solution:
def countLargestGroup(self, n: int) -> int:
cnt = defaultdict(int)
max_cnt = ans = 0
for i in range(1, n + 1):
ds = sum(map(int, str(i)))
cnt[ds] += 1
# 维护 max_cnt 以及 max_cnt 的出现次数
if cnt[ds] > max_cnt:
max_cnt = cnt[ds]
ans = 1
elif cnt[ds] == max_cnt:
ans += 1
return ans
class Solution:
def countLargestGroup(self, n: int) -> int:
m = len(str(n))
cnt = [0] * (m * 9 + 1) # 数位和 <= 9m
max_cnt = ans = 0
for i in range(1, n + 1):
ds = sum(map(int, str(i)))
cnt[ds] += 1
# 维护 max_cnt 以及 max_cnt 的出现次数
if cnt[ds] > max_cnt:
max_cnt = cnt[ds]
ans = 1
elif cnt[ds] == max_cnt:
ans += 1
return ans
class Solution {
public int countLargestGroup(int n) {
int m = String.valueOf(n).length();
int[] cnt = new int[m * 9 + 1]; // 数位和 <= 9m
int maxCnt = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
int ds = calcDigitSum(i);
cnt[ds]++;
// 维护 maxCnt 以及 maxCnt 的出现次数
if (cnt[ds] > maxCnt) {
maxCnt = cnt[ds];
ans = 1;
} else if (cnt[ds] == maxCnt) {
ans++;
}
}
return ans;
}
private int calcDigitSum(int num) {
int ds = 0;
while (num > 0) {
ds += num % 10;
num /= 10;
}
return ds;
}
}
class Solution {
public:
int countLargestGroup(int n) {
int m = to_string(n).size();
vector<int> cnt(m * 9 + 1); // 数位和 <= 9m
int max_cnt = 0, ans = 0;
for (int i = 1; i <= n; i++) {
int ds = 0;
for (int x = i; x > 0; x /= 10) {
ds += x % 10;
}
cnt[ds]++;
// 维护 max_cnt 以及 max_cnt 的出现次数
if (cnt[ds] > max_cnt) {
max_cnt = cnt[ds];
ans = 1;
} else if (cnt[ds] == max_cnt) {
ans++;
}
}
return ans;
}
};
func countLargestGroup(n int) (ans int) {
m := len(strconv.Itoa(n))
cnt := make([]int, m*9+1) // 数位和 <= 9m
maxCnt := 0
for i := 1; i <= n; i++ {
ds := 0
for x := i; x > 0; x /= 10 {
ds += x % 10
}
cnt[ds]++
// 维护 maxCnt 以及 maxCnt 的出现次数
if cnt[ds] > maxCnt {
maxCnt = cnt[ds]
ans = 1
} else if cnt[ds] == maxCnt {
ans++
}
}
return
}
在仓库中,这一版对应 a.go 里的 countLargestGroup1。值得注意的是,暴力解法把"计算数位和"写成了循环 for x := i; x > 0; x /= 10 { ds += x % 10 },没有调用字符串转换,在 Go 里避免了 strconv.Itoa 的分配开销——这是竞赛场景下常见的性能取舍。
复杂度分析
- 时间复杂度:。每个数字需要 的时间计算数位和。
- 空间复杂度:,其中 。有 个不同的数位和(数组长度为 ,)。
当 量级(本题实际约束)时,暴力法完全够用;但若把 放大到 ,逐个数枚举显然会超时,就需要方法二。
方法二:数位 DP
为什么要用数位 DP
如果 ,方法一就超时了,怎么办?这时我们不能再"一个数一个数"地算数位和,而应该直接统计:数位和恰好等于某个 target 的数有多少个。这正是数位 DP 的主场——它不枚举具体数值,而是按"位"做带约束的计数,复杂度与 的位数 有关,而非与 本身有关。
这类写法属于上界数位 DP(只受 约束、无下界约束),即题解中"数位 DP v1.0"视频讲解所介绍的写法。仓库 copypasta/dp.go 的 digitDP(low, high, target) 模板正是这一家族的直接体现:它同时处理下界 lowS 与上界 highS,用 limitLow, limitHigh 两个布尔参数标记两侧约束,用 memo[i][cnt0] 做记忆化;当只需上界时(如本题),lowS 可初始化为 "0" 或 "1",本质就是本节的单侧约束版本。
模型建立
设 的十进制字符串为 ,设 的长度为 。那么数位和至多为 (每一位都填 )。
枚举目标数位和 ,计算 中有多少个整数的数位和恰好等于 。这正是方法一哈希表(数组)中的 value 值,即 。求出所有 后,再用方法一相同的"维护最大值的出现次数"技巧得到答案。
状态定义
表示构造第 位及其之后数位的合法方案数,其余参数的含义为:
- :当前构造到第 位(从最高位 开始)。
- :剩余数位的数位和,也就是 到 填的数位之和必须恰好等于 。
- :当前是否受到了 的约束(我们要构造的数字不能超过 )。若为真,则第 位填入的数字至多为 ,否则至多为 ,这个数记作 。如果在受到约束的情况下填了 ,那么后续填入的数字仍会受到 的约束。例如 ,那么 填的是 的话, 的这一位至多填 。
注 1:为什么要把 定义成剩余的数位和,而不是已填数位之和?因为这样可以让 复用同一个记忆化搜索的结果。如果反过来,从 递归到 ,记忆化的内容就和 有关了,无法复用——这正是本题实现能够"一份 memo 服务所有 target"的关键设计。
注 2:本题前导零不影响答案,因为任何数加上(减去) 是不变的。若题目受前导零影响(例如统计"不含前导零且数字不重复"的个数),则需额外引入
isNum维度;仓库模板 copypasta/dp.go 中专门给出了"前导零影响答案"的第二种写法(以 P2657 为例),可对照学习。
状态转移与递归边界
状态转移:枚举第 位填数字 ,把 加一,把 减少 ,继续向后递归(枚举右边的数位)。这里 是一个天然剪枝:剩余数位和已经不足以容纳更大的 。
递归终点: 时,如果 ,说明我们成功构造出一个数位和恰好等于 的整数,返回 ,否则返回 。(注意 是从 开始减少的)
递归入口:,表示:
- 从最高位开始。
- 目标数位和为 。
- 一开始要受到 的约束(否则就可以随意填了,这肯定不行)。
记忆化:当 limitHigh == false 时,状态与 无关,可以缓存 memo<a href="https://link.gitcode.com/i/0ea4318b457091d5678e361746028017" target="_blank">i][left];处于约束状态(limitHigh == true)的分支每个 只出现一次,无需缓存。这与 [a.go 中 if !limitHigh { p := &memo<a href="https://link.gitcode.com/i/958a7cf3806a43be6425f96f2404c583" target="_blank">i][left]; if *p != -1 { return *p }; defer func() { *p = res }() } 的写法一一对应——defer 在递归返回后写入缓存,是 Go 惯用的记忆化写法,同样出现在 [copypasta/dp.go 的模板中。
代码实现(四种语言)
class Solution:
def countLargestGroup(self, n: int) -> int:
s = list(map(int, str(n))) # 避免在 dfs 中频繁调用 int()
m = len(s)
@cache
def dfs(i: int, left: int, limit_high: bool) -> int:
if i == m:
return 1 if left == 0 else 0
hi = s[i] if limit_high else 9 # 当前数位至多填 hi
res = 0
for d in range(min(hi, left) + 1): # 枚举当前数位填 d
res += dfs(i + 1, left - d, limit_high and d == hi)
return res
max_cnt = ans = 0
for target in range(1, m * 9 + 1): # 枚举目标数位和
cnt = dfs(0, target, True)
if cnt > max_cnt:
max_cnt = cnt
ans = 1
elif cnt == max_cnt:
ans += 1
return ans
class Solution {
public int countLargestGroup(int n) {
char[] s = String.valueOf(n).toCharArray();
int m = s.length;
int[][] memo = new int[m][m * 9 + 1];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
int maxCnt = 0;
int ans = 0;
for (int target = 1; target <= m * 9; target++) { // 枚举目标数位和
int cnt = dfs(0, target, true, s, memo);
if (cnt > maxCnt) {
maxCnt = cnt;
ans = 1;
} else if (cnt == maxCnt) {
ans++;
}
}
return ans;
}
private int dfs(int i, int left, boolean limitHigh, char[] s, int[][] memo) {
if (i == s.length) {
return left == 0 ? 1 : 0;
}
if (!limitHigh && memo[i][left] != -1) {
return memo[i][left];
}
int hi = limitHigh ? s[i] - '0' : 9; // 当前数位至多填 hi
int res = 0;
for (int d = 0; d <= Math.min(hi, left); d++) { // 枚举当前数位填 d
res += dfs(i + 1, left - d, limitHigh && d == hi, s, memo);
}
if (!limitHigh) {
memo[i][left] = res;
}
return res;
}
}
class Solution {
public:
int countLargestGroup(int n) {
string s = to_string(n);
int m = s.size();
vector memo(m, vector<int>(m * 9 + 1, -1));
auto dfs = & -> int {
if (i == m) {
return left == 0;
}
if (!limit_high && memo[i][left] != -1) {
return memo[i][left];
}
int hi = limit_high ? s[i] - '0' : 9; // 当前数位至多填 hi
int res = 0;
for (int d = 0; d <= min(hi, left); d++) { // 枚举当前数位填 d
res += dfs(i + 1, left - d, limit_high && d == hi);
}
if (!limit_high) {
memo[i][left] = res;
}
return res;
};
int max_cnt = 0, ans = 0;
for (int target = 1; target <= m * 9; target++) { // 枚举目标数位和
int cnt = dfs(0, target, true);
if (cnt > max_cnt) {
max_cnt = cnt;
ans = 1;
} else if (cnt == max_cnt) {
ans++;
}
}
return ans;
}
};
func countLargestGroup(n int) (ans int) {
s := strconv.Itoa(n)
m := len(s)
memo := make([][]int, m)
for i := range memo {
memo[i] = make([]int, m*9+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dfs func(i, left int, limitHigh bool) int
dfs = func(i, left int, limitHigh bool) (res int) {
if i == m {
if left == 0 {
return 1
}
return
}
if !limitHigh {
p := &memo[i][left]
if *p != -1 {
return *p
}
defer func() { *p = res }()
}
// 当前数位至多填 hi
hi := 9
if limitHigh {
hi = int(s[i] - '0')
}
for d := 0; d <= min(hi, left); d++ { // 枚举当前数位填 d
res += dfs(i+1, left-d, limitHigh && d == hi)
}
return
}
maxCnt := 0
for target := 1; target <= m*9; target++ { // 枚举目标数位和
cnt := dfs(0, target, true)
if cnt > maxCnt {
maxCnt = cnt
ans = 1
} else if cnt == maxCnt {
ans++
}
}
return
}
这份 Go 实现与仓库 a.go 中的 countLargestGroup 完全一致,是仓库作者提交并被测试验证通过的版本。其中用到的 min 函数在该竞赛模板仓库中由 common.go 或 cp.go 等基础设施提供。
复杂度分析
- 时间复杂度:,其中 。由于每个状态只会计算一次,动态规划的时间复杂度 状态个数 单个状态的计算时间。本题 有 个, 有 个,所以状态个数为 ,单个状态的计算时间为 ,所以总的时间复杂度为 。
- 空间复杂度:。保存多少状态,就需要多少空间。
对比方法一的 ,当 有几十位时(如 ),数位 DP 的优势是指数级的。
仓库实证:测试与通用模板
测试用例如何驱动
leetcode/biweekly/23/a/a_test.go 是仓库中本题的测试文件:
examples := [][]string{
{`13`, `4`},
{`2`, `2`},
{`15`, `6`},
{`24`, `5`},
}
targetCaseNum := 0 // -1
if err := testutil.RunLeetCodeFuncWithExamples(t, countLargestGroup, examples, targetCaseNum); err != nil {
t.Fatal(err)
}
它通过 leetcode/testutil/leetcode.go 提供的 RunLeetCodeFuncWithExamples 自动把输入输出字符串解析成函数参数并断言结果,targetCaseNum := 0 表示按顺序运行全部官方样例。这套测试基建由 copypasta/template/leetcode/generator_test.go 自动生成,构成了仓库"每题一测"的质量保障。
数位 DP 在模板库中的位置
copypasta/dp.go 是仓库的 DP 通用模板集,与本题直接相关的组件包括:
digitDP(low, high, target)(L3201):上下界数位 DP 计数模板,limitLow/limitHigh双约束 +memo[i][cnt0]记忆化。本题是它的"只有上界"特例;digitDP2(L3270):旧版写法,把上下界拆成两次calc(s)记忆化搜索;其中第一种写法注释"前导零不影响答案",正是本题的情形,第二种写法展示"前导零影响答案"时如何加isNum维度;digitDPContribution(L3381):求和型数位 DP(v2.1 模板),返回区间内每个数价值的总和,可视为本题"计数型"思路的姊妹版;digitDPRightToLeft/digitDPRightToLeft2(L3453):从低位往高位构造的数位 DP 写法,适用于带借位/异或等特殊约束的问题。
这些模板与本题 dfs(i, left, limitHigh) 的核心骨架完全同构:按位递归 → 约束参数限界 → 未约束状态记忆化。把本题吃透后,再对照模板库阅读,即可把这套手法迁移到"数字计数""数字和/积统计""某性质数的个数"等一大类题目上。
相似题目与延伸学习
- 2719. 统计整数数目:同样是枚举数位和、利用上界约束做数位 DP 的题目,是本题最直接的同族练习题。
在仓库作者的分类体系中,这类题目归属于动态规划题单的"数位 DP"专题(与滑动窗口、二分、单调栈、网格图、位运算、图论、数学算法等并列)。从仓库的刷题归档看,数位 DP 不仅在 leetcode 目录的周赛/双周赛题解中有大量分布,其通用模板也沉淀在 copypasta/dp.go 中,形成"题解 → 模板 → 新题"的闭环学习路径。
总结
| 维度 | 方法一:暴力枚举 | 方法二:数位 DP |
|---|---|---|
| 思路 | 逐个算数位和,哈希表/数组计数 | 按位构造,统计"数位和恰为 target"的个数 |
| 状态 | 无 | |
| 时间复杂度 | () | |
| 空间复杂度 | () | |
| 适用规模 | 在万级以内 | 可达 |
| 仓库落点 | a.go 的 countLargestGroup1 |
a.go 的 countLargestGroup,模板见 copypasta/dp.go |
两道方法的共同收尾技巧是"在线维护最大值及其出现次数":用 maxCnt 记录当前最大组大小,遇到新的更大值就重置答案、遇到并列就自增。掌握本题后,建议对照 a_test.go 跑通本地测试,再依次研读 copypasta/dp.go 中的数位 DP 模板,完成从"一题"到"一类题"的跃迁。