【Leetcode 每日一题】1742. 盒子中小球的最大数量

问题背景

你在一家生产小球的玩具厂工作，有 $n$ 个小球，编号从 $lowLimit$ 开始，到 $highLimit$ 结束（包括 $lowLimit$ 和 $highLimit$，即 $n=highLimit-lowLimit+1$）。另有无限数量的盒子，编号从 $1$ 到 $infinity$。
你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号$321$的小球应当放入编号 $3+2+1=6$ 的盒子，而编号 $10$ 的小球应当放入编号 $1+0=1$ 的盒子。
给你两个整数 $lowLimit$ 和 $highLimit$，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。

数据约束

• $1\le lowLimit\le highLimit\le 10^5$

解题过程

这题要求的数据范围不是特别大，直接用哈希表把结果算出来然后在调用的时候去取就好了。
进阶的方法还有利用前缀和或者数位 DP，暂时不作要求。

具体实现

class Solution {
    private static final int[] map = new int[100010];

    static {
        for (int i = 0; i < map.length; i++) {
            int sum = 0, cur = i;
            while (cur != 0) {
                sum += cur % 10;
                cur /= 10;
            }
            map[i] = sum;
        }
    }

    public int countBalls(int lowLimit, int highLimit) {
        int[] count = new int[50];
        int res = 0;
        for (int i = lowLimit; i <= highLimit; i++) {
            int index = map[i];
            count[index]++;
            res = Math.max(res, count[index]);
        }
        return res;
    }
}