【算法】贪心算法练习一
1. 贪心算法的介绍
一、贪心策略：解决问题的策略，局部最优->全局最优
- 把解决问题的过程分为若干步；
- 解决每一步的时候，都选择当前看起来“最优的”解法；
- 希望得到全局最优。
二、贪心策略的正确性 因为有可能“贪心策略”是一个错误的方法 正确的贪心策略，是需要证明的
常见的证明方法就是在数学中见过的所有证明方法。
三、学习贪心算法的方向 遇到不会的贪心题，很正常，把心态放平。
- 前期学习的时候，把重点放在贪心的策略上，把这个策略当做经验吸收。
- 如何证明贪心策略是正确的
2. 860. 柠檬水找零
2.1 分析
一、题目解析 题目已经提到：一开始你手头没有任何零钱，如果第一个顾客给的钱超过了5美元，那么就没有零钱找，就返回false。 考虑当前的顾客时候，是不考虑后面的顾客。
二、算法原理 分情况讨论：第一种：当顾客给了5美元，就直接收下； 第二种，当顾客给了10美元，先判断一下有没有5美元，有就收下，没有就返回false; 第三种：20美元的找零，可以分一张10和一张5；还可以找三种5块钱，有分歧的时候就得判断一下哪一个找零更好，是10+5，还是5+5+5，所以对于5块钱的作用很大的时候，就把5块钱保留。
2.2 代码
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five=0,ten=0;
for(auto x: bills)
{
if(x==5) five++;
else if(x==10)
{
if(five==0) return false;
five--;ten++;
}
else
{
if(ten&&five)
{
ten--;five--;
}
else if(five>=3)
{
five-=3;
}
else return false;
}
}
return true;
}
};3. 2208. 将数组和减半的最少操作次数
3.1 分析
一、题目解析 题目要求返回将 nums 数组和至少减少一半的最少操作数，看一下例1：
数组和是33，一半就是16.5，先选择19减半就是9.5，此时数组和没有小于16.5；然后继续选择9.5减半为4.75，此时数组和没有小于16.5；再选择8减半为4，此时此时数组和小于16.5，总共就三次减半。
二、算法原理 每次挑选当前数组中，最大的那个数，然后减半，最大的数减半，才有可能最快减到数组和减少到至少一半。 为了选择最大的数，遍历一遍数组的时间复杂度太高了，所以就用一个大根堆，每次堆顶的元素就是最大的数。
3.2 代码
class Solution {
public:
int halveArray(vector<int>& nums) {
priority_queue<double> heap;
double sum=0;
for(auto x:nums)
{
heap.push(x);
sum+=x;
}
sum/=2.0;
int count=0;
while(sum>0)
{
double t=heap.top()/2;
heap.pop();
sum-=t;
count++;
heap.push(t);
}
return count;
}
};4. 179. 最大数
4.1 分析
一、题目解析 题目已经提到： 要得到最大的拼接数，就得先把这些数先拼接起来，然后比较找到最大的那一个就行。
二、算法原理 这里就得排序，确定元素的先后顺序：谁在前，谁在后 给这个数组排序，比如[a,b]：如果ab>ba,那么a前,b后；如果ab=ba，那么顺序无所谓；如果ab<ba,那么b前，a后。 比较数的拼接大小比较麻烦，可以把数转换为字符串，然后拼接字符串，比较字典序。 如果传[0,0]，那么就会出现前导0的情况，所以在最后的结果中，就直接返回0。
4.2 代码
class Solution {
public:
string largestNumber(vector<int>& nums) {
vector<string> strs;
for(int x:nums)strs.push_back(to_string(x));
sort(strs.begin(),strs.end(),[](const string& s1,const string& s2)
{
return s1+s2>s2+s1;
});
string ret;
for(auto& s:strs)
{
ret+=s;
}
if(ret[0]=='0')return "0";
return ret;
}
};有问题请指出，大家一起进步！！！
腾讯云开发者
