题目
题解 贪心+排序
贪心,顾名思义就是贪到最多的,本题要求一定数额的钱,要获得最多数量的雪糕,那以我们平常人的思维去买,就是:
-
先买最便宜的
-
然后再买次便宜的
-
…
因此我们可以先将数组排序,排序后从头开始遍历,一直算到前i个雪糕价钱之和大于coin时停止(或者一直小于coin就遍历到数组尾部停止),我们以官方例1来讲解,coins = 7 , 数组costs = [1, 3, 2, 4, 1],先排序,排完序后进行如下操作:
到3时,coin剩余为0,则退出,最多可得到4根雪糕
因此我们可以编写如下代码
java版本:
class Solution {
public int maxIceCream(<