LeetCode 1399 统计最大组的数目:从暴力枚举到数位 DP,以 codeforces-go 仓库源码为范例

原创2026-10-07 17:34:301,953 阅读
文章标签:开发工具

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 的状态设计与记忆化优化,以及它在 n=1018n=10^{18} 级数据下的应用方法。

题目回顾:什么是"最大组"

给你一个整数 nn。请你先求出从 11 到 nn 的每个整数 1010 进制表示下的数位和(每一位上的数字相加),然后把数位和相等的数字放到同一个组中。 请你统计每个分组中的数字数目,并返回数字数目并列最多的组有多少个。

用示例 1(n=13n=13)来说明:

  • 1,101,10 的数位和为 11,一组;
  • 2,112,11 的数位和为 22,一组;
  • 3,123,12 的数位和为 33,一组;
  • 4,134,13 的数位和为 44,一组;
  • 5,6,7,8,95,6,7,8,9 的数位和分别为 5,6,7,8,95,6,7,8,9,各自单独成组。

统计得到 cnt = {1: 2, 2: 2, 3: 2, 4: 2, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1}。其中最大的组大小为 22,而大小为 22 的组有 44 个(数位和为 1,2,3,41,2,3,4 的四组),因此答案为 44。

这里的关键信息有两点:

  1. 数位和的上限:若 nn 有 mm 位,则数位和至多为 9m9m(每一位都填 99)。这决定了哈希表/数组的开辟大小。
  2. 答案是"并列最多的组的个数",即最大组大小出现次数,而不是最大组大小本身。

在 a_test.go 中,仓库收录了 4 组官方样例(13→4、2→2、15→6、24→5),由 testutil 驱动比对,可作为本地验证答案的正确性基准。

方法一:暴力枚举 + 哈希表/数组计数

思路

枚举 [1,n][1,n] 中的整数 ii,计算 ii 的数位和 ds\textit{ds},用一个哈希表(或者数组)cnt\textit{cnt} 统计 ds\textit{ds} 及其出现次数。

统计 cnt\textit{cnt} 中的最大 value(出现次数)的出现次数。比如示例 1 的最大 value 为 22,我们需要统计 cnt\textit{cnt} 中有多少个 value 等于 22,这一共有 44 个。

一个常被忽视的细节是:最大值与最大值的出现次数可以在枚举过程中同步维护,无需遍历完 nn 后再扫描一遍 cnt\textit{cnt}。每当 cnt[ds]\textit{cnt}[\textit{ds}] 更新后:

  • 若 cnt[ds]>maxCnt\textit{cnt}[\textit{ds}] > \textit{maxCnt}:出现了新的最大组,重置答案为 11;
  • 若 cnt[ds]==maxCnt\textit{cnt}[\textit{ds}] == \textit{maxCnt}:出现了并列的最大组,答案自增 11;
  • 若 cnt[ds]<maxCnt\textit{cnt}[\textit{ds}] < \textit{maxCnt}:不影响答案。

代码实现(四种语言)

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 的分配开销——这是竞赛场景下常见的性能取舍。

复杂度分析

  • 时间复杂度:O(nlog⁡n)\mathcal{O}(n\log n)。每个数字需要 O(log⁡n)\mathcal{O}(\log n) 的时间计算数位和。
  • 空间复杂度:O(Dlog⁡n)\mathcal{O}(D\log n),其中 D=9D=9。有 O(Dlog⁡n)\mathcal{O}(D\log n) 个不同的数位和(数组长度为 9m+19m+1,m=log⁡nm=\log n)。

当 n≤104n \le 10^4 量级(本题实际约束)时,暴力法完全够用;但若把 nn 放大到 101810^{18},逐个数枚举显然会超时,就需要方法二。

方法二:数位 DP

为什么要用数位 DP

如果 n=1018n = 10^{18},方法一就超时了,怎么办?这时我们不能再"一个数一个数"地算数位和,而应该直接统计:数位和恰好等于某个 target 的数有多少个。这正是数位 DP 的主场——它不枚举具体数值,而是按"位"做带约束的计数,复杂度与 nn 的位数 mm 有关,而非与 nn 本身有关。

这类写法属于上界数位 DP(只受 nn 约束、无下界约束),即题解中"数位 DP v1.0"视频讲解所介绍的写法。仓库 copypasta/dp.go 的 digitDP(low, high, target) 模板正是这一家族的直接体现:它同时处理下界 lowS 与上界 highS,用 limitLow, limitHigh 两个布尔参数标记两侧约束,用 memo[i][cnt0] 做记忆化;当只需上界时(如本题),lowS 可初始化为 "0" 或 "1",本质就是本节的单侧约束版本。

模型建立

设 nn 的十进制字符串为 ss,设 ss 的长度为 mm。那么数位和至多为 9m9m(每一位都填 99)。

枚举目标数位和 target=1,2,…,9m\textit{target}=1,2,\ldots,9m,计算 [1,n][1,n] 中有多少个整数的数位和恰好等于 target\textit{target}。这正是方法一哈希表(数组)中的 value 值,即 cnt[target]\textit{cnt}[\textit{target}]。求出所有 cnt[target]\textit{cnt}[\textit{target}] 后,再用方法一相同的"维护最大值的出现次数"技巧得到答案。

状态定义

dfs(i,left,limitHigh)\textit{dfs}(i, \textit{left}, \textit{limitHigh})

表示构造第 ii 位及其之后数位的合法方案数,其余参数的含义为:

  • ii:当前构造到第 ii 位(从最高位 00 开始)。
  • left\textit{left}:剩余数位的数位和,也就是 ii 到 m−1m-1 填的数位之和必须恰好等于 left\textit{left}。
  • limitHigh\textit{limitHigh}:当前是否受到了 nn 的约束(我们要构造的数字不能超过 nn)。若为真,则第 ii 位填入的数字至多为 s[i]s[i],否则至多为 99,这个数记作 hi\textit{hi}。如果在受到约束的情况下填了 hi\textit{hi},那么后续填入的数字仍会受到 nn 的约束。例如 n=123n=123,那么 i=0i=0 填的是 11 的话,i=1i=1 的这一位至多填 22。

注 1:为什么要把 left\textit{left} 定义成剩余的数位和,而不是已填数位之和?因为这样可以让 target=1,2,…,9m\textit{target}=1,2,\ldots,9m 复用同一个记忆化搜索的结果。如果反过来,从 00 递归到 target\textit{target},记忆化的内容就和 target\textit{target} 有关了,无法复用——这正是本题实现能够"一份 memo 服务所有 target"的关键设计。

注 2:本题前导零不影响答案,因为任何数加上(减去)00 是不变的。若题目受前导零影响(例如统计"不含前导零且数字不重复"的个数),则需额外引入 isNum 维度;仓库模板 copypasta/dp.go 中专门给出了"前导零影响答案"的第二种写法(以 P2657 为例),可对照学习。

状态转移与递归边界

状态转移:枚举第 ii 位填数字 d=0,1,…,min⁡(hi,left)d=0,1,\ldots,\min(\textit{hi},\textit{left}),把 ii 加一,把 left\textit{left} 减少 dd,继续向后递归(枚举右边的数位)。这里 d≤leftd \le \textit{left} 是一个天然剪枝:剩余数位和已经不足以容纳更大的 dd。

递归终点:i=ni=n 时,如果 left=0\textit{left}=0,说明我们成功构造出一个数位和恰好等于 target\textit{target} 的整数,返回 11,否则返回 00。(注意 left\textit{left} 是从 target\textit{target} 开始减少的)

递归入口:dfs(0,target,true)\textit{dfs}(0, \textit{target}, \texttt{true}),表示:

  • 从最高位开始。
  • 目标数位和为 target\textit{target}。
  • 一开始要受到 nn 的约束(否则就可以随意填了,这肯定不行)。

记忆化:当 limitHigh == false 时,状态与 nn 无关,可以缓存 memo<a href="https://link.gitcode.com/i/0ea4318b457091d5678e361746028017" target="_blank">i][left];处于约束状态(limitHigh == true)的分支每个 nn 只出现一次,无需缓存。这与 [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 等基础设施提供。

复杂度分析

  • 时间复杂度:O(D2log⁡2n)\mathcal{O}(D^2\log ^2 n),其中 D=10D=10。由于每个状态只会计算一次,动态规划的时间复杂度 == 状态个数 ×\times 单个状态的计算时间。本题 ii 有 O(log⁡n)\mathcal{O}(\log n) 个,left\textit{left} 有 O(Dlog⁡n)\mathcal{O}(D\log n) 个,所以状态个数为 O(Dlog⁡2n)\mathcal{O}(D\log^2 n),单个状态的计算时间为 O(D)\mathcal{O}(D),所以总的时间复杂度为 O(D2log⁡2n)\mathcal{O}(D^2\log ^2 n)。
  • 空间复杂度:O(Dlog⁡2n)\mathcal{O}(D\log ^2 n)。保存多少状态,就需要多少空间。

对比方法一的 O(nlog⁡n)\mathcal{O}(n\log n),当 nn 有几十位时(如 101810^{18}),数位 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"的个数
状态 无 dfs(i,left,limitHigh)\textit{dfs}(i, \textit{left}, \textit{limitHigh})
时间复杂度 O(nlog⁡n)\mathcal{O}(n\log n) O(D2log⁡2n)\mathcal{O}(D^2\log ^2 n)(D=10D=10)
空间复杂度 O(Dlog⁡n)\mathcal{O}(D\log n)(D=9D=9) O(Dlog⁡2n)\mathcal{O}(D\log ^2 n)
适用规模 nn 在万级以内 nn 可达 101810^{18}
仓库落点 a.go 的 countLargestGroup1 a.go 的 countLargestGroup,模板见 copypasta/dp.go

两道方法的共同收尾技巧是"在线维护最大值及其出现次数":用 maxCnt 记录当前最大组大小,遇到新的更大值就重置答案、遇到并列就自增。掌握本题后,建议对照 a_test.go 跑通本地测试,再依次研读 copypasta/dp.go 中的数位 DP 模板,完成从"一题"到"一类题"的跃迁。

登录后查看全文
codeforces-go