解题思路

方法一：哈希表统计

1
2
3
4
5
6
7
8
9
10
11
12
13
def countBalls(self, lowLimit: int, highLimit: int) -> int:
    # 使用字典存储每个盒子中球的数量
    box_count = {}
    
    # 遍历每个球的编号
    for i in range(lowLimit, highLimit + 1):
        # 计算数位和
        box_num = sum(int(d) for d in str(i))
        # 更新盒子中球的数量
        box_count[box_num] = box_count.get(box_num, 0) + 1
    
    # 返回最多的球数
    return max(box_count.values())

优点：

  • 实现简单直观
  • 空间复杂度较低
  • 适合小范围数据

方法二：数组统计（优化版）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def countBalls(self, lowLimit: int, highLimit: int) -> int:
    # 使用数组存储盒子中球的数量（最大数位和为9*5=45）
    box_count = [0] * 46
    
    # 遍历每个球的编号
    for i in range(lowLimit, highLimit + 1):
        num = i
        total = 0
        # 计算数位和
        while num:
            total += num % 10
            num //= 10
        box_count[total] += 1
    
    return max(box_count)

优点：

  • 性能更好，避免了字符串转换
  • 内存使用固定
  • 适合大范围数据

方法三：动态规划计算数位和

1

优点：

  • 最优性能
  • 避免重复计算
  • 利用数位之间的关系

算法比较

方法 时间复杂度 空间复杂度 特点
哈希表 O(n*d) O(k) 简单直观
数组统计 O(n*d) O(1) 性能稳定
动态规划 O(n) O(1) 最优性能

其中：

  • n 是数字范围大小 (highLimit - lowLimit + 1)
  • d 是数字的位数
  • k 是不同的数位和数量（最大45）

总结：

def countBalls(self, lowLimit: int, highLimit: int) -> int:
box_count = [0] * 46

# 计算第一个数的数位和
num = lowLimit
curr_sum = 0
while num:
    curr_sum += num % 10
    num //= 10
box_count[curr_sum] += 1

# 利用前一个数的数位和计算下一个数的数位和
for i in range(lowLimit + 1, highLimit + 1):
    while i % 10 == 0:
        curr_sum -= 9
        i //= 10
    curr_sum += 1
    box_count[curr_sum] += 1

return max(box_count)