leetcode·每日一题·1742.盒子中小球的最大数量·哈希_舒迅的博客-爱代码爱编程
作者:小迅
链接:https://leetcode.cn/problems/maximum-number-of-balls-in-a-box/solutions/1986502/ha-xi-zhu-shi-chao-ji-xiang-xi-by-xun-ge-hg14/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目
示例
思路
题目要求我们对所有球按编号和进行分组,最后返回最大数量的分组。
我们可以枚举所有球的编号和,并用哈希表对数据进行保存,其中以组号为键值,球编号和为实值,建立分组,最后取出哈希表中最大数量的组。
数据元素最大为 1e5 ,那么最大的组号为 99999 -> 45, 说明我们的组号是比较小的而且相对集中,那么我们可以使用数组哈希表,即用数组代替哈希表,行哈希表功能
代码
inline int Summation(int n)//求编号和
{
int count = 0;
while (n > 0) {
count += n % 10;
n /= 10;
}
return count;
}
int countBalls(int lowLimit, int highLimit){
int flag[46] = {0};//数组哈希表
int count = 0;
while (lowLimit <= highLimit) {//枚举所有球
int n = Summation(lowLimit);
if (count < (++flag[n])) {//哈希表记录
count = flag[n];//每次保存最大值
}
lowLimit++;
}
return count;
}
作者:小迅
链接:https://leetcode.cn/problems/maximum-number-of-balls-in-a-box/solutions/1986502/ha-xi-zhu-shi-chao-ji-xiang-xi-by-xun-ge-hg14/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
class Solution {
public:
inline int Summation(int n) {
int count = 0;
while (n > 0) {
count += n % 10;
n /= 10;
}
return count;
}
int countBalls(int lowLimit, int highLimit) {
int flag[46] = {0};
int count = 0;
while (lowLimit <= highLimit) {
int n = Summation(lowLimit);
if (count < (++flag[n])) {
count = flag[n];
}
++lowLimit;
}
return count;
}
};
作者:小迅
链接:https://leetcode.cn/problems/maximum-number-of-balls-in-a-box/solutions/1986502/ha-xi-zhu-shi-chao-ji-xiang-xi-by-xun-ge-hg14/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。