当前位置：首页 > ai >正文

代码随想录算法训练营第二十五天

ai 2025/7/15 14:22:06

LeetCode题目:

134. 加油站
135. 分发糖果
860. 柠檬水找零
406. 根据身高重建队列
1399. 统计最大组的数目(每日一题)

其他:

今日总结
往期打卡

134. 加油站

跳转: 134. 加油站

学习: 代码随想录公开讲解

问题:

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

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

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

思路:

只要油大于等于消费就一定可以找到一个位置满足形成,因为整个数组切割为二,一段中耗不起油,剩下的部分油溢出就会更多.
由于总量大于等于0,总能找到加上某一块满足当前块所需油量

复杂度:

时间复杂度: $O (n)$
空间复杂度: $O (1)$

代码:

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int curSum = 0;int totalSum = 0;int ans = 0;for(int i=0;i<gas.length;i++){if(curSum<0){ans = i;curSum = 0;}int tmp = gas[i]-cost[i];totalSum+=tmp;curSum+=tmp;}return totalSum<0?-1:ans;}
}

135. 分发糖果

跳转: 135. 分发糖果

学习: 代码随想录公开讲解

问题:

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

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

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

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

思路:

贪心发糖,从前往后看递增至少比前面多1,从后往前看递增比后面多1

或者关注三种状态,递增递减与水平,水平是加上去除头部的长度,递增是加上2+…+(长度+1),递减是1+…+长度但需要判断递减前首部分糖个数是否小于长度+1

复杂度:

时间复杂度: $O (n)$
空间复杂度: $O (n)$

代码(贪心):

class Solution {public int candy(int[] ratings) {int n = ratings.length;int[] ans = new int[n];Arrays.fill(ans,1);for(int i=1;i<n;i++){if(ratings[i]>ratings[i-1]) ans[i] = ans[i-1]+1;}for(int i=n-2;i>=0;i--){if(ratings[i]>ratings[i+1]) ans [i] = Math.max(ans[i],ans[i+1]+1);}int res = 0;for(int i:ans){res += i;}return res;}
}

代码(三种状态):

class Solution {public int candy(int[] ratings) {int preMax = 0;int state = 0;int l = 0;int pre = ratings[0];int[] sums = new int[20001];int tmp = 0;for (int i = 0; i <= 20000; i++) {tmp += i;sums[i] = tmp;}int ans = 0;for (int i : ratings) {tmp = i > pre ? 1 : i < pre ? -1 : 0;if (state == tmp) {l++;} else {if (state == 0) {ans += l;preMax = 1;} else if (state > 0) {ans += sums[l + 1] - 1;preMax = l + 1;} else if (state < 0) {ans += sums[l];if (l + 1 > preMax) {ans += l + 1 - preMax;}preMax = 1;}state = tmp;l=1;}pre = i;}if (state == 0) {ans += l;preMax = 1;} else if (state > 0) {ans += sums[l + 1] - 1;preMax = l + 1;} else if (state < 0) {ans += sums[l];if (l + 1 > preMax) {ans += l + 1 - preMax;}preMax = 1;}return ans;}
}

860. 柠檬水找零

跳转: 860. 柠檬水找零

学习: 代码随想录公开讲解

问题:

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

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

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

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

思路:

贪心,能找10块不找5块

复杂度:

时间复杂度: $O (n)$
空间复杂度: $O (1)$

代码:

class Solution {public boolean lemonadeChange(int[] bills) {int five = 0;int ten = 0;for(int i:bills){if(i==5) five++;else if(i==10){if(five<=0) return false;ten++;five--;}else{if(ten>0) ten--;else five-=2;if(five<=0) return false;five--;}}return true;} 
}

406. 根据身高重建队列

跳转: 406. 根据身高重建队列

学习: 代码随想录公开讲解

问题:

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

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

思路:

先排值大的,因为后插入小的对大的没有影响
值相等先排逻辑上靠前的,因为后插对前面的没有影响

复杂度:

时间复杂度: $O (n)$
空间复杂度: $O (n)$

代码:

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people,(a,b)->b[0]==a[0]?a[1]-b[1]:b[0]-a[0]);ArrayList<int[]> list = new ArrayList<>();for(int i=0;i<people.length;i++){list.add(people[i][1],people[i]);}int[][] res = new int[people.length][2];int j=0;for(int[] i:list){res[j++] = i;}return res;}
}

1399. 统计最大组的数目(每日一题)

跳转: 1399. 统计最大组的数目

问题:

给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和（每一位上的数字相加），然后把数位和相等的数字放到同一个组中。

请你统计每个组中的数字数目，并返回数字数目并列最多的组有多少个。

思路:

暴力,哈希计数再遍历哈希表去求值即可

复杂度:

时间复杂度: $O (n)$
空间复杂度: $O (1)$

代码:

class Solution {public int countLargestGroup(int n) {int[] hash = new int[37];for(int i=1;i<=n;i++){hash[bitSum(i)]++;}int ans = 0;int max = 0;for(int i:hash){if(i>max){max = i;ans = 1;}else if(i==max) ans++;}return ans;}int bitSum(int x){int ans = 0;while(x>0){ans+=x%10;x/=10;}return ans;}
}