本題為11月23日力扣每日一題
題目來源:力扣第1742題
題目tag:哈希表
題面
題目描述
你在一家生產小球的玩具廠作業，有 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 $
思路分析
顯然,這題只要分別計算出每個盒子里放幾個小球,同時在這個程序中找最大值即可.
要計算出每個盒子里放幾個小球,就需要一個資料結構來存放這個資料,以便不斷進行更新.
這里盒子的編號上限顯然很小,所以直接使用一個陣列作為桶即可.
這里我出于個人習慣,選擇了哈希表.其實桶本身也可以看成一種特殊的哈希表,所以兩種寫法本質上是差不多的.直接用桶的演算法效率其實會更高.
參考代碼
class Solution
{
public:
int countBalls(int lowLimit, int highLimit)
{
unordered_map<int, int> book; // 哈希表,記錄每個盒子有幾個小球
int res = 1; // 存放最大值
for (; lowLimit <= highLimit; lowLimit++) // 直接利用lowLimit當回圈變數,計算每個小球放在哪個盒子里,當然單獨用i當回圈變數可能代碼風格更好
{
int sum = countDigitSum(lowLimit); // 計算當前應放入的盒子編號
if (book.find(sum) != book.end()) // 當前盒子已有,直接在原本的基礎上自增
{
book[sum]++;
res = max(res, book[sum]); // 更新最大值
}
else
{
book.emplace(sum, 1); // 當前盒子還沒有,初始化
}
}
return res;
}
private:
/*
計算當前球應放入的盒子的編號,挨個取出每一個十進制位再相加即可
*/
int countDigitSum(int n)
{
int res = 0;
while (n)
{
res += n % 10;
n /= 10;
}
return res;
}
};
"正是我們每天反復做的事情，最終造就了我們，優秀不是一種行為，而是一種習慣" ---亞里士多德
這里是浙江理工大學22屆ACM集訓隊的成員一枚鴨!
本文首發于博客園，作者：星雙子，除了我自己的轉載請注明原文鏈接：https://www.cnblogs.com/geministar/p/LeetCode1742.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/538168.html
標籤：其他