1005. K 次取反后最大化的数组和
代码链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
把负数取反，剩下的次数如果是单数最小的数字取反。
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int min = INT_MAX;
int sum =0;
for(int i=0;i<nums.size();i++)
{
if(nums[i]<0&&k>0)
{
nums[i] = -nums[i];
k--;
}
if(nums[i]<min)
min = nums[i];
sum = sum+nums[i];
}
for(int i=0;i<nums.size();i++)
cout<<nums[i]<<" ";
if(k>0&&k%2==1)
{
sum = sum-min+(-min);
}
return sum;
}
};
134. 加油站
https://leetcode.cn/problems/gas-station/
思路：求每一站剩余的油量，使用cursum进行累加从起始站到当前站的油量，小于0则重新开始。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int cur_sum =0;
int total_sum =0;
int start =0;
for(int i=0;i<gas.size();i++)
{
cur_sum += gas[i] - cost[i];
total_sum += gas[i] - cost[i];
if(cur_sum < 0)
{
start = i+1;
cur_sum = 0;
}
}
if(total_sum<0)
return -1;
if(start==gas.size())
start = 0;
return start;
}
};
135. 分发糖果
https://leetcode.cn/problems/candy/
算法思想：
从左边起遍历数组，找到一个合适的分发糖果方案，此时的方案保证了当前孩子比左孩子评分高的情况下获取到更多的糖果。
从右边起遍历数组，当前孩子比右边孩子大的情况下，获取更多的糖果，同时和上一轮的糖果数量比较，取最大值
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candy(ratings.size(), 1);
for(int i = 1; i<ratings.size();i++)
{
if(ratings[i]>ratings[i-1])
candy[i] = candy[i-1] + 1;
}
int sum = candy[ratings.size()-1];
for(int i=ratings.size()-2; i>=0; i--)
{
if(ratings[i]>ratings[i+1])
{
candy[i] = max(candy[i+1]+1, candy[i]); //在前一个数量+1和当前数量取一个最大值;
}
sum += candy[i];
}
return sum;
}
};
