代码随想录算法训练营第三十三天| ● 1005.K次取反后最大化的数组和 ● 134. 加油站 ● 135. 分发糖果

K次取反后最大化的数组和 

题目链接：1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

思路：首先增序排序，然后依次将负值取反，如果负数先用完，则再排序一次，将最小的正数取反之后求和；如果k先用完，直接求和。

注意sort默认是增序排序，若想要要降序，则不能使用sort(nums.end(),nums.begin()),而是sort(nums.begin(),nums.end(),greater<int>())。

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        int count=0;
        int i=0;
        for(;i<nums.size();i++){
            if(k){
                if(nums[i]<0){nums[i]=-nums[i];--k;}
                else break;
            }
        }
        if(k%2){
            sort(nums.begin(),nums.end());
            nums[0]=-nums[0];
        }
        for(auto i:nums)count+=i;
        return count;
    }
};

我的方法用自定义的绝对值排序会更简单，少一次排序

class Solution {
static bool cmp(int a, int b) {
    return abs(a) > abs(b);
}
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(), A.end(), cmp);       // 第一步
        for (int i = 0; i < A.size(); i++) { // 第二步
            if (A[i] < 0 && K > 0) {
                A[i] *= -1;
                K--;
            }
        }
        if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步
        int result = 0;
        for (int a : A) result += a;        // 第四步
        return result;
    }
};

这里再放一种写法仅供参考。

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int abs_min = 100, sum = 0; 
        for (int i = 0; i < nums.size(); i++) {
          	// 计算绝对值最小的值
            abs_min = min(abs(nums[i]), abs_min);
            // 所有数字的和
            sum += nums[i]; 
        }
        
        sort(nums.begin(), nums.end());
        // 根据k，翻转nums[i]，并更新sum
        for (int i = 0; i < nums.size() && k; i++, k--) {
            if (nums[i] >= 0)
                break;
            sum += 2 * abs(nums[i]);
        }
        // 若k有剩余，且为奇数，减去其在sum中的值
        if (k > 0 && (k & 1))
            sum -= 2 * abs_min;
        return sum;
    }
};

作者：编程熊
链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/solutions/1135672/acmjin-pai-ti-jie-tan-xin-bian-cheng-xio-6gah/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

加油站

题目链接：

思路：首先将gas数组与cost对应项相减，从而得到每一站的油余额。再从第一个正余额的加油站出发，当再次遍历到这个加油站时，证明无解。每次遍历从某个正余额加油站开始，当这一趟的油余额为负时，证明从该加油站出发不可行，只能从下一个正余额的加油站出发，如果能走完一圈，返回start。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        for(int i=0;i<gas.size();i++){
            gas[i]-=cost[i];
        }
        for(int start=0;start<gas.size();start++){
        while(gas[start++]<=0&&start<gas.size());
        --start;
        int g=gas[start];
        for(int i=(start+1)%gas.size();i!=start;i=(i+1)%gas.size()){
            g+=gas[i];
            if(g<0)break;
        }
        if(g>=0)
        return start;
        }
        return -1;
    }
};

最绷不住的一集-_-||

明明思路差不多，但是下面这个写法却比我的方法快十几倍。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1;
            }
        }
        return -1;
    }
};

分发糖果  

题目链接：

思路：只要能获得数组的单调区间长度，就能轻松解决糖果数。因此最初的思路是，先从左到右遍历数组，如果出现单调区间，则将区间内所有项加1，再从右到左遍历数组，如果出现单调区间，将区间内所有项加1。这个思路近乎正确了，但是如果一个元素处于单挑增区间和单调减区间的交界处，则会导致他的糖果数被重复计算，因为他的真实结果应该是左右区间长度的较大者。所以这里必须定义两个记录数组。

同时要注意vector的初始化里第一个是大小，第二个才是初值。

class Solution {
public:
    void sum(vector<int>& can,int start,int end){
        for(int i=start;i<=end;i++){
            can[i]+=1;
        }
    }
    int candy(vector<int>& ratings) {
        if(ratings.size()==1)return 1;
        vector<int>can1(ratings.size(),1);
        vector<int>can2(ratings.size(),1);
        int start=0;
        for(int i=0;i<=ratings.size()-2;i++){
            if(ratings[i]>ratings[i+1]){
                sum(can1,start,i);
            }
            else
                start=i+1;
        }
        start=ratings.size()-1;
        for(int j=ratings.size()-1;j>=1;j--){
            if(ratings[j]>ratings[j-1]){
                sum(can2,j,start);
            }
            else
                start=j-1;
        }
        int count=0;
        for(int i=0;i<ratings.size();i++){
            if(can1[i]>can2[i])count+=can1[i];
            else count+=can2[i];
        }
        return count;
    }
};

我们是垃圾！！

建议好好学学官网解法

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> left(n);
        for (int i = 0; i < n; i++) {
            if (i > 0 && ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }
        int right = 0, ret = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1 && ratings[i] > ratings[i + 1]) {
                right++;
            } else {
                right = 1;
            }
            ret += max(left[i], right);
        }
        return ret;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/candy/solutions/533150/fen-fa-tang-guo-by-leetcode-solution-f01p/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。