1005.?K 次取反后最大化的數(shù)組和
思路：
要實現(xiàn)最大值冰抢，首先是將數(shù)組中的負(fù)數(shù)取反轉(zhuǎn)換為正數(shù)，絕對值大的負(fù)數(shù)優(yōu)先艘狭。如果所有的負(fù)數(shù)都已經(jīng)轉(zhuǎn)為正數(shù)挎扰，但是k不為0河质，則將最小的正數(shù)進(jìn)行取反辕坝，直到k為0百揭。
代碼：
class Solution {
public:
static bool cmp(int a, int b) {
? ? return abs(a) > abs(b);
}
? ? int largestSumAfterKNegations(vector<int>& nums, int k) {
? ? ? ? sort(nums.begin(),nums.end(),cmp);
? ? ? ? for(int i=0;i<nums.size();i++)
? ? ? ? {
? ? ? ? ? ? if(k>0 && nums[i]<0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? nums[i]=-nums[i];
? ? ? ? ? ? ? ? k--;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(k%2==1)nums[nums.size()-1]*=-1;
? ? ? ? int res=0;
? ? ? ? for(int i=0;i<nums.size();i++)
? ? ? ? {
? ? ? ? ? ? res+=nums[i];
? ? ? ? }
? ? ? ? return res;
? ? }
};
134.?加油站
思路：
這道題與第122題有相似之處恼五，如果在第i處的凈值小于0限府，則表示i之前的站點出發(fā)都不行策彤，應(yīng)該從i+1處重新計算奥吩。
代碼：
class Solution {
public:
? ? int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
? ? ? ? int cursum=0;
? ? ? ? int totalsum=0;
? ? ? ? int index=0;
? ? ? ? for(int i=0;i<gas.size();i++)
? ? ? ? {
? ? ? ? ? ? cursum+=gas[i]-cost[i];
? ? ? ? ? ? totalsum+=gas[i]-cost[i];
? ? ? ? ? ? if(cursum<0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? index=i+1;
? ? ? ? ? ? ? ? cursum=0;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(totalsum<0) return -1;
? ? ? ? return index;
? ? }
};
135.?分發(fā)糖果
思路：
這道題的難點在于對于數(shù)組中間的數(shù)字册养，既要跟左邊比較又要跟右邊比較傲绣，此類問題可以分兩部求解掠哥，先從頭遍歷，比較左邊的情況斜筐，再從尾部倒序遍歷龙致，比較右邊，最后求兩者的交集（最大值）顷链。
代碼：
class Solution {
public:
? ? int candy(vector<int>& ratings) {
? ? ? ? vector<int> res(ratings.size(),1);
? ? ? ? for(int i=1;i<ratings.size();i++)
? ? ? ? {
? ? ? ? ? ? if(ratings[i]>ratings[i-1])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? res[i]=res[i-1]+1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? for(int i=ratings.size()-2;i>=0;i--)
? ? ? ? {
? ? ? ? ? ? if(ratings[i]>ratings[i+1])
? ? ? ? ? ? res[i]=max(res[i],res[i+1]+1);
? ? ? ? }
? ? ? ? int sum=0;
? ? ? ? for(int i=0;i<res.size();i++)
? ? ? ? {
? ? ? ? ? ? sum+=res[i];
? ? ? ? }
? ? ? ? return sum;
? ? }
};
