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

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

代码随想录链接

题目

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

给定一个整数数组和一个数字K, 要求选取K次, 每次都将该数置为其负数, 返回K次选择后的最大值.

自己的想法

将所有值按照绝对值的大小从大到小进行排列, 从左至右遍历, 先将绝对值大的负数置为正数, 多余的选择次数全部用在最后一个数(即绝对值最小的数)上.

题解

class Solution {
static bool absCmp(int a, int b) {  // 自定义sort的排序
    return abs(a) > abs(b);
}
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), absCmp); // 将所有数字按照绝对值的大小从大到小进行排序
        for (int i = 0; i < nums.size(); i++) { // 遍历并将负值置为正数
            if (nums[i] < 0 && k > 0) {
                nums[i] *= -1;
                k--;
            }
        }
        while (k--) nums[nums.size() - 1] *= -1; // 将多余的次数用在绝对值最小的数上
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];   // 求和
        return sum;
    }
};

134.加油站

代码随想录链接

题目

LeetCode-134.加油站

给定一个gas和cost数组, 分别表示加油站的油量和开往下一个加油站所需要的油量, 所有加油站可以看成一个回路, 求从何处出发可以绕环路一周, 若不能绕行一周, 则返回-1.

自己的想法

如果gas数组之和小于cost数组之和, 则无论如何也无法行驶一周.

如果gas数组之和大于等于cost数组之和, 则可以找到一个起始位置完成一周的行驶. 在这种情况下, 可以假设从0位置出发, 求rest[i] = gas[i] - cost[i]之和, 如果在一个位置上, 该和小于0, 则证明从0处出发无法到达此位置, 需要将起始位置置为下一个加油站, 并重新计算rest[i]之和. 遍历完成后即能得到可行的起始位置.

题解

解法一:(就是上面描述的方法)

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int total = 0;
        int pos = 0;
        for (int i = 0; i < gas.size(); i++) {
            int rest = gas[i] - cost[i];
            curSum += rest; // 计算从上一个设想位置出发的rest之和, 判断该位置出发是否可行
            total += rest;  // 计算全路程的油量, 判断是否有可能完成一周绕行
            if (curSum < 0) {   // 如果上个出发位置不可行, 就更换为下一个出发位置
                pos = i + 1;
                curSum = 0;
                /**
                 * 为什么不将当前位置设为下一个出发位置呢?
                 * 在进行当前位置的计算时, curSum是大于等于0的, 计算完当前位置之后, curSum小于0, 证明当前位置一定有rest[i] < 0, 一定不适合出发, 所以需要置到下一个位置为起始位置.
                 */

            }
        }
        if (total < 0) return -1;   // 环路剩余油量不满足环路消耗量, 无法绕行
        return pos;
    }
};

解法二:

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int minSum = INT_MAX;
        for (int i = 0; i < gas.size(); i++) {  // 计算环路油量剩余是否大于0, 以及找到从0出发时最小剩余油量
            int rest = gas[i] - cost[i];
            curSum += rest;
            minSum = min(curSum, minSum); 
        }
        if (curSum < 0) return -1;  // 环路油量不足, 无法绕行
        if (minSum >= 0) return 0;  // 从0处出发没有遇到油不足的情况, 可行
        for (int i = gas.size() - 1; i >= 0; i--) { // 从后往前计算剩余油量之和, 找出第一个之和能将minSum置为非负数的位置, 从该位置出发可行
            int rest = gas[i] - cost[i];
            minSum += rest;
            if (minSum >= 0) {
                return i;
            }
        }
        return -1;
    }
};

135.分发糖果

代码随想录链接

题目

LeetCode-135.分发糖果

给N个孩子分糖果, 给定N个孩子的评分, 相邻两个孩子中分数较高的孩子需要获得更多的糖果, 每个孩子都需要获得至少一个糖果, 求所需的最少糖果.

自己的想法

评分较高需要从左右两侧来看, 两边一起考虑一定会有些问题. 可以先从前往后考虑每个孩子与左侧对比, 再从后往前, 将每个孩子的平分与右侧孩子对比.

题解

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyNum(ratings.size(), 1);    // 每个孩子至少一个糖果
        for (int i = 1; i < candyNum.size(); i++) // 每个孩子与左侧孩子对比
            if (ratings[i] > ratings[i - 1])
                candyNum[i] = candyNum[i - 1] + 1;

        for (int i = candyNum.size() - 2; i >= 0; i--) // 每个孩子与右侧孩子对比
            if (ratings[i] > ratings[i + 1])
                candyNum[i] = max(candyNum[i], candyNum[i + 1] + 1);

        int sum = 0;
        for (int i = 0; i < candyNum.size(); i++) // 求和
            sum += candyNum[i];

        return sum;
    }
};