侧边栏壁纸
博主头像
thinkTV博主等级

喜爱动漫的二刺螈一枚,摩托车云爱好者(快要有车了)。 懂一点技术的在读生物医学工程研究生( •̀ ω •́ )✧,多多指教。

  • 累计撰写 136 篇文章
  • 累计创建 17 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

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

thinkTV
2023-05-23 / 0 评论 / 0 点赞 / 38 阅读 / 1,107 字 / 正在检测是否收录...

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

代码随想录:原文

力扣题目:1005.K次取反后最大化的数组和

1.1 思路

两步贪心:

  • 局部最优:让绝对值大的负数变为正数,当前数值达到最大
  • 整体最优:整个数组和达到最大
  • 局部最优:只找数值最小的正整数进行反转,当前数值和可以达到最大
  • 全局最优:整个 数组和 达到最大。

1.2 代码实现

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;
    }
};

  • 时间复杂度: O(nlogn)O(nlogn)
  • 空间复杂度: O(1)O(1)

2. 加油站

代码随想录:原文

力扣题目:1005.K次取反后最大化的数组和

2.1 思路

暴力方法

  • 遍历每一个加油站为起点的情况,模拟一圈
  • for循环适合模拟从头到尾的遍历,而while循环适合模拟环形遍历,要善于使用while
  • 时间复杂度:O(n2)O(n^2)

贪心算法

  • 情况一:如果gas的总和小于cost总和,那么无论从哪里出发,一定是跑不了一圈的
  • 情况二:rest[i] = gas[i]-cost[i]为一天剩下的油,i从0开始计算累加到最后一站,如果累加没有出现负数,说明从0出发,油就没有断过,那么0就是起点。
  • 情况三:如果累加的最小值是负数,汽车就要从非0节点出发,从后向前,看哪个节点能把这个负数填平,能把这个负数填平的节点就是出发节点。

2.2 代码实现

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;
    }
};

3. 分发糖果

代码随想录:原文

力扣题目:135. 分发糖果

3.1 思路

  • 两边一起考虑一定会顾此失彼
    先确定右边评分大于左边的情况(也就是从前向后遍历)
  • 局部最优:只要右边评分比左边大,右边的孩子就多一个糖果
  • 全局最优:相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果
// 从前向后
for (int i = 1; i < ratings.size(); i++) {
    if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
}

再确定左孩子大于右孩子的情况(从后向前遍历)

  • 局部最优:取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,保证第i个小孩的糖果数量既大于左边的也大于右边的
  • 全局最优:相邻的孩子中,评分高的孩子获得更多的糖果
  • candyVec[i + 1] + 1 candyVec[i] 最大的糖果数量,candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多,也比右边candyVec[i + 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);
    }
}

3.2 代码实现

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;
    }
};

4. 总结

  • 坚持用贪心的思考方式(局部最优,全局最优)
  • 不好两头兼顾的题目,处理好一边再处理另一边
0

评论区