代码训练营Day.34 | 1005. K次取反后最大化的数组和、134. 加油站、135. 分发糖果

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

1. LeetCode链接

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

2. 题目描述

3. 解法

整体来说，就是把负数全部取反，然后如果有剩余反转次数都给绝对值最小的数。

我的解法：先从小到大排序，这个需要分析多种情况。略。

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int i = 0;
        int sum = 0;
        for (; i < nums.size() && k > 0; i++) {
            if (nums[i] >= 0) break;
            nums[i] = 0 - nums[i];
            sum += nums[i];
            k--;
        }
        if (i != nums.size() && k != 0) {
            if (i > 0 && nums[i] > nums[i - 1]) {
                i--;
                sum -= nums[i];
            }
            if (k % 2 == 1) nums[i] = 0 - nums[i]; 
        } else if (i == nums.size() && k != 0) {
            if (k % 2 == 1) sum -= 2 *nums[nums.size() - 1];
        }
        for (; i < nums.size(); i++) {
            sum += nums[i];
        }
        return sum;
        // k <= nums中的非正数个数
        // k > nums中的非正数个数 && 有0
        // k > nums中的非正数个数 && no 0
        // nums中全是非正数
    }
};

简洁方法，直接按照绝对值大小排序。

class Solution {
static bool cmp(int a, int b) {
    return abs(a) > abs(b);
}
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), cmp);
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            if(nums[i] < 0 && k > 0) {
                nums[i] *= -1;
                k--;
            }
            sum += nums[i];
        }
        if (k % 2 == 1) sum -= 2 * nums[nums.size() - 1];
        return sum;
    }
};

134. 加油站

1. LeetCode链接

134. 加油站 - 力扣（LeetCode）

2. 题目描述

3. 解法

整体来说，如果gas的总量 < cost的总量，汽车无论如何都不可能循环一周。否则，必可以循环一周。

我的解法：

1. 判断两个数组总量是否合理。求得存储两数组对应元素差值的数组left（表示，空油箱从i节点出发，到i + 1节点还能剩多少油）。

2. 如果left总和 < 0，直接return -1.

3. 如果left综合 > =0。在left数组上执行类似于LeetCode题目53.最大子序和的操作。首先，记录最大子序的长度len，直到长度与原数组长度相等，return 当前下标；count持续记录连续序列和，如果<0，则刷新len和count。

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

还有更简单的是，记录累加和初始坐标start，这样可以在一遍遍历后得到答案，而且只需一次遍历。

因为如果在计算局部累加和时，count < 0，则说明其对应累加初始坐标一定不是循环起始点，累加和之间的坐标，也不是！这时，初始化count并记录start。

最后，因为是一次从前到后的完整遍历。判断记录后的累加差值是负数，则return -1。否则，return start。

start之后的是否可能也存在循环起点？因为start到末尾的累加和中，从来没有小于过0，所以，start一定是第一个。

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

135. 分发糖果

1. LeetCode链接

135. 分发糖果 - 力扣（LeetCode）

2. 题目描述

3. 解法

我的解法：

整体来说，就是每个孩子尽可能拿最少的糖果数量。

一般我们自己解这种题，都是先找极小值；然后，将极小值点设为1（颗糖果），从极小值开始，向左爬升到极大值点，糖果数量依次+1，向右爬升到极大值点，糖果数量一次+1。

编程时，需要先计算完所有极小值点向一侧爬升后，再考虑一起从另一侧爬升。这是因为一个极大值点，两侧各有一个极小值点；左侧极小值点向右爬升得到的糖果数量 和 右侧极小值点向左爬升得到的糖果数量，当前极大值点要取最大值。如果按极小值点先后顺序同时考虑两侧爬升，并不能考虑到这一点。

class Solution {
public:
    int candy(vector<int>& ratings) {
        int pre = ratings[0];
        int cur;
        int post = 0;
        vector<int> index;
        vector<int> candies(ratings.size(), 0);    // 记录每个孩子能分发到的最终糖果数量
        for (int i = 0; i < ratings.size(); i++) {    // 找极小值点，其中判断时，仅考虑非严格递增/递减
            if (i == ratings.size() - 1) post = ratings[i];
            else post = ratings[i + 1];
            cur = ratings[i];
            if (pre >= cur && cur <= post) index.push_back(i);
            pre = cur;
        }
        for (int i = 0; i < index.size(); i++) {   // 从所有极小值点出发，向左爬升
            candies[index[i]] = 1;
            int c = 2;
            for (int j = index[i] - 1; j >=0; j--) {
                if (ratings[j] <= ratings[j + 1]) break;
                candies[j] = c;
                c++;
            }
        }
        for (int i = 0; i < index.size(); i++) {   // 从所有极小值点出发，向右爬升
            int c = 2;
            for (int j = index[i] + 1; j < ratings.size(); j++) {
                if (ratings[j] <= ratings[j - 1]) break;
                if (candies[j] > c) break;
                candies[j] = c;
                c++;
            }
        }
        int sum = 0;
        for (int i : candies) sum += i;     // 求和
        return sum;
    }
};

巧妙解法：

局部最优：所有孩子的相邻右孩子如果评分比他高的话+1糖果；所有孩子的相邻左孩子如果评分比他高的话+1糖果。

全局最优：相邻两个孩子评分更高的孩子会获得更多的糖果。

1. 先设置数组记录每个孩子分到的糖果数，设置基数都为1，即每个孩子都分到一个。

2. 从左向右遍历，如果当前孩子评分比前一个高，前一个糖果数+1。

3. 从右向左遍历，如果当前孩子评分比后一个高，取他原本的数/后一个糖果数+1中最大的。

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candies(ratings.size(), 1);
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = max(candies[i], candies[i + 1] + 1);
            }
        }
        int sum = 0;
        for (int i : candies) sum += i;
        return sum;
    }
};