1742. 盒子中小球的最大数量
1742. 盒子中小球的最大数量
题目
You are working in a ball factory where you have n
balls numbered from lowLimit
up to highLimit
inclusive (i.e., n == highLimit - lowLimit + 1
), and an infinite number of boxes numbered from 1
to infinity
.
Your job at this factory is to put each ball in the box with a number equal to the sum of digits of the ball's number. For example, the ball number 321
will be put in the box number 3 + 2 + 1 = 6
and the ball number 10
will be put in the box number 1 + 0 = 1
.
Given two integers lowLimit
and highLimit
, return the number of balls in the box with the most balls.
Example 1:
Input: lowLimit = 1, highLimit = 10
Output: 2
Explanation:
Box Number: 1 2 3 4 5 6 7 8 9 10 11 ...
Ball Count: 2 1 1 1 1 1 1 1 1 0 0 ...
Box 1 has the most number of balls with 2 balls.
Example 2:
Input: lowLimit = 5, highLimit = 15
Output: 2
Explanation:
Box Number: 1 2 3 4 5 6 7 8 9 10 11 ...
Ball Count: 1 1 1 1 2 2 1 1 1 0 0 ...
Boxes 5 and 6 have the most number of balls with 2 balls in each.
Example 3:
Input: lowLimit = 19, highLimit = 28
Output: 2
Explanation:
Box Number: 1 2 3 4 5 6 7 8 9 10 11 12 ...
Ball Count: 0 1 1 1 1 1 1 1 1 2 0 0 ...
Box 10 has the most number of balls with 2 balls.
Constraints:
1 <= lowLimit <= highLimit <= 10^5
题目大意
你在一家生产小球的玩具厂工作,有 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 <= 10^5
解题思路
数字和计算:
- 定义一个辅助函数
digitSum(n)
用于计算一个数的各位数字之和。 - 通过逐位取余 (
n % 10
) 并整除 (n = Math.floor(n / 10)
) 累加计算。
- 定义一个辅助函数
初始化计数器:
- 使用一个数组
count
,其索引表示可能的数字和(从 0 到 45)。因为数字和的最大值为99999
的各位数字之和,即9 * 5 = 45
。
- 使用一个数组
从
lowLimit
到highLimit
,逐一计算数字和,将count
对应索引的值加一。记录过程中出现次数最多的盒子数,最终返回最大值。
复杂度分析
- 时间复杂度:
O((h - l) * log_10(h))
,其中l
为最小编号lowLimit
,h
为最大编号highLimit
。- 需要遍历从
lowLimit
到highLimit
,计算数字和,共h - l + 1
次。 - 计算数字和的时间复杂度为
O(log_10(h))
。 - 总复杂度为
O((h - l) * log_10(h))
。
- 需要遍历从
- 空间复杂度:
O(1)
,仅需额外的固定长度数组count
和几个常量空间。
代码
/**
* @param {number} lowLimit
* @param {number} highLimit
* @return {number}
*/
var countBalls = function (lowLimit, highLimit) {
let count = new Array(46).fill(0); // 初始化 0-45 的计数器
const digitSum = (n) => {
let sum = 0;
while (n > 0) {
sum += n % 10; // 加上当前最低位
n = Math.floor(n / 10); // 去掉最低位
}
return sum;
};
let max = 0; // 记录最大值
for (let i = lowLimit; i <= highLimit; i++) {
const idx = digitSum(i); // 计算数字和
count[idx]++; // 计数
max = Math.max(count[idx], max); // 更新最大值
}
return max;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
3160 | 所有球里面不同颜色的数目 | 数组 哈希表 模拟 | 🟠 | 🀄️ 🔗 |