Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/01/06 13:44)推噓5(5推 0噓 0→)

留言5則, 5人參與討論串181/719 (看更多)

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