当前位置：首页 > news >正文

【算法】贪心算法:柠檬水找零C++

news 2025/8/28 13:10:00

在日常生活的交易场景中，找零问题是最常见的算法应用场景之一。柠檬水找零问题作为贪心算法的经典案例，其核心在于如何利用有限的零钱组合，高效完成每一笔交易的找零操作。本文将详细解析该问题的解题思路，并通过 C++ 代码实现贪心策略的具体应用。

问题描述与分析

问题定义

在柠檬水摊上，每杯柠檬水售价为 5 美元。顾客排队购买你的产品，每人只能购买一杯。顾客支付的钱币面额可能为 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零（即每位顾客支付的金额减去 5 美元后，你需要恰好返还）。初始时你手头没有任何零钱。

给定一个整数数组bills，其中bills[i]表示第 i 位顾客支付的金额，请判断你是否能给每位顾客正确找零。如果能，返回true；否则，返回false。

示例分析

示例 1：bills = [5,5,5,10,20] → 返回true

第 1 位顾客付 5 美元，无需找零，手中有 1 张 5 美元
第 2 位顾客付 5 美元，无需找零，手中有 2 张 5 美元
第 3 位顾客付 5 美元，无需找零，手中有 3 张 5 美元
第 4 位顾客付 10 美元，找零 5 美元，手中有 2 张 5 美元和 1 张 10 美元
第 5 位顾客付 20 美元，找零 15 美元（1 张 10 美元 + 1 张 5 美元），手中有 1 张 5 美元、0 张 10 美元和 1 张 20 美元

示例 2：bills = [5,5,10,10,20] → 返回false

前 4 位顾客交易后，手中有 1 张 5 美元和 2 张 10 美元
第 5 位顾客付 20 美元需找零 15 美元，此时若用 1 张 10 美元 + 1 张 5 美元找零，剩余零钱无法满足后续可能的 10 美元支付

问题核心

该问题的关键在于找零策略的选择：当需要找零 15 美元时（面对 20 美元支付），应优先使用 1 张 10 美元 + 1 张 5 美元的组合，而非 3 张 5 美元。因为 5 美元零钱的用途更广泛（可用于找零 5 美元和 15 美元），而 10 美元只能用于找零 15 美元。这种 "优先消耗大额零钱" 的策略正是贪心算法的体现。

贪心算法解题思路

贪心策略设计

贪心算法的核心思想是在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优。对于柠檬水找零问题，最优策略如下：

只维护两种零钱：5 美元和 10 美元（20 美元无法用于找零，无需统计）
面对 5 美元支付：直接收入，不找零，增加 5 美元计数
面对 10 美元支付：必须找零 5 美元，若有 5 美元则完成交易（5 美元计数减 1，10 美元计数加 1），否则失败
面对 20 美元支付：优先找零 1 张 10 美元 + 1 张 5 美元（更优策略），若该组合不可行则尝试找零 3 张 5 美元，若都不可行则失败

算法步骤

初始化两个计数器：five（5 美元数量）和ten（10 美元数量），初始值均为 0
遍历顾客支付数组bills：

若支付 5 美元：five++
若支付 10 美元：

若five == 0：返回false（无法找零）
否则：five--，ten++

若支付 20 美元：

若ten > 0 且 five > 0：ten--，five--（优先使用 10+5 组合）
else if five >= 3：five -= 3（使用 3 张 5 美元）
else：返回false（无法找零）

遍历完成后返回true

C++ 代码实现

完整代码

#include <vector>using namespace std;class Solution {public:    bool lemonadeChange(vector<int>& bills) {        int five = 0, ten = 0;  // 记录5美元和10美元的数量        for (int bill : bills) {            if (bill == 5) {                // 收到5美元，直接收入                five++;            } else if (bill == 10) {                // 收到10美元，需要找零5美元                if (five == 0) {                    return false;  // 没有5美元可找零                }                five--;                ten++;            } else {  // bill == 20                // 收到20美元，优先找零10+5组合                if (ten > 0 && five > 0) {                    ten--;                    five--;                } else if (five >= 3) {                    // 没有10美元，用3张5美元找零                    five -= 3;                } else {                    // 两种方式都无法找零                    return false;                }            }        }        // 所有顾客都成功找零        return true;    }};

代码解析

变量设计：使用两个整数five和ten分别记录 5 美元和 10 美元的数量，空间复杂度为 O (1)
循环逻辑：遍历每个顾客的支付金额，根据不同面额执行相应的找零操作
贪心选择：在处理 20 美元支付时，优先消耗 10 美元零钱，保留更多 5 美元零钱用于后续可能的找零需求
终止条件：一旦出现无法找零的情况立即返回false，全部处理完成则返回true

时间复杂度与空间复杂度

时间复杂度：O (n)，其中 n 为顾客数量，只需遍历一次数组
空间复杂度：O (1)，仅使用固定数量的额外变量，与输入规模无关

测试用例验证

测试用例 1：基础可行场景

vector<int> bills = {5,5,5,10,20};Solution sol;cout << (sol.lemonadeChange(bills) ? "true" : "false") << endl;  // 输出true

执行过程：

处理 5→five=1
处理 5→five=2
处理 5→five=3
处理 10→five=2，ten=1
处理 20→ten=0，five=1 → 成功

测试用例 2：找零失败场景

vector<int> bills = {5,5,10,10,20};cout << (sol.lemonadeChange(bills) ? "true" : "false") << endl;  // 输出false

执行过程：

处理 5→five=1
处理 5→five=2
处理 10→five=1，ten=1
处理 10→five=0，ten=2
处理 20→ten>0 但 five=0，且 five<3 → 失败

测试用例 3：边界情况

// 首个顾客支付10美元（无法找零）vector<int> bills1 = {10};cout << (sol.lemonadeChange(bills1) ? "true" : "false") << endl;  // 输出false// 全部支付5美元vector<int> bills2 = {5,5,5,5};cout << (sol.lemonadeChange(bills2) ? "true" : "false") << endl;  // 输出true// 20美元找零使用3张5美元的情况vector<int> bills3 = {5,5,5,20};cout << (sol.lemonadeChange(bills3) ? "true" : "false") << endl;  // 输出true