1005.K次取反后最大化的数组和
这道题自己试了好几个方法，发现都有漏洞。最后瞟了一眼回答，才想明白原来一直更新最小的数就可以了。不用写各种条件来去反转数。
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
int result;
for(int i=0; i<k; i++){
sort(nums.begin(),nums.end());
nums[0] = nums[0] * -1;
}
for(int i=0; i<nums.size(); i++){
result = result + nums[i];
}
return result;
}
};
Carl的答案是先按照所有数的绝对值从大到小排列，如果遇到负数且k大于0，那就反转这个负数为正数。把这一步做完之后，如果目前k值还大于0，那当前的所有负值都已转化为正值了，那就让k%2，如果得的是1，说明要进行奇数次的反转，那我们反转应该反转最小的数，也就是位于nums.size()-1的数。如果k%2得0，说明我们没必要再反转，毕竟反多少次，最后都要反回到正数。最后再把数值都相加。
我又自己写了一遍，写的时候开始没有给result赋值，所以出来的数不对。后来检查出来了。
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);
int nums_size = nums.size();
for(int i=0; i<nums.size() && k>0; i++){
if(nums[i]<0 && k>0){
nums[i] = nums[i] * -1;
k--;
}
}
if(k%2 == 1){
nums[nums_size-1] = nums[nums_size-1] * -1;
}
int result = 0;
for(int i=0; i<nums_size; i++){
result = result + nums[i];
}
return result;
}
};
134. 加油站
之前做过一遍了，但是逻辑还是捋的不清楚。
这道题就是在找最后一个非负数的(gas-cost)的下一个值。当目前的值是负数，说明下一个有可能是。然后遍历整个数组来找。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int cur_gas = 0;
int total_gas = 0;
int result = 0;
for(int i=0; i<gas.size(); i++){
cur_gas = cur_gas + gas[i] - cost[i];
total_gas = total_gas + gas[i] - cost[i];
if(cur_gas<0){
result = i+1;
cur_gas = 0;
}
}
if(total_gas<0){
return -1;
}
return result;
}
};
135. 分发糖果
困难题直接跳过。
