贪心算法 part03 1005. K 次取反后最大化的数组和 134. 加油站 135. 分发糖果
1005. K 次取反后最大化的数组和
思路文章来源:https://www.toymoban.com/news/detail-803598.html
- 第一步,从前向后遍历,遇到负数将其变为正数,同时K–
- 第二步:如果K还大于0,那么反复转变数值最小的元素,将K用完
- 第三步:求和
class Solution {
public:
static bool Compare(int& a, int& b){
return abs(a) > abs(b);
}
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(),nums.end(),Compare); //绝对值排序
for(int i = 0; i<nums.size();i++){
if(nums[i]<0 && k>0){ //第一步贪心,取绝对值最大的数确保为正数
nums[i] = -nums[i];
k--;
}
}
if(k%2==1) nums[nums.size()-1] *= -1; //第二步贪心,如果k还有剩余,进行绝对值最小数的操作
int result = 0; //第三步,取结果
for (int a : nums) result += a;
return result;
}
};
134. 加油站
方法一(暴力)
leetcode超时(35/40)文章来源地址https://www.toymoban.com/news/detail-803598.html
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
for(int i = 0; i<gas.size(); i++){
int rest = gas[i]-cost[i]; //记录当天用油差值
int Index = (i+1)%gas.size(); //方便下面的while进行判断
while(rest>0 && Index!=i){
rest+=gas[Index] - cost[Index];
Index = (Index + 1) % cost.size();
}
if(Index ==i && rest >=0) return i; //返回当前i
}
return -1;
}
};
方法二(贪心)
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum = 0;
int totalSum = 0;
int start = 0;
for (int i = 0; i < gas.size(); i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) { // 当前累加rest[i]和 curSum一旦小于0
start = i + 1; // 起始位置更新为i+1
curSum = 0; // curSum从0开始
}
}
if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
return start;
}
};
135. 分发糖果
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candyVec(ratings.size(), 1);
for(int i = 1; i<ratings.size();i++){ //从前往后
if(ratings[i-1]<ratings[i]) candyVec[i] = candyVec[i-1] +1;
}
for(int i = ratings.size()-1; i>=1; i--){ //从后往前
if(ratings[i] <ratings[i-1]) candyVec[i-1] =max(candyVec[i-1],candyVec[i]+1);
}
int result = 0;
for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];
return result;
}
};
到了这里,关于Day34 贪心算法 part03 1005. K 次取反后最大化的数组和 134. 加油站 135. 分发糖果的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!