【贪心算法】No.1---贪心算法（1)

---

前言

👧个人主页：@小沈YO.
😚小编介绍：欢迎来到我的乱七八糟小星球🌝
📋专栏：贪心算法
🔑本章内容：贪心算法
记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~

---

一、贪心算法：

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。贪心算法解决问题的过程中，每一步都做出一个看似最优的决策，这个决策依赖于当前问题状态，不依赖于解决问题的前面的步骤和将来的步骤。这种方法在很多情况下并不会得到最优解，但是在某些问题上贪心算法的解就是最优解。

二、贪心算法示例：

1.1 柠檬⽔找零

1. 题⽬链接：860. 柠檬⽔找零
2. 题⽬描述
   
3. 解法（贪⼼）：
   贪⼼策略：
   分情况讨论：
   a. 遇到 5 元钱，直接收下；
   b. 遇到 10 元钱，找零 5 元钱之后，收下；
   c. 遇到 20 元钱：
   i. 先尝试凑 10 + 5 的组合；
   ii. 如果凑不出来，拼凑 5 + 5 + 5 的组合；
4. C++代码

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five=0,ten=0;for(int i=0;i<bills.size();i++){if(bills[i]==5)five++;else if(bills[i]==10){ten++;if(five>0)five--;else return false;}else{if(ten>0&&five>0)//贪心{ten--;five--;}else if(five>=3)five-=3;else return false;}}return true;}
};

1.2 将数组和减半的最少操作次数

1. 题⽬链接：2208. 将数组和减半的最少操作次数
2. 题⽬描述：
   
3. 解法（贪⼼）：
   贪⼼策略：
   a. 每次挑选出「当前」数组中「最⼤」的数，然后「减半」；
   b. 直到数组和减少到⾄少⼀半为⽌。
   为了「快速」挑选出数组中最⼤的数，我们可以利⽤「堆」这个数据结构
4. C++代码

class Solution {double sum=0,cnt=0;priority_queue<double,vector<double>,less<double>> pq;
public:int halveArray(vector<int>& nums) {for(auto&e:nums){  sum+=e;pq.push(e);}sum/=2.0;while(sum>0){cnt++;double tmp=pq.top()/2;pq.pop();sum-=tmp;pq.push(tmp);}return cnt;}
};

1.3 最⼤数

1. 题⽬链接：179. 最⼤数
2. 题⽬描述
   
3. 解法（贪⼼）：
   可以先优化：将所有的数字当成字符串处理，那么两个数字之间的拼接操作以及⽐较操作就会很⽅便。
   贪⼼策略：按照题⽬的要求，重新定义⼀个新的排序规则，然后排序即可。
   排序规则：
   a. 「A 拼接 B」 ⼤于 「B 拼接 A」，那么 A 在前，B 在后；
   b. 「A 拼接 B」 等于 「B 拼接 A」，那么 A B 的顺序⽆所谓；
   c. 「A 拼接 B」 ⼩于 「B 拼接 A」，那么 B 在前，A 在后；
4. C++代码

class Solution {
public:string largestNumber(vector<int>& nums) {vector<string> v;for(auto&e:nums)v.push_back(to_string(e));string ret;sort(v.begin(),v.end(),[](string& s1,string& s2){return s1+s2>s2+s1;});for(int i=0;i<v.size();i++){if(i==0&&v[i]=="0")return "0";ret+=v[i];}return ret;}
};

1.4 摆动序列

1. 题⽬链接：376. 摆动序列
2. 题⽬描述
   
3. 解法（贪⼼）：
   贪⼼策略：
   对于某⼀个位置来说：
   ◦ 如果接下来呈现上升趋势的话，我们让其上升到波峰的位置；
   ◦ 如果接下来呈现下降趋势的话，我们让其下降到波⾕的位置。
   因此，如果把整个数组放在「折线图」中，我们统计出所有的波峰以及波⾕的个数即可。
4. C++代码

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int left=0,ret=0;for(int i=0;i<nums.size()-1;i++){int right=nums[i+1]-nums[i];if(right==0)continue;if(right*left<=0)ret++;left=right;}return ret+1;//加上最后一个}
};

1.5 最⻓递增⼦序列

1. 题⽬链接：300. 最⻓递增⼦序列
2. 题⽬描述：
   
3. 解法（贪⼼）：
   贪⼼策略：
   我们在考虑最⻓递增⼦序列的⻓度的时候，其实并不关⼼这个序列⻓什么样⼦，我们只是关⼼最后⼀个元素是谁。这样新来⼀个元素之后，我们就可以判断是否可以拼接到它的后⾯。
   因此，我们可以创建⼀个数组，统计⻓度为 x 的递增⼦序列中，最后⼀个元素是谁。为了尽可能的让这个序列更⻓，我们仅需统计⻓度为 x 的所有递增序列中最后⼀个元素的「最⼩值」。
   统计的过程中发现，数组中的数呈现「递增」趋势，因此可以使⽤「⼆分」来查找插⼊位置。
4. C++代码

class Solution {int cnt=0;
public:int lengthOfLIS(vector<int>& nums) {int n=nums.size();vector<int> ret;ret.push_back(nums[0]);for(int i=1;i<nums.size();i++){if(nums[i]>ret.back())ret.push_back(nums[i]);//可以拼接到后面//如果不可以拼接到末尾则需要找到ret中出现第一次>=nums[i]的值进行替换，也就是把这个第一次大的值换成小的nums[i]else{int left=0,right=ret.size()-1;while(left<right){int mid=left+(right-left)/2;if(ret[mid]>=nums[i])right=mid;else left=mid+1;}ret[left]=nums[i];}}return ret.size();}
};

1.6 递增的三元⼦序列

1. 题⽬链接：334. 递增的三元⼦序列
2. 题⽬描述
   
3. 解法（贪⼼）：
   贪⼼策略：
   最⻓递增⼦序列的简化版。
   不⽤⼀个数组存数据，仅需两个变量即可。也不⽤⼆分插⼊位置，仅需两次⽐较就可以找到插⼊位置
4. C++代码

class Solution {
public:bool increasingTriplet(vector<int>& nums) {int n=nums.size();vector<int> ret;ret.push_back(nums[0]);for(int i=1;i<n;i++){if(nums[i]>ret.back())ret.push_back(nums[i]);else{int left=0,right=ret.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[i]>ret[mid])left=mid+1;else right=mid;}ret[left]=nums[i];}}return ret.size()>=3?true:false;}
};
----------------------------------------------------------------------------------------------
class Solution {
public:bool increasingTriplet(vector<int>& nums) {int n=nums.size();int a=nums[0],b=INT_MAX;for(int i=1;i<n;i++){if(nums[i]>b)return true;else{if(nums[i]<=a)a=nums[i];else b=nums[i];}}return false;}
};