个人主页 : zxctscl
如有转载请先通知
题目
- 1. 贪心算法的介绍
- 2. 860. 柠檬水找零
- 2.1 分析
- 2.2 代码
- 3. 2208. 将数组和减半的最少操作次数
- 3.1 分析
- 3.2 代码
- 4. 179. 最大数
- 4.1 分析
- 4.2 代码
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;
}
};
有问题请指出,大家一起进步!!!