兰溪网站建设iis 建设网站
贪心算法 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一旦小于0start = i + 1; // 起始位置更新为i+1curSum = 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;}
};