目录
1. 贪心算法简介
2. 柠檬水找零
题目链接：860. 柠檬水找零 - 力扣（LeetCode）
题目展示：
题目分析：
贪心策略：
分情况讨论：
a. 遇到5 元钱，直接收下；
b. 遇到10 元钱，找零5 元钱之后，收下；
c. 遇到20 元钱：
i. 先尝试凑0 + 5 的组合；
ii. 如果凑不出来，拼凑5 + 5 + 5 的组合；
这里就体现了贪心的思想，优先选择最优的方案。
代码实现：
class Solution {
public:
bool lemonadeChange(vector<int>& bills)
{
int five=0;
int ten=0;
for(auto x:bills)
{
if(x==5)
{
five++;
}
else if(x==10)
{
if(five==0) return false;
else
{
five--;
ten++;
}
}
else
{
//贪心
if(ten&&five)
{
five--;
ten--;
}
else if (five>=3)
{
five-=3;
}
else
{
return false;
}
}
}
return true;
}
};3. 将数组和减半的最少操作次数
题目链接：2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）
题目展示：
题目分析：
贪心策略：
a. 每次挑选出「当前」数组中「最⼤」的数，然后「减半」；
b. 直到数组和减少到⾄少⼀半为止。 为了「快速」挑选出数组中最大的数，我们可以利用大根堆来寻找。
代码实现：
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 ret=heap.top()/2.0;
heap.pop();
sum-=ret;
count++;
heap.push(ret);
}
return count;
}
};4. 递增的三元子序列
题目链接：334. 递增的三元子序列 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
class Solution {
public:
bool increasingTriplet(vector<int>& nums)
{
int a=nums[0];
int b=INT_MAX;
for(int i=0;i<nums.size();i++)
{
if(nums[i]>b) return true;
else if(nums[i]>a) b=nums[i];
else a=nums[i];
}
return false;
}
};5. K次取反后最大化的数组和
题目链接：1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
题目展示；
题目分析：
代码实现：
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k)
{
int m=0;
int n=nums.size();
int minElem=INT_MAX;
for(auto x:nums)
{
if(x<0)
{
m++;
}
minElem=min(minElem,abs(x));
}
int ret=0;
if(m>k)
{
sort(nums.begin(),nums.end());
for(int i=0;i<k;i++)
{
ret+=-nums[i];
}
for(int i=k;i<n;i++)
{
ret+=nums[i];
}
}
else
{
//先把所有负数变成正数
for(auto x:nums) ret+=abs(x);
if((k-m)%2)
{
ret-=minElem*2;
}
}
return ret;
}
};6. 增减字符串匹配
题目链接：942. 增减字符串匹配 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
class Solution {
public:
vector<int> diStringMatch(string s)
{
int left=0,right=s.size();
vector<int> ret;
for(auto ch:s)
{
if(ch=='I')
{
ret.push_back(left++);
}
else if(ch=='D')
{
ret.push_back(right--);
}
}
ret.push_back(left);
return ret;
}
};7. 分发饼干
题目展示：
题目分析：
代码实现：
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s)
{
int ret=0;
int m=g.size();
int n=s.size();
//排序
sort(g.begin(),g.end());
sort(s.begin(),s.end());
for(int i=0,j=0;i<m&&j<n;i++,j++)
{
while(j<n&&s[j]<g[i]) j++;
if(j<n) ret++;
}
return ret;
}
};8. 整数替换
题目展示：
题目分析：
代码实现：