本次题目
135 分发糖果
- 局部最优:分别讨论左右相邻孩子。从前向后遍历,只要右边评分比左边高,则右边孩子糖果加1,否则为1;从后向前遍历,只要左边评分比右边高,则左边孩子糖果加1。此时针对每个孩子都有两个选择(比左边大1或比右边大1),选择两者中最大的才满足条件。
- 注意:数组求和先转为stream后(Arrays.stream())再求和(sum())。
class Solution {
public int candy(int[] ratings) {
//分别讨论左右相邻孩子
int[] resFromLeft = new int[ratings.length];
int[] resFromRight = new int[ratings.length];
//初始化
resFromLeft[0] = 1;
resFromRight[resFromRight.length - 1] = 1;
//从前向后遍历
for(int i = 1; i < ratings.length; i++){
//只要右边评分比左边高,则右边孩子糖果加1,否则为1
if(ratings[i] > ratings[i - 1]){
resFromLeft[i] = resFromLeft[i - 1] + 1;
}else{
resFromLeft[i] = 1;
}
}
//从后向前遍历
for(int j = ratings.length - 1; j > 0; j--){
//只要左边评分比右边高,则左边孩子糖果加1
if(ratings[j - 1] > ratings[j]){
resFromRight[j - 1] = resFromRight[j] + 1;
}else{
resFromRight[j - 1] = 1;
}
}
//针对每个孩子选择两者中最大的才满足条件
for(int i = 0; i < resFromRight.length; i++){
if(resFromRight[i] < resFromLeft[i]) resFromRight[i] = resFromLeft[i];
}
//返回结果
return Arrays.stream(resFromRight).sum();
}
}
406 根据身高重建队列
- 局部最优:分别考虑身高和前面更高的人个数。先按身高从高到低排序(身高相同前面更高的人个数小的放前面),定义队列(LinkedList),然后按照前面更高的人个数插入。
- 注意:构造器升序o1-o2;降序o2-o1(o1为右边元素,返回值小于0时交换两者位置)。按下标插入LinkedList中add(index, element)。将LinkedList转为二维数组toArray(new int[二维数组的行][可省略])。
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)
LinkedList queue = new LinkedList<>();
//然后按照前面更高的人个数插入
for(int[] p : people){
queue.add(p[1], p);
}
//返回结果
return queue.toArray(new int[people.length][]);
}
}