算法训练day36 1005.134.135.

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

题目

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

题解

代码随想录 (programmercarl.com)

将数字按绝对值大小排序
优先将绝对值最大的负数取反
剩余步骤将最小非负数取反
- 注意数组大小顺序，以及处理剩余步骤的操作

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);
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] < 0 && k > 0)
            {
                nums[i] = -nums[i];
                k--;
            }
        }
        if (k % 2 == 1)
            nums[nums.size() - 1] *= -1;
        int result = 0;
        for (int a : nums)
            result += a;
        return result;
    }
};

134.加油站

题目

134. 加油站 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

对gas和cost做差可以得到每个站点净油量
从头累加净油量，如果全部累加之后为负值，则任何站点都不符合要求；如果某站点出现负值，那么从此站点之前任何站点开始都不能完成环路

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

135.分发糖果

题目

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

题解

代码随想录 (programmercarl.com)

先确定左边关系，再确定右边关系

class Solution
{
public:
    int candy(vector<int> &ratings)
    {
        vector<int> candyVec(ratings.size(), 1);
        // 从前向后
        for (int i = 1; i < ratings.size(); i++)
        {
            if (ratings[i] > ratings[i - 1])
                candyVec[i] = candyVec[i - 1] + 1;
        }
        // 从后向前
        for (int i = ratings.size() - 2; i >= 0; i--)
        {
            if (ratings[i] > ratings[i + 1])
            {
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
            }
        }

        int result = 0;
        for (int i : candyVec)
            result += i;
        return result;
    }
};