算法奇妙屋(三十四)-贪心算法学习之路 1

Ne0inhk

— 4 min read
算法奇妙屋(三十四)-贪心算法学习之路 1

文章目录

一. 力扣 860. 柠檬水找零

1. 题目解析

1. 题目翻译成人话就是: 每名顾客只能按bills顺序买你的柠檬水, 给的钱数也是按顺序, 柠檬水固定5元, 要求就是给每名顾客都能正确找零
2. 注意点①: 一开始你没有任何钱, 所以如果顾客一上来给的不是5元的面额, 直接返回false
3. 注意点②: 先考虑当前顾客能否正常找零, 不能的话直接返回false, 不继续考虑后面
4. 注意点③: 顾客给你的面额只有三种, 5, 10, 20

2. 算法原理

在这里插入图片描述

3. 代码

classSolution{int[] change;publicbooleanlemonadeChange(int[] bills){if(bills[0]!=5){returnfalse;} change =newint[2];for(int i =0; i < bills.length; i++){if(bills[i]==5){ change[0]++;}elseif(bills[i]==10){if(change[0]!=0){ change[0]--; change[1]++;}else{returnfalse;}}else{if(change[0]!=0&& change[1]!=0){ change[0]--; change[1]--;}elseif(change[0]>=3){ change[0]-=3;}else{returnfalse;}}}returntrue;}}

二. 力扣 2208. 将数组和减半的最少操作次数

1. 题目解析

这道题的题意就是题目, 这里图解简单重复下过程

2. 算法原理

根据题目解析我们可以发现两个关键点:
1. 我们每次都需要找到最大值, 用最大值➗️2, 这样就可以让总和减少的最多
2. 使用大根堆, 将所有元素丢入堆中, 每次取出堆顶元素(最大值)

3. 代码

classSolution{publicinthalveArray(int[] nums){PriorityQueue<Double> q =newPriorityQueue<>((a, b)-> b.compareTo(a));double sum =0;for(int x : nums){ sum += x; q.offer((double)x);}int ret =0; sum /=2.0;while(sum >0){double t = q.poll()/2.0; sum -= t; q.offer(t); ret++;}return ret;}}

三. 力扣 179. 最大数

1. 题目解析

**结合示例这道题很好理解, 返回拼接的最大整数的字符串形式
**

在这里插入图片描述

2. 算法原理

做这道题, 我们可以通过类比数据结构5-七大基于比较的常见排序算法中的排序算法, 先确立排序规则, 将数组中的元素排好序👇
1. 排序规则: 假设数组nums = [a, b, c]
① 将最近的两个数a 与 b, 进行拼接, 组成ab与ba
② ab > ba, a就排在前面, b排在后面
③ 反之, b在前, a在后, 之后以此类推进行排序
2. 注意点:
① 当最后的结果nums的第一个元素为0时, 意味着给定的所有元素都是0, 所以直接返回字符串 “0” 即可
② 进行拼接并比较时, 我们可以先将整个nums转化为字符串数组, 再拼接比较每个位置的字典序即可

3. 代码

classSolution{publicStringlargestNumber(int[] nums){int n = nums.length;// 将nums都变为字符串String[] s =newString[n];for(int i =0; i < n; i++){ s[i]=""+ nums[i];}// 排序Arrays.sort(s,(a, b)->{return(b + a).compareTo((a + b));});StringBuilder ret =newStringBuilder();for(String str : s){ ret.append(str);}if(ret.charAt(0)=='0')return"0";return ret.toString();}}
Could not load content