​860. 柠檬水找零​,406.根据身高重建队列

简介: **简介:**本文介绍了两道经典算法题的解法与思路。第一题“柠檬水找零”通过贪心算法解决找零问题,核心在于优先使用大面额钞票找零以保留更灵活的小面额;第二题“根据身高重建队列”利用排序与插入操作,通过先按身高降序排列再按k值插入位置的方式实现队列重建。两题均体现了贪心算法在局部最优推导全局最优中的应用,同时展示了如何通过合理排序和模拟操作高效解决问题。

 题目:860. 柠檬水找零

在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。

每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。

注意,一开始你手头没有任何零钱。

给你一个整数数组 bills ,其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零,返回 true ,否则返回 false 。

示例 1:

输入:bills = [5,5,5,10,20]

输出:true

解释:

前 3 位顾客那里,我们按顺序收取 3 张 5 美元的钞票。

第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。

第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。

由于所有客户都得到了正确的找零,所以我们输出 true。

示例 2:

输入:bills = [5,5,10,10,20]

输出:false

解释:

前 2 位顾客那里,我们按顺序收取 2 张 5 美元的钞票。

对于接下来的 2 位顾客,我们收取一张 10 美元的钞票,然后返还 5 美元。

对于最后一位顾客,我们无法退回 15 美元,因为我们现在只有两张 10 美元的钞票。

由于不是每位顾客都得到了正确的找零,所以答案是 false。

提示:

1 <= bills.length <= 105

bills[i] 不是 5 就是 10 或是 20  

思考历程与知识点:  

有如下三种情况:

情况一:账单是5,直接收下。

情况二:账单是10,消耗一个5,增加一个10

情况三:账单是20,优先消耗一个10和一个5,如果不够,再消耗三个5

此时大家就发现 情况一,情况二,都是固定策略,都不用我们来做分析了,而唯一不确定的其实在情况三。

而情况三逻辑也不复杂甚至感觉纯模拟就可以了,其实情况三这里是有贪心的。

账单是20的情况,为什么要优先消耗一个10和一个5呢?

因为美元10只能给账单20找零,而美元5可以给账单10和账单20找零,美元5更万能!

所以局部最优:遇到账单20,优先消耗美元10,完成本次找零。全局最优:完成全部账单的找零。

题解:

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0, twenty = 0;
        for (int bill : bills) {
            // 情况一
            if (bill == 5) five++;
            // 情况二
            if (bill == 10) {
                if (five <= 0) return false;
                ten++;
                five--;
            }
            // 情况三
            if (bill == 20) {
                // 优先消耗10美元,因为5美元的找零用处更大,能多留着就多留着
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                    twenty++; // 其实这行代码可以删了,因为记录20已经没有意义了,不会用20来找零
                } else if (five >= 3) {
                    five -= 3;
                    twenty++; // 同理,这行代码也可以删了
                } else return false;
            }
        }
        return true;
    }
};

 题目:406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ,前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ,其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性(queue[0] 是排在队列前面的人)。

示例 1:

输入:people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

输出:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

解释:

编号为 0 的人身高为 5 ,没有身高更高或者相同的人排在他前面。

编号为 1 的人身高为 7 ,没有身高更高或者相同的人排在他前面。

编号为 2 的人身高为 5 ,有 2 个身高更高或者相同的人排在他前面,即编号为 0 和 1 的人。

编号为 3 的人身高为 6 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。

编号为 4 的人身高为 4 ,有 4 个身高更高或者相同的人排在他前面,即编号为 0、1、2、3 的人。

编号为 5 的人身高为 7 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。

因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2:

输入:people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]

输出:[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示:

1 <= people.length <= 2000

0 <= hi <= 106

0 <= ki < people.length

题目数据确保队列可以被重建

思考历程与知识点:  

如果按照k来从小到大排序,排完之后,会发现k的排列并不符合条件,身高也不符合条件,两个维度哪一个都没确定下来。

那么按照身高h来排序呢,身高一定是从大到小排(身高相同的话则k小的站前面),让高个子在前面。

此时我们可以确定一个维度了,就是身高,前面的节点一定都比本节点高

在按照身高从大到小排序后:

局部最优:优先按身高高的people的k来插入。插入操作过后的people满足队列属性

全局最优:最后都做完插入操作,整个队列满足题目队列属性

局部最优可推出全局最优,找不出反例,那就试试贪心。

题解:

class Solution {
public:
    // 身高从大到小排(身高相同k小的站前面)
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort (people.begin(), people.end(), cmp);
        list<vector<int>> que; // list底层是链表实现,插入效率比vector高的多
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1]; // 插入到下标为position的位置
            std::list<vector<int>>::iterator it = que.begin();
            while (position--) { // 寻找在插入位置
                it++;
            }
            que.insert(it, people[i]);
        }
        return vector<vector<int>>(que.begin(), que.end());
    }
};


相关文章
|
编解码 算法 搜索推荐
淘宝人生里的虚拟人像渲染技术
全程干货,淘宝人生里的虚拟人像是如何实现的?
淘宝人生里的虚拟人像渲染技术
|
域名解析 网络协议 应用服务中间件
Docker搭建Nginx并配置ssl证书
Docker搭建Nginx并配置ssl证书
3027 1
Docker搭建Nginx并配置ssl证书
|
9月前
|
自然语言处理 Go 开发工具
Go 1.25 新特性:正式支持 Git 仓库子目录作为 Go 模块
Go 1.25 正式支持 Git 子目录作为模块根路径,终结了长期限制——模块必须置于仓库根目录。现可在 monorepo 中按需在子目录(如 `/libs/math`)定义独立模块,通过扩展的 `go-import` 标签精准定位,兼顾工程规范与多语言协作,大幅提升大型项目组织灵活性。(239字)
533 1
|
10月前
|
人工智能 运维 数据可视化
告别繁琐巡检:AR智能眼镜打造工业&电力运维闭环体系|阿法龙XR云平台
本方案以AR眼镜为核心,融合蓝牙定位、AI识别与多模态感知技术,构建智能巡检体系。通过精准定位触发、AI实时识别仪表状态、数据自动上传与可视化管理,实现电力、化工、智能制造等场景下巡检效率提升60%、故障率降低40%,推动工业运维数字化、标准化、闭环化转型。(238字)
|
机器学习/深度学习 人工智能 分布式计算
【AI系统】混合并行
混合并行融合了数据并行、模型并行和流水线并行,旨在高效利用计算资源,尤其适合大规模深度学习模型训练。通过将模型和数据合理分配至多个设备,混合并行不仅提升了计算效率,还优化了内存使用,使得在有限的硬件条件下也能处理超大型模型。3D混合并行(DP+PP+TP)是最先进的形式,需至少8个GPU实现。此策略通过拓扑感知3D映射最大化计算效率,减少通信开销,是当前深度学习训练框架如Deepspeed和Colossal AI的核心技术之一。
1087 15
【AI系统】混合并行
|
搜索推荐 网络架构 UED
什么是超链接?
本文介绍超链接的基本概念及其在网络中的重要性。超链接作为Web的核心组成部分,由蒂姆·伯纳斯·李在1989年提出,与URL、HTTP共同构成Web的三大支柱。通过链接,用户能轻松从一个文档跳转至另一个文档。文章探讨了不同类型的链接,包括内部链接、外部链接与传入链接,并介绍了锚点链接的功能。此外,还强调了链接对于用户体验及搜索引擎优化(SEO)的重要性,以及如何合理构建链接以提升网站的可用性和搜索引擎排名。最后,提供了进一步学习资源,帮助读者深入了解URL结构与超链接的实际应用。
2395 3
|
消息中间件 数据采集 安全
Python教程:深入理解 Python multiprocessing.Queue
在 Python 编程中,多进程编程是利用计算机多核心资源的重要手段之一。然而,多进程之间的通信却是一个相对复杂的问题。在本文中,我们将深入探讨 Python 中的 multiprocessing.Queue 模块,它为多进程间的通信提供了便捷而高效的解决方案。
818 5
|
数据采集 安全 搜索推荐
更高性价比的住宅IP代理服务商SmartProxy
互联网的发展增加了对海外住宅IP的需求。它们为个人提供访问特定区域资源的能力,并为企业拓展国际市场提供支持。选择可靠的供应商至关重要; SmartProxy作为优质服务商,特点包括: - 覆盖200多个国家的真实住宅IP。 - 高匿性及无限带宽确保数据采集无忧。 - 支持多种协议并可定制独享IP。 - 自定义选项实现精准定位。 - 24/7技术支持保障使用体验。 静态住宅IP提供固定地址,适用于需稳定连接的场景。[了解更多](https://www.smartproxycn.com/?r-source=-8jaZawMss)并领取0.5G免费流量。