英文原文
Given an integer n. Each number from 1 to n is grouped according to the sum of its digits.
Return how many groups have the largest size.
Example 1:
Input: n = 13 Output: 4 Explanation: There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13: [1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. There are 4 groups with largest size.
Example 2:
Input: n = 2 Output: 2 Explanation: There are 2 groups [1], [2] of size 1.
Example 3:
Input: n = 15 Output: 6
Example 4:
Input: n = 24 Output: 5
Constraints:
1 <= n <= 10^4
中文题目
给你一个整数 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^4
通过代码
高赞题解
解题思路
1 先思考如何将十进制的各个数位相加，因为求的是从1-n的数位和，所以可以找出规律：
sum[i] = sum[i / 10] + i % 10 //按顺序添加sum[i]2 然后统计各数位和的个数（有多少个相同个数并列的组）
3 求出并列数目最多的组，也就是统计和中最大的那个数
4 最后计算与max相等的数有多少个就可以了。
一开始代码写的比较长，按照基本的思路写，例如计数那块用了HashMap，求数位和用了i % 10 和 i / 10的计算方法
后来慢慢优化，答案还可以优化成一个for循环求出答案，但是这样需要做的判断却增加了，不如分开两个for循环计算
代码
class Solution {
public int countLargestGroup(int n) {
int ans = 0, max = 1;
int[] count = new int[n + 1];// 统计数位和有多少
int[] sum = new int[n + 1]; //计算1-n各个元素的数位和，例如数字i的数位和是sum[i / 10] + i % 10
for(int i = 1; i <= n; i++){
sum[i] = sum[i / 10] + i % 10;
count[sum[i]]++;
if(count[sum[i]] > max)
max = count[sum[i]];
}
for(int num : count) ans += num == max ? 1 : 0;
return ans;
}
}统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 9854 | 14682 | 67.1% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
