[Java 算法] 贪心(1)

练习一 : 柠檬水找零860. 柠檬水找零 - 力扣LeetCodeclass Solution { public boolean lemonadeChange(int[] bills) { if(bills[0]5){ return false; } int five 0,ten 0; for(int i 0;ibills.length;i){ if(bills[i] 5){ five; } else if(bills[i] 10){ ten; five--; if(five0||ten0){ return false; } } else if(bills[i] 20){ if(ten1five1){ ten--; five--; } else{ five-3; } if(five0||ten0){ return false; } } } return true; } }贪心策略 : 优先用大面额 , 保留小面额万能钱5 : 不用找零 , 直接收下10 : 找 5 元 , 并且收下20 : 找总共 15 元 , 不用收下 ; 找 15 元时 , 优先用 10 块钱找零 , 5 块钱可以留着给 10 块找零练习二 : 将数组和肩膀的最小操作次数2208. 将数组和减半的最少操作次数 - 力扣LeetCodeclass Solution { public int halveArray(int[] nums) { PriorityQueueDouble maxHeap new PriorityQueueDouble((a,b) - b.compareTo(a)); double sum 0; for(int x:nums){ maxHeap.offer((double)x); sumx; } int count 0; double k sum/2; while(sumk){ double t maxHeap.poll(); t t/2; sum-t; count; maxHeap.offer(t); } return count; } }贪心策略 : 每次都选最大的数 , 将它减半通过大根堆找到最大的元素 , 减半再放入大根堆 , 同时修改数组和 , 循环往复 , 便可找到最小的操作次数练习三 : 最大数179. 最大数 - 力扣LeetCodeclass Solution { public String largestNumber(int[] nums) { int n nums.length; String[] strs new String[n]; for(int i 0;in;i){ strs[i] nums[i]; } Arrays.sort(strs,(a,b)-(ba).compareTo(ab)); StringBuffer sbf new StringBuffer(); for(String s:strs){ sbf.append(s); } if(sbf.charAt(0) 0){ return 0; } return sbf.toString(); } }贪心策略 : 让 拼接结果更大 的组合排在前面代码细节 :① 整型转字符串 : strs[i] nums[i]; 在整型的基础上加一个空串②Arrays.sort(strs,(a,b)-(ba).compareTo(ab));冒泡排序 , 谁拼起来更大 , 谁放在前面③ 用 StringBuffer 来拼接 : 由于 String 类型为不可变类型 , 每次拼接都需要创建新的对象 , 浪费内存空间④ 判断特殊情况 : [0,0] : 拼接为 00 ; 直接返回 0 , 而非 00