贪心算法（一）
目录
一、贪心算法
贪心算法的本质是选择每一阶段的局部最优，从而达到全局最优。
贪心策略：1、把解决问题的过程分为若干步。2、解决每一步的时候，都选择当前看起来最优的解法。3、最后希望得到全局最优解。
例子：找零问题
小明买完东西正在付钱，他买了4元钱的东西，然后付给收银员50元，那么收银员要找给他46元，此时收银员手里有 [ 20，10，5，1 ]这些钱，那么应该如何找呢？
我们最先想到的就是尽量先用面值大的去凑出找零，选出2张20，1张5元，1张1元就可以了。
这里的尽量先用面值大的去凑出找零，就是一种贪心策略。
贪心算法的特点
1、贪心策略的提出：贪心策略的提出是没有标准和模板的，可能每一道题的贪心策略都是不同的。
2、贪心策略的正确性：一道题的贪心策略可能最终得到的结果是错误的，所以贪心策略是否正确是需要证明的。
二、柠檬水找零
贪心策略：
对于找零来说，我们最需要考虑的是顾客支付20元的情况，因为如果顾客支付20元的话，找零方法有两种，那么是随便选择哪种方法找零都可以吗？不是的，我们需要选择哪种对20元找零的方法是最好的。
如果是这种情况：现在手里有一张10元，三张5元的。此时来了一个顾客，支付了20元，如果选择第一种对于20元的找零方法，那么找零后，手里就剩了一张20元和一张10元的，然后又来了一个顾客，支付10元，那么此时就无法找零了。
而如果选择第二种对于20元的找零方法，那么找零后，手里就剩了两张5元，一张20元，然后又来了一个顾客，支付10元，那么此时就可以找零了。
所以说，本道题的贪心策略就是，在对于20元进行找零的时候，尽量使用第二种方法找零，也就是尽量保留5元的，因为支付10元只有找零5元这一种方法。
解题代码：
class Solution
{
public:
bool lemonadeChange(vector<int>& bills)
{
int five = 0, ten = 0; // 记录5元和10元的张数
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;
}
}; 
三、将数组和减半的最少操作次数
分析题目，题目要求我们求出将数组和至少减小一半的最小操作数。我们可以想想，怎么用最少的次数将数组和减少一半呢？
因为我们每次可以选一个数，对其进行减半操作，所以，选择数组中怎样的一个数就是重点了。打个比方，如果选2，那么进行一次操作后，数组总和会减少1，而如果选择4，进行一次操作后，数组总和会减少2。也就是说，每次选择数组中最大的数，就可以用最少的次数，将数组和减半。
贪心策略：
每次挑选当前数组中最大的那个数，将它减半，直到数组和减小到至少一半为止。
我们可以使用一个大根堆，来保存数组元素，堆顶元素就是数组中，目前来说的最大元素，这样就不需要每次遍历去找数组的最大值了。
解题代码：
class Solution
{
public:
int halveArray(vector<int>& nums)
{
priority_queue<double> heap;
double sum = 0.0;
for(int& x : nums)
{
heap.push(x);
sum += x;
}
double tmp = sum;
tmp /= 2.0;
int count = 0;
while(sum > tmp)
{
double top = heap.top();
heap.pop();
sum -= top / 2.0;
count++;
heap.push(top / 2.0);
}
return count;
}
}; 
四、最大数
题目分析：根据题意，题目要求我们确定各个元素的顺序，然后将它们按这个顺序组合起来，使组成的整数是最大的。比如示例一，其中的元素可以组成 102和210两个整数，结果就是最大的210。
贪心策略：
根据题目分析，我们最终的目的是将数组的元素按照一定的规则，按顺序放置，也就是对元素进行排序，就得到元素组成的整数是最大的。而本题的元素排序规则如下：
解题代码：
class Solution
{
public:
string largestNumber(vector<int>& nums)
{
vector<string> num;
for(auto& e : nums)
num.push_back(to_string(e));
sort(num.begin(), num.end(), [&](const string& s1, const string& s2)
{
return s1+s2 > s2+s1;
});
string ret = "";
for(auto& x : num)
ret += x;
if(ret[0] == '0')
return "0";
return ret;
}
};
五、摆动序列
贪心策略：
如下图，找出数组中处于波峰和波谷位置元素，再加上两个端点的元素，组成的序列就是最长的摆动序列。统计出它们的个数就是最长的摆动序列的长度。
如何统计最长的摆动序列的长度
确定一个元素处于波峰，用该元素减去它前面一个的元素，差值sum1是大于0的。然后用它后面的元素减去它自己，差值sum2是小于0的，得到 sum1 * sum2是小于0的。
确定一个元素处于波谷，用该元素减去它前面一个的元素，差值sum1是小于0的。然后用它后面的元素减去它自己，差值sum2是大于0的，得到 sum1 * sum2是小于0的。
所以说，对于一个元素，如果用该元素减去它前面一个的元素得到的差值与用它后面的元素减去它自己得到的差值，相乘是负数，就说明该元素处于波峰或者波谷，那么这个元素就属于最长摆动序列的一员，统计长度时就要算上它。
最后再加上两个端点，就是最长摆动序列的长度了。
解题代码：
class Solution
{
public:
int wiggleMaxLength(vector<int>& nums)
{
// 贪心算法
int m = nums.size();
if(m < 2)
return m;
int ret = 0, left = 0;
for(int i = 0; i < m-1; i++)
{
int right = nums[i+1] - nums[i];
if(right == 0) continue;
if(left*right <= 0)
ret++;
left = right;
}
return ret+1;
}
}; 
原文地址：https://blog.csdn.net/zdlynj/article/details/142642414
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！