本文主要是介绍「贪心算法」柠檬水找零，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
力扣原题链接，点击跳转。
假设你的手里没有钱。你要卖柠檬水，每杯5块钱。每个顾客有可能会给你5块钱、10块钱或20块钱，你要拿手中的钱找零。如何判断你能否成功找零呢？
如果一上来就有顾客花10块钱或20块钱，你手中没有钱，自然无法找零。我们考虑一下能找零的情况。如果有顾客花10块钱，你就要找5块钱，如果你手里没有5块钱，则找零失败。如果有顾客花20块钱，你可以找一张10块钱和一张5块钱，或者三张5块钱。如果是你，你会选择一张10块钱和一张5块钱，还是三张5块钱呢？显然，10块钱的作用并不大，只有顾客花20块钱时，才有可能用作找零；但是5块钱的作用就非常大了，不管顾客花10块钱还是20块钱，都有可能用作找零。所以，我们应尽可能把作用不大的10块钱花出去，把作用较大的5块钱留在手里，这就是贪心策略。换句话说，我们优先考虑10+5，如果不行，再考虑5+5+5，如果还不行，那就找零失败。
class Solution
{
public:bool lemonadeChange(vector<int>& bills){int five = 0, ten = 0;for (auto bill : bills){if (bill == 5){five++;}else if (bill == 10){if (five == 0){return false;}five--;ten++;}else{// 贪心，10+5优先于5*3if (five && ten){five--;ten--;}else if (five >= 3){five -= 3;}else{return false;}}}return true;}
};这篇关于「贪心算法」柠檬水找零的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
