LeetCode——贪心篇（二）

刷题顺序及思路来源于代码随想录，网站地址：https://programmercarl.com

134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

import java.util.Scanner;/*** @author light* @Description 加油站** 在一条环路上有n个加油站，其中第 个加油站有汽油 gas[i] 升。** 你有一辆油箱容量无限的的汽车，从第i个加油站开往第 i+1个加油站需要消耗汽油cost[i]升。* 你从其中的一个加油站出发，开始时油箱为空。** 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，* 则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。** （思路--贪心：* 从第i个站点开始，如果剩余油量和<0,则从第i+1个站点开始从新作为起点开始计算** @create 2023-09-06 8:24*/
public class CanCompleteCircuitTest {public static void main(String[] args) {Scanner input=new Scanner(System.in);int n=input.nextInt();int[] gas=new int[n];  //汽油for (int i = 0; i < n; i++) {gas[i]=input.nextInt();}int[] cost=new int[n]; //消耗汽油for (int i = 0; i < n; i++) {cost[i]=input.nextInt();}System.out.println(canCompleteCircuit(gas, cost));}public static int canCompleteCircuit(int[] gas, int[] cost) {/*暴力解法：直接模拟）遍历每一个加油站为起点的情况，模拟一圈。如果跑了一圈，中途没有断油，而且最后油量大于等于0，说明这个起点是ok的。for (int i = 0; i < gas.length; i++) {int rest=gas[i]-cost[i];  //剩余油量int index=(i+1)% gas.length;while(rest>0&&index!=i){ //模拟以i为起点，行驶一圈rest+=gas[index]-cost[index];index=(index+1)% gas.length;  //控制下标变化}if(rest>=0&&index==i){return i;//回到起始位置，如果剩余油量等于0，则返回下标}}return -1;*///贪心int curSum=0; //统计每个站点剩余油量（累加int index=0;int totalSum=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;}else {return index;}}
}

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

import java.util.Scanner;/*** @author light* @Description 分发糖果** (贪心：* 1.从左向右遍历，比较右边大于左边的值* 2.从右向左遍历，比较左边大于右边的值* @create 2023-09-06 10:01*/
public class CandyTest {public static void main(String[] args) {Scanner input=new Scanner(System.in);int n=input.nextInt();int[] ratings=new int[n];for (int i = 0; i < n; i++) {ratings[i]=input.nextInt();}System.out.println(candy(ratings));}public static int candy(int[] ratings) {int[] canVec=new int[ratings.length];canVec[0]=1;//从左向右遍历for (int i = 1; i < ratings.length; i++) {//if(ratings[i]>ratings[i-1]){//	canVec[i]=canVec[i-1]+1;//}else {//	canVec[i]=1;//}canVec[i]=(ratings[i]>ratings[i-1])?canVec[i-1]+1:1;}//从右向左遍历for (int i = ratings.length-2; i >=0; i--) {if(ratings[i]>ratings[i+1]){canVec[i]=Math.max(canVec[i+1]+1,canVec[i]);}}int sum=0;for (int i = 0; i < canVec.length; i++) {sum+=canVec[i];}return sum;}
}

860. 柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

import java.util.Scanner;/*** @author light* @Description 柠檬水找零** (思路：有三种情况* 1.账单是5，直接收下* 2.账单是10，先消耗5，在增加10* 3.账单是20，优先消耗10，在消耗5（贪心，美元5更万能* @create 2023-09-06 10:25*/
public class LemonadeChangeTest {public static void main(String[] args) {Scanner input=new Scanner(System.in);int n=input.nextInt();int[] bills=new int[n];for (int i = 0; i < n; i++) {bills[i]=input.nextInt();}System.out.println(lemonadeChange(bills));}public static boolean lemonadeChange(int[] bills) {int five=0,ten=0,twenty=0;for (int bill : bills) {if(bill==5){five++;}if(bill==10){if(five<=0){return false;}five--;ten++;}if(bill==20){if(five>0&&ten>0){ten--;five--;twenty++;}else if(five>=3){five-=3;twenty++;}else {return false;}}}return true;}
}

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Scanner;/*** @author light* @Description 根据身高重建队列** （思路：遇到有两个维度进行判断时，一定要先确定一个维度，在确定另一个维度** 先对身高进行排序* @create 2023-09-06 10:41*/
public class ReconstructQueueTest {public static void main(String[] args) {Scanner input=new Scanner(System.in);int n=input.nextInt();int[][] people=new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {people[i][j]=input.nextInt();}}people=reconstructQueue(people);for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-1; j++) {System.out.print(people[i][j]+" ");}}System.out.println(people[n - 1][n - 1]);}public static int[][] reconstructQueue(int[][] people) {//1.现根据身高进行排序Arrays.sort(people, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {if(o1[0]==o2[0]){return o1[1]-o2[1]; //如果身高相同，则将k按从小到大排序}return o2[0]-o1[0]; //将身高从大到小排序}});LinkedList<int[]> list=new LinkedList<>();for (int[] p : people) {list.add(p[1],p);    //Linkedlist.add(index, value)，会將value插入到指定index里。}return list.toArray(new int[people.length][]);}
}