算法训练营day34

一、柠檬水找零

逻辑比较好理解，找钱时先用最大的面额，再使用小的面额，因为小的面额更灵活

class Solution {
    public boolean lemonadeChange(int[] bills) {
//使用三个变量记录三种面值的钞票的数量，返还零钱从大到小返还，也限制了顾客给钱的金额只有5/10/15三种情况
    int five = 0;
    int ten = 0;
    
    for(int i = 0; i < bills.length; i++){
        if(bills[i] == 5){
            five++;
        }else if(bills[i] == 10){
            five--;
            ten++;
        }else if(bills[i] == 20){
            if(ten > 0){
                ten--;
                five--;
            }else{
                five -= 3;
            }
        }
        if(five < 0 || ten < 0) return false;
    }
    return true;
    }
}

二、根据身高重建队列

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a,b) -> {
            //身高从大到小排列，升高相同k小的站前面;相同升序，相反降序
//核心思想：高个子先站好位，矮个子插入到K位置上，前面肯定有K个高个子，矮个子再插到前面也满足K的要求
            if(a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });

        LinkedList<int[]> que = new LinkedList<>();

        for(int[] p : people){
            que.add(p[1],p);
        }

        return que.toArray(new int[people.length][]);
    }
}

三、用最少数量的箭引爆气球

在Java中，比较器的compare方法的返回值约定如下：

• 返回一个负整数，表示第一个参数应该排在第二个参数之前；
• 返回一个正整数，表示第一个参数应该排在第二个参数之后；
• 返回0，表示两个参数相等，顺序不变。

代码的思路是首先对气球的结束位置进行排序，然后从左到右遍历气球数组。我们使用pos变量来记录当前箭的位置，初始值为第一个气球的结束位置。然后，我们依次遍历每个气球，如果当前气球的起始位置大于pos，说明这个气球无法被当前箭射破，我们需要更新箭的位置为当前气球的结束位置，并将箭的数量增加1

class Solution {
    public int findMinArrowShots(int[][] points) {
         if (points.length == 0) {
            return 0;
        }
        //将数组进行排序，在Java中，比较器的compare方法的返回值约定如下：
        //返回一个负整数，表示第一个参数应该排在第二个参数之前；
        //返回一个正整数，表示第一个参数应该排在第二个参数之后；
        //返回0，表示两个参数相等，顺序不变。
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] point1, int[] point2) {
                if (point1[1] > point2[1]) {
                    return 1;
                } else if (point1[1] < point2[1]) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });
        // 初始化值为排序后的第一个右边界，也就是最小的右边界
        int pos = points[0][1];
        int ans = 1; //初始化，需要一支箭
        for (int[] balloon: points) { //遍历气球
            if (balloon[0] > pos) {  //如果气球的起始位置大于 pos，说明这支箭无法射到该气球，需要增加一支箭，并更新pos的位置
                pos = balloon[1];
                ++ans;
            }
        }
        return ans;
    }
}