代码随想录算法训练营第二十九天-134加油站、135分发糖果、860柠檬水找零、406根据身高重建队列
初步题解
134 加油站
题目链接：(https://leetcode.cn/problems/gas-station)
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
31
32
33
34
35
36
37
38
|
public static int canCompleteCircuit(int[] gas, int[] cost) {
int startIndex = -1;
int sum = 0;
for (int i = 0, j = i; i < gas.length * 2 && startIndex < gas.length; i++, j++) {
if (startIndex != -1 && i - startIndex == gas.length) {
break;
}
if (sum == 0 && i < gas.length) {
startIndex = i;
}
if (j >= gas.length) {
j = i - gas.length;
}
int diff = gas[j] - cost[j];
sum += diff;
if (sum < 0) {
startIndex = -1;
sum = 0;
}
}
return startIndex;
}
|
135 分发糖果
题目链接：(https://leetcode.cn/problems/candy)
提前看了一部分解析，不能同时考虑左右（没看真的想不到🤕）。但是很慢。看了解析，和我写的一样。
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
| public static int candy(int[] ratings) {
if (ratings.length <= 1) {
return ratings.length;
}
int[] result = new int[ratings.length];
result[0] = 1;
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
result[i] = result[i - 1] + 1;
} else {
result[i] = 1;
}
}
System.out.println(Arrays.toString(result));
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1] && result[i] <= result[i + 1]) {
result[i] = result[i + 1] + 1;
}
}
System.out.println(Arrays.toString(result));
return Arrays.stream(result).sum();
}
|
860 柠檬水找零
题目链接：(https://leetcode.cn/problems/lemonade-change)
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
| public boolean lemonadeChange(int[] bills) {
Map<Integer, Integer> map = new HashMap<>();
map.put(5, 0);
map.put(10, 0);
map.put(20, 0);
for (int bill : bills) {
map.put(bill, map.get(bill) + 1);
if (bill == 10) {
if (map.get(5) < 1) {
return false;
}
map.put(5, map.get(5) - 1);
}
if (bill == 20) {
if (map.get(5) >= 1 && map.get(10) >= 1) {
map.put(5, map.get(5) - 1);
map.put(10, map.get(10) - 1);
} else if (map.get(5) >= 3){
map.put(5, map.get(5) - 3);
} else {
return false;
}
}
}
return true;
}
|
406 根据身高重建队列
题目链接：(https://leetcode.cn/problems/queue-reconstruction-by-height)
没有思路，虽然看了提示要和 135 一样分开处理，但是还是没有思路。
看解析
134 加油站
题解：(https://programmercarl.com/0134.加油站.html)
看了解析，明明思路是一样的，就是慢一点。❗忽略了一个点，如果总和大于 0， 那么必定有解。无语解析里那个 totalSum 真的太妙了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public static int canCompleteCircuit(int[] gas, int[] cost) {
int curSum = 0;
int totalSum = 0;
int index = 0;
for (int i = 0; i < gas.length; i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) {
index = (i + 1) % gas.length;
curSum = 0;
}
}
if (totalSum < 0) {
return -1;
}
return index;
}
|
135 分发糖果
解析：(https://programmercarl.com/0135.分发糖果.html)
860 柠檬水找零
解析：(https://programmercarl.com/0860.柠檬水找零.html)
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
| 不用HashMap，直接两个int进行加减🤡
public boolean lemonadeChange(int[] bills) {
int five = 0;
int ten = 0;
for (int bill : bills) {
if (bill == 5) {
five++;
} else if (bill == 10) {
ten++;
five--;
if (five < 0) {
return false;
}
} else if (bill == 20) {
if (five >= 1 && ten >= 1) {
five--;
ten--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}
|
406 根据身高重建队列
解析：(https://programmercarl.com/0406.根据身高重建队列.html)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (o1, o2) -> {
if (o1[0] == o2[0]) {
return o1[1] - o2[1];
}
return o2[0] - o1[0];
});
LinkedList<int[]> list = new LinkedList<>();
for (int[] person : people) {
list.add(person[1], person);
}
return list.toArray(new int[people.length][]);
}
|