Easy

题目描述

你在一球工厂工作，工厂里有 n 个球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit）（即 n == highLimit - lowLimit + 1），和无限数量的盒子，编号为 1 到无穷大。

你在工厂的工作是将每个球放在编号等于球上编号的各位数字之和的盒子中。例如，编号 321 的球将放在编号 3 + 2 + 1 = 6 的盒子中，编号 10 的球将放在编号 1 + 0 = 1 的盒子中。

给你两个整数 lowLimit 和 highLimit ，返回放有最多球的盒子中的球数量。

示例 1：

输入：lowLimit = 1, highLimit = 10
输出：2
解释：
盒子编号：  1 2 3 4 5 6 7 8 9 10 11 ...
球的数量：  2 1 1 1 1 1 1 1 1 0  0  ...
1号盒子放的球最多，有2个球。

示例 2：

输入：lowLimit = 5, highLimit = 15
输出：2
解释：
盒子编号：  1 2 3 4 5 6 7 8 9 10 11 ...
球的数量：  1 1 1 1 2 2 1 1 1 0  0  ...
5号盒子和6号盒子放的球最多，每个盒子中都有2个球。

示例 3：

输入：lowLimit = 19, highLimit = 28
输出：2
解释：
盒子编号：  1 2 3 4 5 6 7 8 9 10 11 12 ...
球的数量：  0 1 1 1 1 1 1 1 1 2  0  0  ...
10号盒子放的球最多，有2个球。

提示：

  • 1 <= lowLimit <= highLimit <= 10^5

解题思路

这道题的核心思路是：

  1. 遍历从 lowLimit 到 highLimit 的每个球的编号
  2. 计算每个球编号的各位数字之和，这个和就是对应的盒子编号
  3. 使用哈希表统计每个盒子中球的数量
  4. 返回球数最多的盒子中的球数

具体实现步骤：

  • 创建一个哈希表来记录每个盒子（按数字和分组）中的球数
  • 对于范围内的每个数字，计算其各位数字之和
  • 将该数字放入对应的盒子中（哈希表计数+1）
  • 遍历完成后，找出哈希表中的最大值

计算数字各位数字之和的方法：不断对数字取模10得到个位数，然后除以10去掉个位数，重复直到数字变为0。

时间复杂度主要取决于数字范围的大小，由于题目限制范围不超过10^5，所以可以直接暴力遍历所有数字。

代码实现

class Solution {
public:
    int countBalls(int lowLimit, int highLimit) {
        unordered_map<int, int> boxCount;
        
        for (int i = lowLimit; i <= highLimit; i++) {
            int sum = 0;
            int num = i;
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }
            boxCount[sum]++;
        }
        
        int maxBalls = 0;
        for (auto& pair : boxCount) {
            maxBalls = max(maxBalls, pair.second);
        }
        
        return maxBalls;
    }
};

class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        box_count = {}
        
        for i in range(lowLimit, highLimit + 1):
            digit_sum = sum(int(digit) for digit in str(i))
            box_count[digit_sum] = box_count.get(digit_sum, 0) + 1
        
        return max(box_count.values())

public class Solution {
    public int CountBalls(int lowLimit, int highLimit) {
        Dictionary<int, int> boxCount = new Dictionary<int, int>();
        
        for (int i = lowLimit; i <= highLimit; i++) {
            int sum = 0;
            int num = i;
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }
            
            if (boxCount.ContainsKey(sum)) {
                boxCount[sum]++;
            } else {
                boxCount[sum] = 1;
            }
        }
        
        int maxBalls = 0;
        foreach (var count in boxCount.Values) {
            maxBalls = Math.Max(maxBalls, count);
        }
        
        return maxBalls;
    }
}

var countBalls = function(lowLimit, highLimit) {
    const boxCount = new Map();
    
    for (let i = lowLimit; i <= highLimit; i++) {
        let sum = 0;
        let num = i;
        while (num > 0) {
            sum += num % 10;
            num = Math.floor(num / 10);
        }
        
        boxCount.set(sum, (boxCount.get(sum) || 0) + 1);
    }
    
    return Math.max(...boxCount.values());
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × log m)n = highLimit - lowLimit + 1，m是数字的最大值，log m表示计算数字各位和的时间
空间复杂度O(k)k是不同数字和的个数，最多为9×5=45（因为最大数字10^5有5位，每位最大为9）

相关题目