[LeetCode] #1833 Maximum Ice Cream Bars (Medium)
LeetCode 第 1833 題 Maximum Ice Cream Bars，難度 Medium
用 PHP 解 LeetCode 系列，Maximum Ice Cream Bars，屬於 Medium
原始題目
It is a sweltering summer day, and a boy wants to buy some ice cream bars.
At the store, there are n ice cream bars. You are given an array costs of length n, where costs[i] is the price of the ith ice cream bar in coins. The boy initially has coins coins to spend, and he wants to buy as many ice cream bars as possible.
Return the maximum number of ice cream bars the boy can buy with coins coins.
Note: The boy can buy the ice cream bars in any order.
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.
Input: costs = [1,6,3,1,2,5], coins = 20
Output: 6
Explanation: The boy can buy all the ice cream bars for a total price of 1 + 6 + 3 + 1 + 2 + 5 = 18.
題目分析
- 輸入所有冰淇淋的價錢列表
costs，以及男孩擁有的所有錢coins - 計算男孩最多可以買幾支冰淇淋
解題過程
這邊採用所謂的：貪婪演算法
，理論上能買最多冰淇淋的情況下就是全部買便宜的
所以先對輸入的冰淇淋價錢列表 costs 做排序，排序完之後就是簡單的計算
當剩餘的錢比冰淇淋多，可購買冰淇淋數量就 +1，並且扣掉買冰的錢
一般會做 coins >= 0 的判斷
如果金額小於等於 0，合理推斷他不可能再買任何冰淇淋
但是這樣會多一個判斷式，執行時間和記憶體用量反而會上升
原本以為用 break 終止迴圈會更省資源的！
在一般情況下也不可能存在價錢是負數的冰淇淋，所以就不做剩餘金額判斷
如果不是特別要跑數字還是應該加一下，比較安全
class Solution {
/**
* @param Integer[] $costs
* @param Integer $coins
* @return Integer
*/
function maxIceCream($costs, $coins) {
sort($costs);
$ice_cream_num = 0;
foreach($costs as $cost) {
if($coins >= $cost) {
$ice_cream_num += 1;
$coins -= $cost;
}
}
return $ice_cream_num;
}
}
結果
