重生之我在代码随想录刷算法第二十五天 | 134. 加油站、135. 分发糖果、860.柠檬水找零、406.根据身高重建队列
参考文献链接：代码随想录
本人代码是Java版本的，如有别的版本需要请上代码随想录网站查看。
134. 加油站
解题思路
这道题目是求从哪个起始位置开始走可以跑完全程回到起始位置。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。
代码示例
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int totalSum = 0;
int curSum = 0;
int start = 0;
for(int i = 0;i < gas.length;i++){
totalSum += gas[i] - cost[i];
curSum += gas[i] - cost[i];
if(curSum < 0){
start = i + 1;
curSum = 0;
}
}
if(totalSum < 0){
return -1;
}
return start;
}
}
135. 分发糖果
解题思路
这道题目是要比较小孩得分去分发糖果，比较的时候就要考虑两种情况，跟左边相比哪边大，跟右边相比哪边大。第一次做的时候是同时进行比较的，结果发现最后没有得到想要的结果，自己模拟了一次过程才发现，两者兼顾顾此失彼啊
所以这种两边比较的题目一定要分两次去比较，第一次从左往右，右大于左则右等于左+1。
第二次从右往左，但不能只是左大于右就左等于右+1.因为还要兼顾这个大于其左边的值，所以当左大于右，左值=max（左，右+1），比较这两者谁更大就留下谁。右+1可能没有原来的左值大，这样左值就可能无法满足大于左左值了
代码示例
class Solution {
public int candy(int[] ratings) {
int len = ratings.length;
int[] candyVec = new int[len];
candyVec[0] = 1;
for (int i = 1; i < len; i++) {
candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;
}
for (int i = len - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
}
}
int ans = 0;
for (int num : candyVec) {
ans += num;
}
return ans;
}
}
860.柠檬水找零
解题思路
这道题比之前的都简单，找零是我们日常生活很常见的一个操作，这道题创建一个存钱的数组即可。
然后通过if判断每次什么钱该增什么该减，找零的时候能用大钱先用大的，防止小钱用完后续没法找零。
代码示例
class Solution {
public boolean lemonadeChange(int[] bills) {
if(bills.length == 1 && bills[0] != 5){
return false;
}
int[] money = new int[2];
for(int i = 0;i < bills.length;i++){
if(bills[i] == 5){
money[0]++;
}
if(bills[i] == 10){
money[1]++;
if(i != 0 && money[0]-- <= 0){
return false;
}
}
if(bills[i] == 20){
if(money[1] > 0 && money[0] > 0){
money[1]--;
money[0]--;
}else if(money[0] > 2){
money[0] = money[0] - 3;
}else{
return false;
}
}
}
return true;
}
}
406.根据身高重建队列
解题思路
这道题目又属于两个维度，不要一起考虑先处理一个。
我们先按身高从高到低排序，排序之后每一个数组前面的都是比他身高高的，所以我们只需要遍历数组把它放入数组中第二个维度数的位置即可。这样它前面的都比他高，说明他在这个位置刚好满足条件。
代码示例
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[]> result = new LinkedList<>();
for(int[] array : people){
result.add(array[1],array);
}
return result.toArray(new int[people.length][]);
}
}
原文地址：https://blog.csdn.net/qq_73210658/article/details/142992198
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！