860 柠檬水找零
5， 10 的逻辑好想，在20时，需要考虑贪心
即优先10的找零
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0;
int ten = 0;
for (int i = 0; i < bills.length; i++){
if (bills[i] == 5){
five++;
}
if (bills[i] == 10){
if (five == 0) return false;
ten++;
five--;
}
if (bills[i] == 20){
if (ten > 0){
ten--;
five--;
} else {
five -= 3;
}
if (five < 0) return false;
}
}
return true;
}
}
|
406 根据身高重建队列
此题有两个维度，需要权衡两个维度，像是分发糖果：先从前遍历，确定右边，再从后遍历确定左边
此题先利用身高和k排序，身高越高，k越低的在前面之后再利用k值调整顺序
写法：
array.sort写法，第二个值越小排在前面，身高越大排在前面
linkedlist在index处添加的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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);
}
return que.toArray(new int[people.length][]);
}
}
|
452 用最少数量的箭引爆气球
先排序，之后对比气球，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, (a,b) -> Integer.compare(a[0], b[0]));
int count = 1;
for (int i = 1; i < points.length; i++){
if (points[i][0] > points[i-1][1]){
count++;
} else {
points[i][1] = Math.min(points[i][1], points[i-1][1]);
}
}
return count;
}
}
|