html网站标题怎么做,软文广告经典案例200字,如何创建链接,网店美工毕业设计刷题顺序及思路来源于代码随想录#xff0c;网站地址#xff1a;https://programmercarl.com 134. 加油站
在一条环路上有 n 个加油站#xff0c;其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车#xff0c;从第 i 个加油站开往第 i1 个加油站需要消耗…刷题顺序及思路来源于代码随想录网站地址https://programmercarl.com 134. 加油站
在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 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个加油站开往第 i1个加油站需要消耗汽油cost[i]升。* 你从其中的一个加油站出发开始时油箱为空。** 给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周* 则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。** 思路--贪心* 从第i个站点开始如果剩余油量和0,则从第i1个站点开始从新作为起点开始计算** create 2023-09-06 8:24*/
public class CanCompleteCircuitTest {public static void main(String[] args) {Scanner inputnew Scanner(System.in);int ninput.nextInt();int[] gasnew int[n]; //汽油for (int i 0; i n; i) {gas[i]input.nextInt();}int[] costnew 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 restgas[i]-cost[i]; //剩余油量int index(i1)% gas.length;while(rest0index!i){ //模拟以i为起点行驶一圈restgas[index]-cost[index];index(index1)% gas.length; //控制下标变化}if(rest0indexi){return i;//回到起始位置如果剩余油量等于0则返回下标}}return -1;*///贪心int curSum0; //统计每个站点剩余油量累加int index0;int totalSum0;for (int i 0; i gas.length; i) {curSumgas[i]-cost[i];totalSumgas[i]-cost[i];if(curSum0){index(i1)% gas.length;curSum0;}}if(totalSum0){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 inputnew Scanner(System.in);int ninput.nextInt();int[] ratingsnew 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[] canVecnew 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[i1]){canVec[i]Math.max(canVec[i1]1,canVec[i]);}}int sum0;for (int i 0; i canVec.length; i) {sumcanVec[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 inputnew Scanner(System.in);int ninput.nextInt();int[] billsnew 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 five0,ten0,twenty0;for (int bill : bills) {if(bill5){five;}if(bill10){if(five0){return false;}five--;ten;}if(bill20){if(five0ten0){ten--;five--;twenty;}else if(five3){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 inputnew Scanner(System.in);int ninput.nextInt();int[][] peoplenew int[n][n];for (int i 0; i n; i) {for (int j 0; j n; j) {people[i][j]input.nextInt();}}peoplereconstructQueue(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 Comparatorint[]() {Overridepublic int compare(int[] o1, int[] o2) {if(o1[0]o2[0]){return o1[1]-o2[1]; //如果身高相同则将k按从小到大排序}return o2[0]-o1[0]; //将身高从大到小排序}});LinkedListint[] listnew LinkedList();for (int[] p : people) {list.add(p[1],p); //Linkedlist.add(index, value)会將value插入到指定index里。}return list.toArray(new int[people.length][]);}
}
