贪心
1个维度【生活常识】
135. 分发糖果
class Solution {
public boolean lemonadeChange(int[] bills) {
int[] arr = new int[2];
for (int bill : bills) {
if (bill == 5){
arr[0]++;
}else if (bill == 10){
if (arr[0] > 0){
arr[0]--;
arr[1]++;
}else {
return false;
}
}else { // 20【fw：不会进行收集】
if (arr[1] > 0){ // 有 10 块
arr[1]--;
if (arr[0] > 0){
arr[0]--;
}else {
return false;
}
}else { // 没有 10 块钱
if (arr[0] >= 3){
arr[0] -= 3;
}else {
return false;
}
}
}
}
return true;
}
}
2个维度【要分别考虑：挑选合适的】
406. 根据身高重建队列
先身高，同时 count 小的在前 ====> 保证当前坐标的前方都是比自己大于等于的 ===> 然后再去一点点微调整
class Solution {
public int[][] reconstructQueue(int[][] people) {
List<man> list = new ArrayList<>();
for (int[] person : people) {
list.add(new man(person[0], person[1]));
}
Collections.sort(list, (o1, o2) -> {
if (o1.height != o2.height) {
return o2.height - o1.height; // 身高大的在前
}
return o1.count - o2.count; // count 小的在前
});
List<man> men = new ArrayList<>();
int[][] arr = new int[people.length][2];
for (int i = 0; i < arr.length; i++) {
man man = list.get(i);
if (man.count == i){
men.add(man);
}else {
men.add(man.count, man);
}
}
for (int i = 0; i < arr.length; i++) {
man man = men.get(i);
arr[i][0] = man.height;
arr[i][1] = man.count;
}
return arr;
}
}
class man{
int height;
int count;
public man(int height, int count) {
this.height = height;
this.count = count;
}
}