• 贪心算法练习day.4


    860.柠檬水找零

    链接:. - 力扣(LeetCode)

    题目描述:

    在柠檬水摊上,每一杯柠檬水的售价为 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找零,如果没有5直接返回假,如果客户支付20,我们可以10和5找零或者3个5找零,因为5更万能,5可以对20找零,还能对10找零,因此我们在找零时优先保留5面额的钞票(局部最优),最后完成整个账号的找零(全局最优)

    代码实现:

    1. bool lemonadeChange(int* bills, int billsSize) {
    2. int five = 0, ten = 0;
    3. for(int i = 0; i < billsSize ; i++)
    4. {
    5. if(bills[i] == 5)
    6. five++;
    7. else if(bills[i] == 10)
    8. {
    9. if(five)
    10. {
    11. ten++;
    12. five--;
    13. }
    14. else
    15. return false;
    16. }
    17. else
    18. {
    19. if(ten && five)
    20. {
    21. ten--;
    22. five--;
    23. }
    24. else if(five >= 3)
    25. {
    26. five -= 3;
    27. }
    28. else
    29. {
    30. return false;
    31. }
    32. }
    33. }
    34. return true;
    35. }

    406.根据身高重建队列

    链接:. - 力扣(LeetCode)

    题目描述:

    假设有打乱顺序的一群人站成一个队列,数组 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
    • 题目数据确保队列可以被重建

    思路:

    我们可以根据题目的例子进行分析

    该题分为h和k两个维度,因为我们要先考虑一个维度再考虑另外一个维度,h代表这个人的身高,而k代表这个人前面有多少人,我们可以先对k进行排列,k相同时较矮的在前,排序之后我们会发现结果会比较乱,因此可以排除这个方法

    我们可以再尝试从h的维度去排序,即由高到矮的顺序,当h相同时,则k大的在后边,这样就得到了我们初步排序的结果,如下所示

    接下来我们可以按照k的大小,再去将不符合条件的位置进行修改,可得出正确结果

    因为我们根据身高维度确定好大小之后,我们就可以保证每一个人的前面的人一定会比它高,因此我们就可以放心的根据k值去插入到对应的队列,来满足题目要求

    代码实现:

    1. // 比较函数,用于qsort排序,排序规则为按照身高降序排序,若身高相同则按照前面比他高的人数升序排序
    2. int cmp(const void *p1, const void *p2) {
    3. int *pp1 = *(int**)p1; // 获取第一个人的信息
    4. int *pp2 = *(int**)p2; // 获取第二个人的信息
    5. // 如果两个人的身高相同,则按照前面比他高的人数升序排序
    6. // 否则,按照身高降序排序
    7. return pp1[0] == pp2[0] ? pp1[1] - pp2[1] : pp2[0] - pp1[0];
    8. }
    9. // 将数组中的元素向后移动一位,从end到start
    10. void moveBack(int **people, int peopleSize, int start, int end) {
    11. int i;
    12. for(i = end; i > start; i--) {
    13. people[i] = people[i-1]; // 将当前位置的元素设为前一个位置的元素
    14. }
    15. }
    16. // 重建队列函数
    17. int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes){
    18. int i;
    19. qsort(people, peopleSize, sizeof(int*), cmp); // 根据身高降序排序
    20. // 根据前面比他高的人数,将每个人插入到合适的位置
    21. for(i = 0; i < peopleSize; ++i) {
    22. int position = people[i][1]; // 获取当前人应该插入的位置
    23. int *temp = people[i]; // 临时存储当前人的信息
    24. moveBack(people, peopleSize, position, i); // 将当前人插入到合适的位置
    25. people[position] = temp; // 将当前人的信息插入到对应位置
    26. }
    27. // 设置返回值大小
    28. *returnSize = peopleSize;
    29. // 分配返回列的大小
    30. *returnColumnSizes = (int*)malloc(sizeof(int) * peopleSize);
    31. // 设置每列的大小为2
    32. for(i = 0; i < peopleSize; ++i) {
    33. (*returnColumnSizes)[i] = 2;
    34. }
    35. // 返回重建的队列
    36. return people;
    37. }

    452.用最少数量的箭引爆气球

    链接:. - 力扣(LeetCode)

    题目描述:

    有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

    一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstartxend, 且满足  xstart ≤ x ≤ xend,则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后,可以无限地前进。

    给你一个数组 points返回引爆所有气球所必须射出的 最小 弓箭数 

    示例 1:

    输入:points = [[10,16],[2,8],[1,6],[7,12]]
    输出:2
    解释:气球可以用2支箭来爆破:
    -在x = 6处射出箭,击破气球[2,8]和[1,6]。
    -在x = 11处发射箭,击破气球[10,16]和[7,12]。

    示例 2:

    输入:points = [[1,2],[3,4],[5,6],[7,8]]
    输出:4
    解释:每个气球需要射出一支箭,总共需要4支箭。

    示例 3:

    输入:points = [[1,2],[2,3],[3,4],[4,5]]
    输出:2
    解释:气球可以用2支箭来爆破:
    - 在x = 2处发射箭,击破气球[1,2]和[2,3]。
    - 在x = 4处射出箭,击破气球[3,4]和[4,5]。

    提示:

    • 1 <= points.length <= 105
    • points[i].length == 2
    • -231 <= xstart < xend <= 231 - 1

    贪心思路:

    我们尽量让重叠的气球在一起,这样只需要一个弓箭就可以,这就是局部最优,全局最优就是让所有的气球能够使用最少的弓箭,因为题目给我们的气球是没有顺序的,我们可以先进行快速排序,统一按照左边界排序或者右边界排序都可以,因为排序之后的气球重叠部分会尽量相邻在一起,这样就便于我们处理,如果后一个气球的左边界小于它前一个气球的右边界,不重叠,我们需要多加一个弓箭,而对于重叠的情况,我们需要记录重叠的两个气球的最小右边界,这样就可以判断和其他的气球是否有重叠的情况

    代码如下:

    1. int cmp(const void* a, const void* b) {
    2. // 按照每个点的起始位置进行比较
    3. return (*((int**)a))[0] > (*((int**)b))[0];
    4. }
    5. int findMinArrowShots(int** points, int pointsSize, int* pointsColSize) {
    6. // 使用qsort对points数组进行排序,按照每个点的起始位置
    7. qsort(points, pointsSize, sizeof(points[0]), cmp);
    8. // 初始化箭的数量为1,至少需要一支箭
    9. int count = 1;
    10. // 遍历points数组
    11. for (int i = 1; i < pointsSize; i++) {
    12. // 若当前点的起始位置大于前一个点的结束位置,表示不重叠,增加箭的数量
    13. if (points[i][0] > points[i - 1][1])
    14. count++;
    15. else
    16. // 若当前点的起始位置小于等于前一个点的结束位置,更新当前点的结束位置为两点中的较小值
    17. points[i][1] = points[i][1] > points[i - 1][1] ? points[i - 1][1] : points[i][1];
    18. }
    19. // 返回最终箭的数量
    20. return count;
    21. }

  • 相关阅读:
    python 2018全国自学考试第5章 第21题 成功!!!左右金字塔建模加平方结果
    SpringBoot 测试实践 - 1:常用的工具
    性能提升3倍之路:记Guava cache带来的GC问题
    图解设计模式:身份认证场景的应用
    web前端期末大作业实例 (1500套) 集合
    解锁编程潜能:探索亚马逊CodeWhisperer,打造编程世界的声音引导者
    深入理解Windows句柄
    R Markdown 格式
    元宇宙构建基石:三维重建技术
    报表开发工具DevExpress Reporting v23.2 - 增强PDF导出、多平台打印等
  • 原文地址:https://blog.csdn.net/u011381222/article/details/138135632