2018-08-19 LeetCode 贪心算法

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
//分数一样的不用给一样的数量，可以只给1

class Solution {
    public int candy(int[] ratings) {
        if(ratings==null||ratings.length==0){
            return 0;
        }
        int len = ratings.length;
        int[] candy = new int[len];
        candy[0]=1;
        //从左至右，右边的比左边的大，就可以把右边的糖果数量设置为左边的加1
        for(int i=1;i<len;i++){
            if(ratings[i]>ratings[i-1]){
                candy[i]=candy[i-1]+1;
            }else{
                candy[i]=1;
            }
        }
        //从右边到左边，左边比右边的大，并且原来左边的糖果数量小于等于右边的，就可以把左边的糖果数量设置为右边的加1；
        for(int i=len-2;i>=0;i--){
            if((ratings[i]>ratings[i+1])&& (candy[i]<=candy[i+1])){
                candy[i]=candy[i+1]+1;
            }
        }
        int res=0;
        for(int i=0;i<len;i++){
            res+=candy[i];
        }
        return res;
    }
}

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
按照h从高到低，k从小到大排序，依次插入到list的k位置

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        if(people == null || people.length == 0 || people[0].length == 0)
            return new int[0][0];

        Arrays.sort(people, new Comparator<int[]>(){
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) return o1[1] - o2[1];
                return o2[0] - o1[0];
            }
        });

        int n = people.length;
        ArrayList<int[]> tmp = new ArrayList<>();

        for(int i = 0; i < n; i++)
            tmp.add(people[i][1], people[i]);

        return tmp.toArray(new int[tmp.size()][]);
    }
}