题目链接直达

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 <= 104

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
}