贪心算法 part03 1005. K 次取反后最大化的数组和 134. 加油站 135. 分发糖果
1005. K 次取反后最大化的数组和
思路
- 第一步，从前向后遍历，遇到负数将其变为正数，同时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）
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;
}
};
