7月21日，贪心练习

大家好呀，今天带来一些贪心算法的应用解题、

一，柠檬水找零

. - 力扣（LeetCode）

解析：

本题的贪心体现在对于20美元的处理上，我们总是优先把功能较少的10元作为找零，这样可以让5元用处更大

Java版

class Solution {public boolean lemonadeChange(int[] bills) {int M5=0, M10=0;for (int i = 0; i < bills.length; i++) {if (bills[i] == 5) {M5++;}if (bills[i] == 10) {if (M5 == 0) {return false;}M5--;M10++;}if (bills[i] == 20) {if (M10 > 0 && M5 > 0) {M10--;M5--;} else if (M5 >= 3) {M5 -= 3;} else {return false;}}}return true;}
}

二，将数组和减半的最小次数

. - 力扣（LeetCode）

解析：

思路非常简单，只需每次找出数组最大的数减半即可，但是需要注意不能采用每次遍历的方法来找最大值，会超时，可以采用堆的方法，构建一个大堆即可

Java版

class Solution {public int halveArray(int[] nums) {PriorityQueue<Double> q = new PriorityQueue<>(Comparator.reverseOrder());double sum = 0;for (double num : nums) {sum += num;q.offer(num);}sum/=2.0;int count = 0;while (sum>0) {Double val = q.poll();double t = val / 2;sum -= t;q.offer(t);count++;}return count;}
}

三，最大数

. - 力扣（LeetCode）

这题很像排序问题，但是需要转成字符串比较排序，本质还是确定元素先后顺序，举个例子，加入把a和b分别看作一个数，那么无非三种情况

1，a+b>b+a  2 ,a+b=b+a  3 ,a+b<b+a, 我们只需要把这个比较规则传给排序函数，贪心也体现在比较规则上，需要特别注意全是0的情况

Java

class Solution {public String largestNumber(int[] nums) {int n=nums.length;String[] str=new String[n];for(int i=0;i<n;i++){str[i]=""+nums[i];}Arrays.sort(str,(a,b)->{return (b+a).compareTo(a+b);});StringBuffer s=new StringBuffer();for(int i=0;i<n;i++){s.append(str[i]);}if(s.charAt(0)=='0')return "0";return s.toString();}
}

好啦，本期就到这里，谢谢大家