算法刷题日志——贪心

分发糖果

相邻的学生中，评分高的学生必须获得更多的糖果 ，所以需要分别从左往右和从右往左遍历，然后取两次遍历结果的最大值就是最少糖果的数目了。

class Solution {
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        int[] right = new int[ratings.length];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        //从左往右遍历，跳过首尾节点。
        for(int i = 1; i < ratings.length; i++)
            if(ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
        int count = left[ratings.length - 1];
        for(int i = ratings.length - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
            count += Math.max(left[i], right[i]);
        }
        return count;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

根据身高重建队列

就是对二维数组进行排序。需要重写sort()方法中的Comparator比较器
可使用lambda表达式对比较器进行简写 ->
含义：对于一个已定义的二位数组a进行如下规则排序,首先按照每一个对应的一维数组第一个元素进行升序排序（即a[][0]）,若第一个元素相等,则按照第二个元素进行升序排序（a[][1]）， 若不相等，则第一个元素进行降序排序。

Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });
1
2
3
4

模拟情景如下：
排序完的people： [[7,0], [7,1], [6,1], [5,0], [5,2]，[4,4]]
插入的过程：
插入[7,0]：[[7,0]]
插入[7,1]：[[7,0],[7,1]]
插入[6,1]：[[7,0],[6,1],[7,1]]
插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> {
            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);//p[1]代表取每个数组p对应的第二位元素的数值(个数)，即要插入的下标
        }
 
        return que.toArray(new int[people.length][]);
    }
}
 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19