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

发布于 2022-12-19  496 次阅读


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

思路:

  • 将数组按绝对值从大到小排序,遍历数组,如果遇到小于0的数且此时k > 0,那么将该值符号反转,如果遍历完一次仍满足k > 0,那么将最小的数翻转k次(此处做取余数处理更快),最后将处理完成的数组元素相加即可

我的AC代码

//时间复杂度O(nlogn),空间复杂度O(1)
class Solution {
public:
    static bool cmp(int& a, int& b) {
        return abs(a) > abs(b);
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int ans = 0;
        sort(nums.begin(), nums.end(), cmp);
        for(int i = 0; i < nums.size(); ++i) {
            if(k > 0 && nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        k = k % 2;
        while(k--) {
            nums[nums.size() - 1] = -nums[nums.size() - 1];
        }
        for(int i = 0; i < nums.size(); ++i) {
            ans += nums[i];
        }
        return ans;
    }
};

标准答案

//时间复杂度O(nlogn),空间复杂度O(1)
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;
    }
};

134. 加油站 - 力扣(LeetCode)

思路:

  • 遍历所有加油站,计算每个加油站gascost的差值,若总差值小于0则返回-1,在遍历过程中如果当前差值和小于0则将当前差值和重置为0,并将起始点置为i + 1,因为如果[l, r]区间内的差值和小于0,则可以断定起点不在该范围内

我的AC代码

//时间复杂度O(n),空间复杂度O(1)
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) {
            totalsum += gas[i] - cost[i];
            cursum += gas[i] - cost[i];
            if(cursum < 0) {
                cursum = 0;
                start = i + 1;
            }
        }
        if(totalsum < 0) {
            return -1;
        }
        return start;
    }
};

标准答案

暴力法

//时间复杂度O(n^2),空间复杂度O(1)
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        for (int i = 0; i < cost.size(); i++) {
            int rest = gas[i] - cost[i]; // 记录剩余油量
            int index = (i + 1) % cost.size();
            while (rest > 0 && index != i) { // 模拟以i为起点行驶一圈
                rest += gas[index] - cost[index];
                index = (index + 1) % cost.size();
            }
            // 如果以i为起点跑一圈,剩余油量>=0,返回该起始位置
            if (rest >= 0 && index == i) return i;
        }
        return -1;
    }
};

巧妙的解法(从全局出发)

直接从全局进行贪心选择,情况如下:

  • 情况一:如果gas的总和小于cost总和,那么无论从哪里出发,一定是跑不了一圈的
  • 情况二:rest[i] = gas[i]-cost[i]为一天剩下的油,i从0开始计算累加到最后一站,如果累加没有出现负数,说明从0出发,油就没有断过,那么0就是起点
  • 情况三:如果累加的最小值是负数,汽车就要从非0节点出发,从后向前,看哪个节点能这个负数填平,能把这个负数填平的节点就是出发节点
//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int min = INT_MAX; // 从起点出发,油箱里的油量最小值
        for (int i = 0; i < gas.size(); i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            if (curSum < min) {
                min = curSum;
            }
        }
        if (curSum < 0) return -1;  // 情况1
        if (min >= 0) return 0;     // 情况2
                                    // 情况3
        for (int i = gas.size() - 1; i >= 0; i--) {
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) {
                return i;
            }
        }
        return -1;
    }
};

贪心

可以换一个思路,首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈,说明各个站点的加油站 剩油量rest[i]相加一定是大于等于零的

每个加油站的剩余量rest[i]为gas[i] - cost[i]

i从0开始累加rest[i],和记为curSum,一旦curSum小于零,说明[0, i]区间都不能作为起始位置,起始位置从i+1算起,再从0计算curSum

//时间复杂度O(n),空间复杂度O(1)
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) {   // 当前累加rest[i]和 curSum一旦小于0
                start = i + 1;  // 起始位置更新为i+1
                curSum = 0;     // curSum从0开始
            }
        }
        if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
        return start;
    }
};

135. 分发糖果 - 力扣(LeetCode)

思路:

  • 轮流判断右边评分大于左边的情况和左边评分大于右边的情况,不要顾此失彼

  • 先从前向后遍历数组,确定右边评分大于左边的情况

  • 然后从后往前遍历数组,确定左边评分大于右边的情况

细节:

  • 确定右边评分大于左边一定要从前往后遍历,而确定左边评分大于右边一定要从后往前遍历,因为要利用上一次的结果。比如确定左边评分大于右边的情况,若从前往后遍历,那么每次被改变的那个值在下一轮比较中都没有参与进来,会得出不准确的值,而如果从后往前遍历则每次上一次处理的值都会参与判断
  • 从前往后遍历的时候要从1开始,而从后往前遍历的时候要从ratings.size() - 2开始,因为要确保最后一个元素也参与了判断

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int candy(vector<int>& ratings) {
        int ans = 0;
        vector<int> candy(ratings.size(), 1);
        for(int i = 1; i < ratings.size(); ++i) {
            if(ratings[i] > ratings[i - 1]) {
                candy[i] = candy[i - 1] + 1;
            }
        }
        for(int i = ratings.size() - 2; i >= 0; --i) {
            if(ratings[i] > ratings[i + 1]) {
                candy[i] = max(candy[i], candy[i + 1] + 1);
            }
        }
        for(int i = 0; i < ratings.size(); ++i) {
            ans += candy[i];
        }
        return ans;
    }
};

标准答案

//时间复杂度O(n),空间复杂度O(n)
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 = 0; i < candyVec.size(); i++) result += candyVec[i];
        return result;
    }
};