难度: Easy
给你一个整数 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运行时间: 46 ms
内存: 15.9 MB
class Solution:
def countLargestGroup(self, n: int) -> int:
my_dict = {}
i = 1
ss = 0
while i <= n:
if i % 10 == 0:
if i % 1000 == 0:
ss = 0
temp = i
while temp != 0:
ss += temp % 10
temp = temp // 10
elif i % 100 == 0:
ss -= 17
else:
ss -= 8
else:
ss += 1
my_dict[ss] = my_dict.setdefault(ss, 0) + 1
i += 1
arr = sorted(my_dict.values())
n = len(arr)
if arr[0] == arr[-1]:
return n
for j in range(n-2, -1, -1):
if arr[j] != arr[-1]:
return n - j - 1
此题解通过计算1到n每个数字的数位和，并将计算结果用作字典的键，将相同数位和的数字数量累加存储在字典中。计算数位和时，利用了数位变化的规律，特别是在数字每过10、100、1000的边界时进行调整。最后，将字典中的值（即每个组的大小）进行排序，通过比较找出并列最多的组数。
时间复杂度: O(n)
空间复杂度: O(k)，其中k为不同数位和的数量，远小于n
class Solution:
def countLargestGroup(self, n: int) -> int:
my_dict = {}
i = 1
ss = 0
while i <= n:
if i % 10 == 0:
if i % 1000 == 0:
ss = 0
temp = i
while temp != 0:
ss += temp % 10
temp = temp // 10
elif i % 100 == 0:
ss -= 17
else:
ss -= 8
else:
ss += 1
my_dict[ss] = my_dict.setdefault(ss, 0) + 1
i += 1
arr = sorted(my_dict.values())
n = len(arr)
if arr[0] == arr[-1]:
return n
for j in range(n-2, -1, -1):
if arr[j] != arr[-1]:
return n - j - 1
# Comments added to the code:
# my_dict: Dictionary to hold sum of digits (key) and count of numbers with that sum (value)
# ss: Current sum of digits
# i: Current number being processed
# Adjustments for ss when i is a multiple of 10, 100, or 1000
# After processing, sort the counts and determine the number of groups with the maximum size
在计算数位和时，每当数字是10的倍数时，其最低位由9变为0，这会导致数位和突然减少。例如，从9到10时，数位和从9变为1。因此，为了保持数位和的正确计算，需要进行特殊处理，调整数位和以反映这种突变。
当i是100的倍数时，例如从99到100，最后两位由99变为00，因此数位和需要减去9+9（即18），但同时下一位数位和会增加1，所以最终减去的是17。当i是10的倍数但非100的倍数时，例如从19到20，最后一位由9变为0，数位和减少9，但同时下一位增加1，因此实际上减少的是8。这些数值是根据数位和变化的具体情况精确计算得出的。
当数字是1000或更大的幂时，比如1000、10000等，所有低位数字都从9变为0，导致数位和发生大幅度变化，原有的累积计算方式（逐位增加）无法简单地调整来反映这种变化。因此，最简单且准确的方法是将数位和归零并重新计算当前数字的数位和，以确保计算的准确性。