1742-盒子中小球的最大数量

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

你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 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 <= 105

方法一：哈希表

遍历所有的小球，对于编号为 i 的小球，计算它应该放入的盒子编号 box，使用哈希表 count 记录每个盒子中的小球数量，返回遍历结束后 count 中小球数量最大的盒子对应的小球数量即可。

[sol1-Python3]

class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        count = Counter(sum(map(int, str(i))) for i in range(lowLimit, highLimit + 1))
        return max(count.values())

[sol1-C++]

class Solution {
public:
    int countBalls(int lowLimit, int highLimit) {
        unordered_map<int, int> count;
        int res = 0;
        for (int i = lowLimit; i <= highLimit; i++) {
            int box = 0, x = i;
            while (x) {
                box += x % 10;
                x /= 10;
            }
            count[box]++;
            res = max(res, count[box]);
        }
        return res;
    }
};

[sol1-Java]

class Solution {
    public int countBalls(int lowLimit, int highLimit) {
        Map<Integer, Integer> count = new HashMap<Integer, Integer>();
        int res = 0;
        for (int i = lowLimit; i <= highLimit; i++) {
            int box = 0, x = i;
            while (x != 0) {
                box += x % 10;
                x /= 10;
            }
            count.put(box, count.getOrDefault(box, 0) + 1);
            res = Math.max(res, count.get(box));
        }
        return res;
    }
}

[sol1-C#]

public class Solution {
    public int CountBalls(int lowLimit, int highLimit) {
        IDictionary<int, int> count = new Dictionary<int, int>();
        int res = 0;
        for (int i = lowLimit; i <= highLimit; i++) {
            int box = 0, x = i;
            while (x != 0) {
                box += x % 10;
                x /= 10;
            }
            count.TryAdd(box, 0);
            count[box]++;
            res = Math.Max(res, count[box]);
        }
        return res;
    }
}

[sol1-C]

#define MAX(a, b) ((a) > (b) ? (a) : (b))

typedef struct {
    int key;
    int val;
    UT_hash_handle hh;
} HashItem; 

HashItem *hashFindItem(HashItem **obj, int key) {
    HashItem *pEntry = NULL;
    HASH_FIND_INT(*obj, &key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem **obj, int key, int val) {
    if (hashFindItem(obj, key)) {
        return false;
    }
    HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
    pEntry->key = key;
    pEntry->val = val;
    HASH_ADD_INT(*obj, key, pEntry);
    return true;
}

bool hashSetItem(HashItem **obj, int key, int val) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        hashAddItem(obj, key, val);
    } else {
        pEntry->val = val;
    }
    return true;
}

int hashGetItem(HashItem **obj, int key, int defaultVal) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        return defaultVal;
    }
    return pEntry->val;
}

void hashFree(HashItem **obj) {
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);  
        free(curr);             
    }
}

int countBalls(int lowLimit, int highLimit){
    HashItem *count = NULL;
    int res = 0;
    for (int i = lowLimit; i <= highLimit; i++) {
        int box = 0, x = i;
        while (x) {
            box += x % 10;
            x /= 10;
        }
        hashSetItem(&count, box, hashGetItem(&count, box, 0) + 1);
        res = MAX(res, hashGetItem(&count, box, 0));
    }
    hashFree(&count);
    return res;
}

[sol1-JavaScript]

var countBalls = function(lowLimit, highLimit) {
    const count = new Map();
    let res = 0;
    for (let i = lowLimit; i <= highLimit; i++) {
        let box = 0, x = i;
        while (x !== 0) {
            box += x % 10;
            x = Math.floor(x / 10);
        }
        count.set(box, (count.get(box) || 0) + 1);
        res = Math.max(res, count.get(box));
    }
    return res;
};

[sol1-Golang]

func countBalls(lowLimit, highLimit int) (ans int) {
    count := map[int]int{}
    for i := lowLimit; i <= highLimit; i++ {
        sum := 0
        for x := i; x > 0; x /= 10 {
            sum += x % 10
        }
        count[sum]++
        ans = max(ans, count[sum])
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

• 时间复杂度：O(n \log \textit{highLimit})，其中 n = \textit{highLimit} - \textit{lowLimit} + 1。

• 空间复杂度：O(\log \textit{highLimit})。假设 highLimit 的十进制位数为 x，那么可能使用的盒子编号数目不超过 10 \times x，因此空间复杂度为 O(\log \textit{highLimit})。