Leetcode 1833

1833. 雪糕的最大数量

夏天到了，终于放暑假了！LeetCode也叫人吃雪糕了

由题意可知，要买最多雪糕，可以想出贪心

第一种做法

public int maxIceCream(int[] costs, int coins) {
        int cnt = 0;
        Arrays.sort(costs);//sorted,从最便宜的开始买
        for(int cost : costs){
            if(coins >= cost){//超过即退出
                coins -= cost;
                cnt++;
            }else{
                break;
            }
        }
        return cnt;
    }

第二种排序，用计数排序来实现

public int maxIceCream2(int[] costs, int coins) {
        int[] freq = new int[100001];
        for (int cost:costs){
            //用数组模拟哈希表记录出现次数
            freq[cost]++;
        }

        int cnt = 0;
        for (int i = 1; i <= 100000; i++) {
            if (coins >= i) {//超过即退出
                int curCount = Math.min(freq[i], coins / i);//判断可以买多少支雪糕
                cnt += curCount;
                coins -= i * curCount;
            } else {
                break;
            }
        }
        return cnt; 
    }