【贪心算法题目】

1. 柠檬水找零

这一个题目是一个比较简单的模拟算法，只需要根据手里的钱进行找零即可，对于贪心的这一点，主要是在20元钱找零的情况下，此时会出现两种情况：10 + 5 的组合 和 5 + 5 + 5 的组合，根据找零的特点，5元钱可以对10元和20元找零，而10元钱只能对20找零，5元钱的作用相对较大，所以根据贪心的思想，我们是对于20元找零优先0 + 5 的组合，直接上思路：

C++ 算法代码：

注意：由于本题最大的面值是20元，所以只需要统计5元和10元的数量即可。

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0;
        for (auto x : bills)
        {
            if (x == 5) five++; // 5 元：直接收下
            else if (x == 10) // 10 元：找零 5 元
            {
                if (five == 0) return false;
                else five--; ten++;
            }
            else // 20 元：分情况讨论
            {
                // 优先处理组合:10 + 5
                if (ten != 0 && five != 0) // 贪⼼
                {
                    ten--; five--;
                }
                // 其次处理组合:5 + 5 + 5
                else if (five >= 3)
                {
                    five -= 3;
                }
                else return false;
            }
        }
        return true;
    }
};

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

我们来看看这个题目，将数组和减半的最少操作此时，根据贪心的策略，只要我们每次都选择最大值，将最大值依次减半就可以控制到操作次数最少，直接看思路：

C++ 算法代码：

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;
		}
		sum /= 2.0; // 先算出⽬标和
		int count = 0;
		while (sum > 0) // 依次取出堆顶元素减半，直到减到之前的⼀半以下
		{
			double t = heap.top() / 2.0;
			heap.pop();
			sum -= t;
			count++;
			heap.push(t);
		}
		return count;
	}
};

3. 最大数

这个题目依然是采用贪心来解决，将所有的数字当成字符串处理，那么两个数字之间的拼接操作以及比较操作就会很方便，此时我们只需要找出每次两个值组合的最大的排序方式重新定义⼀个新的排序规则，然后排序即可即可解决问题。

C++ 算法代码：

细节问题：有可能数组中所有的元素都是0，此时结果会有很多0，因此我们需要单独去除前导0。

class Solution
{
public:
	string largestNumber(vector<int>& nums)
	{
		// 优化：把所有的数转化成字符串
		vector<string> strs;
		for (int x : nums) strs.push_back(to_string(x));
		// 排序 - lambda表达式
		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;
	}
};

4. 摆动序列

何为一个摆动序列，我们可以类比一个折线图，题目上要求我们求出最长的摆动序列，那么根据贪心的思想，我们希望到达峰值或者峰低的点尽量大或者小，以此来达到最长的要求，直接上思路：

C++ 算法代码：

class Solution
{
public:
	int wiggleMaxLength(vector<int>& nums)
	{
		int n = nums.size();
		if (n < 2) return n;
		int ret = 0, left = 0;
		for (int i = 0; i < n - 1; i++)
		{
			int right = nums[i + 1] - nums[i]; // 计算接下来的趋势
			if (right == 0) continue; // 如果⽔平，直接跳过
			if (right * left <= 0) ret++; // 累加波峰或者波⾕
			left = right;
		}
		return ret + 1;
	}
};