贪心算法day（1）

1.将数组和减半的最少操作次数

链接：. - 力扣（LeetCode）

思路：创建大跟堆将最大的数进行减半

注意点：double t = queue.poll()会将queue队列数字减少一个后再除以2，queue.offer(queue.poll(）/ 2)

class Solution {public int halveArray(int[] nums) {//如何建立大根堆??PriorityQueue<Double> queue = new PriorityQueue<>((a,b)->b.compareTo(a));double sum = 0.0;int count = 0;for(int x:nums){queue.offer((double) x);sum+=x;}sum /= 2.0;while(sum > 0){double t = queue.poll() / 2.0;sum -= t;count++;queue.offer(t);}return count;}
}

2.最大数

链接：. - 力扣（LeetCode）

主要问题：如何将数字改为字符串以及排序 

class Solution {public static String largestNumber(int[] nums) {//把数字转化成字符串 把两个字符串拼接在一起比较字符串的字典序//ab > ba a在前b在后 ab < ba b在前a在后//转化字符串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 ret = new StringBuffer();for(String x: str){ret.append(x);}if(ret.charAt(0) == '0'){return "0";}return ret.toString();}
}

 3.摆动序列

链接：. - 力扣（LeetCode）

思路：把数子画成波峰波谷 左右端点以及波峰波谷就是我们要找的最大摆序列

问题：如何表示波峰波谷以及什么情况下添加最大摆动序列

class Solution {public int wiggleMaxLength(int[] nums) {int n = nums.length;if(n < 2){return n;}int left = 0;int count = 0;for (int i = 0; i < n - 1; i++) {int right = nums[i+1] - nums[i];if(right == 0) continue;if(left * right <= 0){count++;}left = right;}return count + 1;}
}