【贪心算法篇】：“贪心”之旅--算法练习题中的智慧与策略（一）

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：贪心算法篇–CSDN博客

在这里插入图片描述

文章目录

一.贪心算法
- 1.什么是贪心算法
- 2.贪心算法的特点
二.例题
- 1.柠檬水找零
- 2.将数组和减半的最小操作次数
- 3.最大数
- 4.摆动序列

一.贪心算法

1.什么是贪心算法

贪心算法（Greedy Algorithm)是一种在每一步选择中都采取在当前状态下的最优决策的算法策略。他并不从整体最优上加以考虑，而是做出在当前看来是最好的选择。

1.把解决问题的过程分为若干步骤。

2.解决每一步时都选取当前看起来最优的选择。

3.“希望”得到全局最优解。（注意是“希望”，可不一定就是最优解）

简单形容就是贪婪+鼠目寸光，因此叫做贪心算法。

下面介绍几个典型的示例：

在这里插入图片描述

2.贪心算法的特点

贪心策略的提出
- 贪心策略的提出是没有标准和模板的，可能每一道题的贪心策略都是不同的，因此在学习贪心算法的时候重点要掌握每一道题的策略，把这道题的策略当成经验。
贪心策略的正确性
- 前面提到一个词“希望”得到最优解，因为有可能“贪心策略是一个错误的方法，正确的贪心策略，是需要严格的数学证明。

二.例题

1.柠檬水找零

题目：

在这里插入图片描述

算法原理：

根据题意可以明白，顾客付钱有三种情况，如果是5美元，那就直接收下；如果是10美元，并且当前手里5美元的数量大于等于1，收下然后找零5美元，如果没有5美元，则返回false；如果是20美元，有两种找零方式，第一种：10+5；第二种：5+5+5；这里就用到了贪心的思想，优先使用第一种方式找零。如果第一次20美元使用第二种找零方式，恰好手里有三张5美元，一张10美元，如果第一次就使用三张5美元，等之后再次遇到10美元，就只剩一张10美元，不能找零。

这里用到的是交换论证法：如果20美元使用第二种找零方式，手里的10美元一直到最后也没有使用，因此10美元可以替换20美元找零时的两张5美元；如果第一次20美元使用第二种找零方式5+5+5，第二次使用第一种方式找零10+5，第二次的10可以和第一次的两张5交换，交换后无影响。

代码实现：

bool lemonadeChange(vector<int>& bills){
    //设置两个变量一个用来表示5元的个数，一用来表示10元的个数
    int five = 0, ten = 0;

    for(auto x : bills){
        //如果给的是5元，直接收下
        if(x==5){
            five++;
        }
        //如果给的是10元，先判度是否有5元找零，有就找零收下，没有就返回
        if(x==10){
            if(five==0){
                return false;
            }
            else{
                five--;
                ten++;
            }
        }
        //如果给的是20元，有三种情况
        if(x==20){
            //贪心思想，优先考虑10+5找零
            if(ten&&five){
                five--;
                ten--;
            }
            //第一种不能找零，再考虑第二种找零方式5+5+5
            else if(five>=3){
                five -= 3;
            }
            //如果两种情况都不能找零，返回
            else{
                return false;
            }
        }
    }
    return true;
}

2.将数组和减半的最小操作次数

题目：

在这里插入图片描述

算法原理：

因此本道题的贪心策略：使用最少的操作次数完成数组和的减半，因此每次选择一个数减半时，都选择最大的那个数减半，这里就是贪心的思想，每次都选择最大的数减半。既然要快速获取数组中的最大数，就可以借助大根堆这个数据结构，每次都选择堆顶的元素减半，减半后从新放回堆中调整，然后循环进行，知道数组和减到一半，返回最小操作数。

代码实现：

int halveArray(vector<int>& nums){
    //建立一个大根堆
    priority_queue<double> heap;

    //遍历数组求和并存放到堆中
    double sum = 0.0;
    for(int x : nums){
        heap.push(x);
        sum += x;
    }

    //先获取数组和的一半，每次减去堆顶元素的一半直到减为小于等于0
    sum /= 2.0;
    int count=0;
    while(sum>0){
        //获取堆顶元素的一半,并删去
        double t = heap.top() / 2.0;
        heap.pop();
        count++;
        sum -= t;
        heap.push(t);
    }

    return count;
}

3.最大数

题目：

在这里插入图片描述

算法原理：

根据题意要求，可以自定义排序规则，因为要返回的是组合后最大的数，所以按照自定义的排序规则从大到小的排序；比如现在有两个数，a和b，有两种组合方式ab和ba，如果组合后ab>ba，则a在前，b在后；如果ab=ba，则a=b；如果ab<ba，则b在前，a在后；比如示例一：a=10，b=2，组合后ab=102<ba=210，所以b(2)在前，a(10)在后，根据自定义排序规则将整个数组中的元素都排序后，然后从前往后组合就是要找的最大数。

这里有一个细节点，如何快速的将两个数组合比较？可以先将每一个数都转化成字符串的形式，组合时直接的将两个字符串相加拼接即可，这样就能快速的组合，最后排完序后，还可以直接从前往后将所有字符串拼接，就是要返回的结果。

至于为什么上面的这个自定义排序规则是正确的，可以看下面的证明过程：

在这里插入图片描述

代码实现：

string largestNumber(vector<int>& nums){
    //先将每个数字转换成字符串，存放到字典数组中
    vector<string> dictionary;
    for(auto x : nums){
        dictionary.push_back(to_string(x));
    }

    //使用Lambda表达式自定义排序规则
    sort(dictionary.begin(), dictionary.end(), [&](const string& s1, const string& s2){
        return s1 + s2 > s2 + s1; 
    });

    string ret;
    for(auto s : dictionary){
        ret += s;
    }

    if(ret[0]=='0'){
        return "0";
    }
    return ret;
}

4.摆动序列

题目：

在这里插入图片描述

算法原理：

在这里插入图片描述

代码实现：

//全局变量表示左侧的峰值
int left = 0;
int wiggleMaxLength(vector<int>& nums){
    //寻找波峰和波谷
    int ret = 0;

    for (int i = 0; i < nums.size(); i++){
        //如果是最后一个位置，直接+1
        if(i==nums.size()-1){
            ret++;
            break;
        }
        //先计算当前位置右侧的峰值
        int right = nums[i + 1] - nums[i];
        //如果右侧峰值等于0，跳过
        if(right==0){
            continue;
        }

        //如果左右两侧峰值相乘小于0，表示当前位置是波峰或者波谷
        if(left*right<=0){
            ret++;
        }

        //将当前位置的右侧峰值赋值给左侧，表示下一个位置的左侧峰值
        left = right;
    }

    return ret;
}