我在代码随想录|写代码Day28 | 贪心算法 | 1005.K次取反后最大化的数组和,134. 加油站,135. 分发糖果

博客介���`： 27dCnc

系列专栏： > >

当前专栏:

专题 : 数据结构帮助小白快速入门算法

☆*: .｡. o(≧▽≦)o .｡.:*☆

❤️感谢大家点赞收藏⭐评论✍️

学习目标： 贪心算法

今日学习打卡

• 代码随想录-贪心算法

  ---

  学习时间：

  • 周一至周五晚上 7 点—晚上9点
  • 周六上午 9 点-上午 11 点
  • 周日下午 3 点-下午 6 点

    ---

    学习内容：

    1. K次取反后最大化的数组和
    2. 加油站
    3. 分发糖果

    ---

    内容详细：

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

    考点: 贪心

    思路极其简单: 将每次循环排序下,然后将最小的数反转符号即可

    代码

    class Solution {public:    int largestSumAfterKNegations(vector& nums, int k) {        int cnt = 0;        for(int i = 0;i  
    其他版本
     
    class Solution {static bool cmp(int a, int b) {    return abs(a) > abs(b);}public:    int largestSumAfterKNegations(vector& A, int K) {        sort(A.begin(), A.end(), cmp);       // 第一步        for (int i = 0; i  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. 加油站
     
    题目考点: 贪心
     
    解题思路
     
    暴力方法
    暴力的方法很明显就是O(n^2)的，遍历每一个加油站为起点的情况，模拟一圈。
    如果跑了一圈，中途没有断油，而且最后油量大于等于0，说明这个起点是ok的。
    暴力的方法思路比较简单，但代码写起来也不是很容易，关键是要模拟跑一圈的过程。
    for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while！
     
    代码
     
    class Solution {public:    int canCompleteCircuit(vector& gas, vector& cost) {        for (int i = 0; i  0 && index != i) { // 模拟以i为起点行驶一圈（如果有rest==0，那么答案就不唯一了）                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节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点。

      代码

      class Solution {public:    int canCompleteCircuit(vector& gas, vector& cost) {        int Min = INT_MAX;        int spare = 0;         int len = gas.size(); //数组长度        int index = 0; //起始位置下标        for (int i = 0; i = 0) return 0;        return (index + 1);     }};

      135. 分发糖果

      题目考点: 贪心 区间变化比较

      这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。

      先确定右边评分大于左边的情况（也就是从前向后遍历）

      此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果

      局部最优可以推出全局最优。

      如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个，所以贪心：candyVec[i] = candyVec[i - 1] + 1

      代码如下：

      // 从前向后for (int i = 1; i  ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;}

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

      遍历顺序这里有同学可能会有疑问，为什么不能从前向后遍历呢？

      因为 rating[5]与rating[4]的比较 要利用上 rating[5]与rating[6]的比较结果，所以 要从后向前遍历。

      如果从前向后遍历，rating[5]与rating[4]的比较 就不能用上 rating[5]与rating[6]的比较结果了 。如图：

      所以确定左孩子大于右孩子的情况一定要从后向前遍历！

      如果 ratings[i] > ratings[i + 1]，此时candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。

      那么又要贪心了，局部最优：取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);    }}

      最终代码

      class Solution {public:    int candy(vector& ratings) {        vectorcandy(ratings.size(),1);        for(int i = 1; i = 0; i--) {            if (ratings[i] > ratings[i + 1]) { //然后从右往左进行比较,比较元素下标要反            //要在candy[i] 和 candy[i+1] + 1 间取最大值才符合题意                candy[i] = max(candy[i+1] + 1,candy[i]);             }        }        int cnt = 0;        for (auto& i : candy) {            cnt += i;        }        return cnt;    }};

      ---

      学习产出：

      • 技术笔记 2 遍
      • CSDN 技术博客 3 篇
      • 习的 vlog 视频 1 个

        重磅消息:

        GTP - 4 最新版接入服务他来了 点击链接即可查看详细

        GTP - 4 搭建教程

        如果此文对你有帮助的话，欢迎关注、点赞、⭐收藏、✍️评论，支持一下博主~