第八章 贪心算法 part03
134. 加油站
本题有点难度，不太好想，推荐大家熟悉一下方法二
https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html
错误：
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int num = gas.length;
int[] res = new int[num];
int i = 0;
// 计算 cost - gas 的差值并存储到 res 数组中
while(i < num){
res[i] = gas[i] - cost[i];
i++;
}
int index = 0;
int curSum = 0;
int count = 1;
int j = 0;
// 开始寻找可以绕行一圈的起始点
while(count <= num){
if(j == num) j = 0;
curSum += res[j];
if(curSum < 0){
index = j + 1;
count = 1;
curSum = 0;
}else{
count++;
}
j++;
}
if(count == num + 1) {
return index;
}
return -1;
}
}
//时间复杂度过高
class Solution {
public 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);
curSum = 0;
}
}
if (totalSum < 0) return -1;
return index;
}
}
135. 分发糖果
本题涉及到一个思想，就是想处理好一边再处理另一边，不要两边想着一起兼顾，后面还会有题目用到这个思路
https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html
class Solution {
public int candy(int[] ratings) {
int[] candy = new int[ratings.length];
for (int i = 0; i < candy.length; i++) {
candy[i] = 1;
}
for(int i = 1; i < candy.length; i ++){
if(candy[i-1] < candy[i]) candy[i] = candy[i-1] + 1;
}
for(int i = candy.length - 2; i >= 0; i --){
if(candy[i] > candy[i+1]) candy[i] = candy[i+1] + 1;
}
int sum = 0;
for(int i : candy){
sum += i;
}
return sum;
}
}
正确：
class Solution {
public int candy(int[] ratings) {
int[] candy = new int[ratings.length];
for (int i = 0; i < candy.length; i++) {
candy[i] = 1;
}
for(int i = 1; i < candy.length; i ++){
if(ratings[i-1] < ratings[i]) candy[i] = candy[i-1] + 1;
}
for(int i = candy.length - 2; i >= 0; i --){
if(ratings[i] > ratings[i+1]) candy[i] = Math.max(candy[i+1] + 1 , candy[i]);
}
int sum = 0;
for (int i = 0; i < candy.length; i++) {
sum += candy[i];
}
return sum;
}
}
860.柠檬水找零
本题看上好像挺难，其实很简单，大家先尝试自己做一做。
https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html
class Solution {
public boolean lemonadeChange(int[] bills) {
int fv = 0, tn = 0, tv = 0;
for(int i = 0; i < bills.length; i ++){
if(bills[i] == 5) fv ++;
if(bills[i] == 10) {
tn ++;
if(fv == 0) return false;
fv --;
}
if(bills[i] == 20) {
if(tn > 0 && fv > 0){
tn --;
fv --;
}else if(fv > 2){
fv = fv - 3;
}else{
return false;
}
}
}
return true;
}
}
406.根据身高重建队列
本题有点难度，和分发糖果类似，不要两头兼顾，处理好一边再处理另一边。
https://programmercarl.com/0406.%E6%A0%B9%E6%8D%AE%E8%BA%AB%E9%AB%98%E9%87%8D%E5%BB%BA%E9%98%9F%E5%88%97.html
难点在于基础知识上
class Solution {
public int[][] reconstructQueue(int[][] people) {
//根据身高排序 身高高的放前面
Arrays.sort(people, (a, b) -> {
if(a[0] == b[0]) return a[1] - b[1];
else return b[0] - a[0];
});
// 创建列表
List<int[]> list = LinkedList<>();
for(int i = 0; i < people.length; i ++){
list.add(i, i[1]);
}
return list.toArray(new int[][] result);
}
Line 9: error: illegal start of expression
List<int[]> list = LinkedList<>();
^
Line 9: error: -> expected
List<int[]> list = LinkedList<>();
^
Line 13: error: array dimension missing
return list.toArray(new int[][] result);
^
Line 13: error: ';' expected
return list.toArray(new int[][] result);
List<int[]> list = new LinkedList<>();
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];
});
// 创建列表
List<int[]> list = new LinkedList<>();
for(int[] i : people){
list.add(i[1], i);// 先是序号，再是元素
}
return list.toArray(new int[people.length][]);
}
}
