盒子中小球的最大数量【LC1742】
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.
你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity 。
你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。
给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量*。*如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。
今天的任务是学数位DP
哈希表
- 思路：使用哈希表记录盒子存储的小球个数，哈希表key为盒子编号，value为盒子中的小球个数
- 实现：HashMap
class Solution { public int countBalls(int lowLimit, int highLimit) { Map<Integer,Integer> numToCount = new HashMap<>(); int maxNum = 0; for (int i = lowLimit; i <= highLimit; i++){ int num = getSum(i); numToCount.put(num,numToCount.getOrDefault(num,0) + 1); maxNum = Math.max(numToCount.get(num), maxNum); } return maxNum; } public int getSum (int n){ int ans = 0; while (n / 10 != 0){ ans += n % 10; n /= 10; } ans += n; return ans; } }
。复杂度
- 时间复杂度：O(nloghighLimit)，其中 n=highLimit−lowLimit+1
- 空间复杂度：O(loghighLimit)，假设highLimit的十进制位数为 x xx，那么可能使用的盒子编号数目不超过$ 10x$，因此空间复杂度为 O(loghighLimit)。
- 优化：由于1 <= lowLimit <= highLimit <= 105，因此盒子编号有限，由highLimit的位数决定，因此可以使用数组代替HashMap，优化空间复杂度
class Solution { public int countBalls(int lowLimit, int highLimit) { int m = 0, t = highLimit; while (t > 0) { // 计算highLimit的位数m m++; t /= 10; } int[] numToCount = new int[9 * m + 1]; // 盒子编号不会超过9*m int max = 0; for (int i = lowLimit; i <= highLimit; i++) { int num = getSum(i); max = Math.max(++numToCount[num], max); } return max; } public int getSum (int n){ int ans = 0; while (n / 10 != 0){ ans += n % 10; n /= 10; } ans += n; return ans; } }
。复杂度
- 时间复杂度：O(nloghighLimit)，其中 n=highLimit−lowLimit+1
- 空间复杂度：O ( 1 )
找规律
- 思路：记末尾为9的小球为小球A，末尾为0的小球为小球B，那么可以由小球A对应的箱子编号推出小球B对应的箱子编号，B球所在箱子编号 = A球所在箱子编号 - （9 * [末尾9的个数]）+ 1
- 实现
class Solution { public int countBalls(int lowLimit, int highLimit) { int[] resultMap = new int[46]; int firstIndex = 0, result = 0; for (int num = lowLimit; num > 0; num = num / 10) firstIndex += num % 10; resultMap[firstIndex] = 1; // 初始化第一个数字lowLimit所在编号盒子的小球数量 for (int i = lowLimit; i < highLimit; i++) { for (int prevNum = i; prevNum % 10 == 9; prevNum /= 10) // 根据前一个数的末位是否为9，来重新定位下一个数的位置 firstIndex -= 9; // 前移9位 resultMap[++firstIndex]++; } for (int rm : resultMap) result = Math.max(result, rm); return result; } } 作者：爪哇缪斯 链接：https://leetcode.cn/problems/maximum-number-of-balls-in-a-box/solutions/1986523/-by-muse-77-ru13/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处
数位DP
还没做过数位DP的，晚点学
