[leetcode] 1399. Count Largest Group

Description

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，代表以n结尾的自然数列表。算每个数的数字之和，相同的组成同一个组，求最大组的数目。这个思路也很直接，就是计算每个数的数字之和用一个字典存下来，然后计算最大长度，找出字典中包含最大长度的个数就是结果了。

代码

class Solution: def countLargestGroup(self, n: int) -> int: d=collections.defaultdict(list) max_len=0 for i in range(n): num=i+1 key=0 while(num>0): key+=num%10 num=num//10 d[key].append(i+1) max_len=max(max_len,len(d[key])) res=0 for k,v in d.items(): if(len(v)==max_len): res+=1 return res