题目链接直达

1. 题目描述

给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和（每一位上的数字相加），然后把数位和相等的数字放到同一个组中。

请你统计每个组中的数字数目，并返回数字数目并列最多的组有多少个。

示例 1：

输入：n = 13

输出：4

解释：总共有 9 个组，将 1 到 13 按数位求和后这些组分别是：

[1,10]，[2,11]，[3,12]，[4,13]，[5]，[6]，[7]，[8]，[9]。总共有 4 个组拥有的数字并列最多。

示例 2：

输入：n = 2

输出：2

解释：总共有 2 个大小为 1 的组 [1]，[2]。

示例 3：

输入：n = 15

输出：6

示例 4：

输入：n = 24

输出：5

提示：

• 1 <= n <= 10⁴

2. 分析

核心思路：哈希表聚类+模拟

3. 代码实现

3.1. 暴力模拟

思路：直接模拟，遍历[1, n]，求和各位数，放入哈希表合并。

func countLargestGroup(n int) int {
	group := map[int]int{}
	for i := 1; i <= n; i++ {
		group[sum(i)]++
	}
	ans := 0
	mx := 0
	for _, cnt := range group {
		if mx < cnt {
			mx = cnt
			ans = 1
		} else if mx == cnt {
			ans++
		}
	}
	return ans
}

// 统计n的十进制下的各位和
func sum(n int) int {
	ans := 0
	for n > 0 {
		ans += n % 10
		n /= 10
	}
	return ans
}

3.2. 通过进位优化，无需对每一个数都求解各位和

func countLargestGroup(n int) int {
	group := map[int]int{}
	sum := 0
	for i := 1; i <= n; i++ {
		// 判断i有没有发生进位
		base := 1
		diff := 0
		for i%(base*10) == 0 {
			base *= 10
			diff += 9
		}
		sum -= diff
		sum++
		group[sum]++
	}
	ans := 0
	mx := 0
	for _, cnt := range group {
		if mx < cnt {
			mx = cnt
			ans = 1
		} else if mx == cnt {
			ans++
		}
	}
	return ans
}