深圳市建设局网站张局,关于网站建设的一些事,网站建设宝典,河北省和城乡住房建设厅网站首页大家好呀#xff0c;今天带来一些贪心算法的应用解题、
一#xff0c;柠檬水找零
. - 力扣#xff08;LeetCode#xff09; 解析#xff1a;
本题的贪心体现在对于20美元的处理上#xff0c;我们总是优先把功能较少的10元作为找零#xff0c;这样可以让5元用处更大
…大家好呀今天带来一些贪心算法的应用解题、
一柠檬水找零
. - 力扣LeetCode 解析
本题的贪心体现在对于20美元的处理上我们总是优先把功能较少的10元作为找零这样可以让5元用处更大
Java版
class Solution {public boolean lemonadeChange(int[] bills) {int M50, M100;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) {PriorityQueueDouble q new PriorityQueue(Comparator.reverseOrder());double sum 0;for (double num : nums) {sum num;q.offer(num);}sum/2.0;int count 0;while (sum0) {Double val q.poll();double t val / 2;sum - t;q.offer(t);count;}return count;}
}
三最大数
. - 力扣LeetCode 这题很像排序问题但是需要转成字符串比较排序本质还是确定元素先后顺序举个例子加入把a和b分别看作一个数那么无非三种情况
1abba 2 ,abba 3 ,abba, 我们只需要把这个比较规则传给排序函数贪心也体现在比较规则上需要特别注意全是0的情况
Java
class Solution {public String largestNumber(int[] nums) {int nnums.length;String[] strnew String[n];for(int i0;in;i){str[i]nums[i];}Arrays.sort(str,(a,b)-{return (ba).compareTo(ab);});StringBuffer snew StringBuffer();for(int i0;in;i){s.append(str[i]);}if(s.charAt(0)0)return 0;return s.toString();}
}
好啦本期就到这里谢谢大家
