LeetCode每日一题4.23

题目

问题分析

计算每个数字的数位和：对于从 1 到 n 的每个整数，计算其十进制表示下的数位和。
分组：将数位和相等的数字放到同一个组中。
统计每个组的数字数目：统计每个组中有多少个数字。
找到并列最多的组：返回数字数目并列最多的组有多少个。

思路

计算数位和：
对于每个数字，将其转换为字符串，然后将每个字符（数字）转换为整数并求和。
分组：
使用一个字典来存储数位和作为键，对应的数字列表作为值。
统计每个组的数字数目：
遍历字典，统计每个键（数位和）对应的值（数字列表）的长度。
找到并列最多的组：
找到最大的组长度，然后统计有多少个组的长度等于这个最大长度。

代码

class Solution:def countLargestGroup(self, n: int) -> int:# Step 1: Calculate the digit sum for each number from 1 to ndef digit_sum(x):return sum(int(digit) for digit in str(x))# Step 2: Group numbers by their digit sumgroups = defaultdict(list)for i in range(1, n + 1):ds = digit_sum(i)groups[ds].append(i)# Step 3: Count the size of each groupgroup_sizes = [len(group) for group in groups.values()]# Step 4: Find the largest group size and count how many groups have this sizemax_size = max(group_sizes, default=0)count_max_size = group_sizes.count(max_size)return count_max_size

复杂度分析

时间复杂度：(O(nlogn))
空间复杂度：(O(n))

学习

问题理解：
通过示例来进一步理解：
示例 1：( n = 13 )
数字 1 到 13 的数位和分别为：[1, 2, 3, 4, 5, 6, 7, 8, 9, 1(1+0), 2(1+1), 3(1+2), 4(1+3)]，即 [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4]。
根据数位和分组得到：[ [1, 10], [2, 11], [3, 12], [4, 13], [5], [6], [7], [8], [9] ]。
每个组的大小为：[2, 2, 2, 2, 1, 1, 1, 1, 1]。
最大的组大小为 2，有 4 个组的大小为 2，因此答案为 4。