1005. K 次取反后最大化的數(shù)組和
代碼鏈接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
把負(fù)數(shù)取反，剩下的次數(shù)如果是單數(shù)最小的數(shù)字取反蛾坯。
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進(jìn)行累加從起始站到當(dāng)前站的油量吁津，小于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. 分發(fā)糖果
https://leetcode.cn/problems/candy/
算法思想：
從左邊起遍歷數(shù)組，找到一個(gè)合適的分發(fā)糖果方案开睡，此時(shí)的方案保證了當(dāng)前孩子比左孩子評(píng)分高的情況下獲取到更多的糖果莹菱。
從右邊起遍歷數(shù)組，當(dāng)前孩子比右邊孩子大的情況下文捶，獲取更多的糖果荷逞，同時(shí)和上一輪的糖果數(shù)量比較，取最大值
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]); //在前一個(gè)數(shù)量+1和當(dāng)前數(shù)量取一個(gè)最大值;
? ? ? ? ? ? }
? ? ? ? ? ? sum += candy[i];
? ? ? ? }
? ? ? ? return sum;
? ? }
};
