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

代码随想录算法训练营第三十四 |● 1005.K次取反后最大化的数组和 ● 134. 加油站 ● 135. 分发糖果

news 来源：原创 2024/9/28 14:23:24

今天的解析写在了代码注释中

1005.K次取反后最大化的数组和

讲解链接：https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html

class Solution {
public:static bool cmp(int a,int b) {return abs(a)>abs(b);}int largestSumAfterKNegations(vector<int>& nums, int K) {//所有值按绝对值大小排序sort(nums.begin(),nums.end(),cmp);for(int i=0;i<nums.size();i++) {//先把负值变为正值if(nums[i]<0 && K>0) {nums[i] *= -1;K--;}}//如果K还没用完，就把最小的值拿出来取负if(K%2 == 1) nums[nums.size()-1] *= -1;int result = 0;for(int a : nums) result +=a;return result;}
};

134. 加油站

讲解链接：https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {//逐个元素作为起点进行判断for(int i=0;i<cost.size();i++) {//出发往下一个加油站的剩余油量int shengyu = gas[i]-cost[i];//定义index用来循环下标，防止越界int index = (i+1)%cost.size();//保证油量可以走到下一个点模拟以i为起点行驶一圈while(shengyu > 0 && index!=i) {//累加剩余油量shengyu += gas[index] - cost[index];//末尾的下一个点指向数组头index = (index+1) % cost.size();}if(shengyu >=0 && index==i)return i;}return -1;}
};

135. 分发糖果

讲解链接：https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html

有两个过程，前向判断（i与i-1两两比较)，大的一项直接+1
后向过程(i与i+1两两比较)，这里为了避免重复（1，2，1）这种情况，需要 max( t[i] , t[i+1]+1)

class Solution {
public:int candy(vector<int>& ratings) {vector<int> t(ratings.size(),1);//从前往后,i与i-1进行比较//从第二个数开始，这里是 i 与 i-1 作比较for(int i=1; i<ratings.size();i++) {if(ratings[i] > ratings[i-1])t[i]=t[i-1]+1;//比他左边大一个，这里直接改}//从后往前//从倒数第二个数开始，比较 i 与 i+1//max( t[i] , t[i+1]+1)for(int i = ratings.size()-2; i>=0;i--) {if(ratings[i]>ratings[i+1]) t[i] = max(t[i],t[i+1]+1);}int result = 0;for(int i=0;i<t.size();i++)result+=t[i];return result;}
};