题目

你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity。

你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。

给你两个整数 lowLimit 和 highLimit，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。

解题思路

方法一：哈希表统计

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)

优点：

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

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

优点：

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

算法比较

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

其中：

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

总结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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)