推 Jaka: 大師 01/06 13:47
推 sustainer123: 大師 01/06 13:50
※ 編輯: Rushia (1.160.43.121 臺灣), 01/06/2023 13:52:27
推 SecondRun: 大師 01/06 13:54
推 Che31128: 大師 01/06 13:57
推 AyuniD: 時間複雜度沒有在 nlogn + n 的 8 01/09 02:28
1833. Maximum Ice Cream Bars
給你一個陣列costs表示每天冰淇淋的價錢，我們有coins個硬幣，求出每天最多買一個
冰淇淋最多可以買幾個冰淇淋。
Example :
Input: costs = [1,3,2,4,1], coins = 7
Output: 4
Explanation: The boy can buy ice cream bars at indices 0,1,2,4 for a total
price of 1 + 3 + 2 + 1 = 7.
Input: costs = [10,6,8,7,7,8], coins = 5
Output: 0
Explanation: The boy cannot afford any of the ice cream bars.
法一 排序
思路：
1.很直觀的想法就是從價錢低的天數開始買冰淇淋直到自己沒錢。
2.我們先排序價錢，再遍歷一次價錢一邊減去花費一邊統計數量，直到錢不夠為止。
3.時間複雜度O(nlogn + n)
Java Code：
---------------------------------
class Solution {
public int maxIceCream(int[] costs, int coins) {
int iceCreamBars = 0;
Arrays.sort(costs);
for (int cost : costs) {
if (cost > coins) break;
coins -= cost;
iceCreamBars++;
}
return iceCreamBars;
}
}
---------------------------------
法二 counting sort
思路：
1.因為測資範圍是 1 <= costs[i] <= 10^5 全為正數且數量不大，所以我們可以
對價錢改用counting sort來排序。
2.前半部份的邏輯大致與前面相同。
3.排序完之後每次取「買這個價格的所有冰淇淋」和「買這個價格的冰淇淋直到沒錢」
兩者數量取較小的值並累加。
舉例來說：
`numOfCosts[2]` = 2, coins = 10 ，最多只能買兩個，因為只有2個
`numOfCosts[2]` = 10, coins = 10 ，最多只能買5個，之後就沒錢了
4.時間複雜度O(n)
Java Code：
----------------------------------
class Solution {
public int maxIceCream(int[] costs, int coins) {
int maxCost = 0;
for (int cost : costs) {
maxCost = Math.max(maxCost, cost);
}
int[] numOfCosts = new int[maxCost + 1];
for (int cost : costs) {
numOfCosts[cost]++;
}
int iceCreamBars = 0;
for (int cost = 1; cost <= maxCost; cost++) {
if (numOfCosts[cost] == 0) {
continue;
}
if (coins < cost) {
break;
}
int count = Math.min(numOfCosts[cost], coins / cost);
coins -= count * cost;
iceCreamBars += count;
}
return iceCreamBars;
}
}
----------------------------------
--
https://i.imgur.com/tdaniED.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.43.121 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672983899.A.403.html