贪心算法概念:
1)最自然智慧的算法
2)用一种局部最功利的标准,总是做出在当前看来是最好的选择
3)难点在于证明局部最功利的标准可以得到全局最优解
4)对于贪心算法的学习主要以增加阅历和经验为主
package class13;import java.util.Arrays;
import java.util.TreeSet;/*** 给定一个由字符串组成的数组strs,* 必须把所有的字符串拼接起来,* 返回所有可能的拼接结果中,字典序最小的结果** 贪心算法* 1)最自然智慧的算法** 2)用一种局部最功利的标准,总是做出在当前看来是最好的选择** 3)难点在于证明局部最功利的标准可以得到全局最优解** 4)对于贪心算法的学习主要以增加阅历和经验为主** 贪心算法求解的标准过程* 1,分析业务** 2,根据业务逻辑找到不同的贪心策略** 3,对于能举出反例的策略直接跳过,不能举出反例的策略要证明有效性** 这往往是特别困难的,要求数学能力很高且不具有统一的技巧性** 贪心算法的解题套路* 1,实现一个不依靠贪心策略的解法X,可以用最暴力的尝试** 2,脑补出贪心策略A、贪心策略B、贪心策略C...** 3,用解法X和对数器,用实验的方式得知哪个贪心策略正确** 4,不要去纠结贪心策略的证明*/public class LowsetLexicography {//暴力解法 递归形式 将每个字符作为首部,依次拼接全部情况的结果集,存放到treeset有序集合,取出首元素就是最小的字典序排序拼接方式public static String lowestString1(String[] strs){if(strs == null || strs.length == 0){//null 或者长度0空数组则直接返回空字符串return "";}//有序表保存全部排序情况,返回首元素就是最小排序TreeSet ans = process(strs);return ans.size() == 0 ? "":ans.first();}//递归思路,从左到右依次取字符串,然后递归 排除当前字符串的下个字符串数组,将其追加在当前字符串后public static TreeSet process(String[] strs){//定义一个有序表结构保存结果集,用于返回TreeSet ans = new TreeSet<>();//当字符串减少到0的时候,就直接返回空字符串if(strs.length == 0){//注意要加空字符,返回给上层调用才会有空异常ans.add("");return ans;}//依次遍历每个字符串for(int i = 0; i < strs.length; i++){//取当前遍历到的字符串拼接在首部String first = strs[i];//排除当前字符串 再将数组进行下层递归,直到空的时候,开始向上返回TreeSet nexts = process(removeIndexString(strs,i));//向上依次拼接给当前节点字符后面for(String next : nexts){ans.add(first + next);}}//递归完成,全部排序返回,最后主程序取有序表的首元素,就是最小字典序return ans;}// {"abc", "cks", "bct"}// 0 1 2// removeIndexString(arr , 1) -> {"abc", "bct"}//每次移除当前节点元素,返回剩下的字符串数组集public static String[] removeIndexString(String[] strs, int index){//定义新数组集合以及索引String[] ans = new String[strs.length-1];int ans_index = 0;for(int i = 0;i < strs.length;i++){if(i != index){//遍历原数组,排除index索引,不等于的则赋值到新数组ans[ans_index++] = strs[i];}}return ans;}//贪心思想//字典序排序要最小,已知字典序的排序 "a" < "b" , "b" < "c" 存在传递性规律 所以"a" < "c"//而字符拼接后也一样 排序是具有传递性的://如果字符串a拼接字符串b < 字符串b拼接字符串a 那么就返回 前者,即a放b的前面 ;否则返回后者//按照这个排序定义比较器排序后,就按序拼接就是最小的://因为假设每个字符串交换到前面,它必定是大于未交换前的字符串拼接的public static String lowestString2(String[] strs){if(strs == null || strs.length == 0){return "";}//lambda表达式自定义比较器 参数 a b, 如果字符串数组 字符串a+b < b+a compareTo返回负数,a排前面 返回正数 b排前面Arrays.sort(strs,(a,b)->(a+b).compareTo(b+a));StringBuilder ans = new StringBuilder();for(String str:strs){ans.append(str);}return ans.toString();}// for testpublic static String generateRandomString(int strLen) {char[] ans = new char[(int) (Math.random() * strLen) + 1];for (int i = 0; i < ans.length; i++) {int value = (int) (Math.random() * 5);ans[i] = (Math.random() <= 0.5) ? (char) (65 + value) : (char) (97 + value);}return String.valueOf(ans);}// for testpublic static String[] generateRandomStringArray(int arrLen, int strLen) {String[] ans = new String[(int) (Math.random() * arrLen) + 1];for (int i = 0; i < ans.length; i++) {ans[i] = generateRandomString(strLen);}return ans;}// for testpublic static String[] copyStringArray(String[] arr) {String[] ans = new String[arr.length];for (int i = 0; i < ans.length; i++) {ans[i] = String.valueOf(arr[i]);}return ans;}public static void main(String[] args) {int arrLen = 6;int strLen = 5;int testTimes = 10000;System.out.println("test begin");for (int i = 0; i < testTimes; i++) {String[] arr1 = generateRandomStringArray(arrLen, strLen);String[] arr2 = copyStringArray(arr1);if (!lowestString1(arr1).equals(lowestString2(arr2))) {for (String str : arr1) {System.out.print(str + ",");}System.out.println();System.out.println("Oops!");}}System.out.println("finish!");}
}
1,分析业务
2,根据业务逻辑找到不同的贪心策略
3,对于能举出反例的策略直接跳过,不能举出反例的策略要证明有效性
这往往是特别困难的,要求数学能力很高且不具有统一的技巧性
1,实现一个不依靠贪心策略的解法X,可以用最暴力的尝试
2,脑补出贪心策略A、贪心策略B、贪心策略C...
3,用解法X和对数器,用实验的方式得知哪个贪心策略正确
4,不要去纠结贪心策略的证明
package class14;import java.util.HashSet;/*** 给定一个字符串str,只由‘X’和‘.’两种字符构成。* ‘X’表示墙,不能放灯,也不需要点亮* ‘.’表示居民点,可以放灯,需要点亮* 如果灯放在i位置,可以让i-1,i和i+1三个位置被点亮* 返回如果点亮str中所有需要点亮的位置,至少需要几盏灯** 贪心思想:根据题意 .是要被照亮。 而灯可以照亮三个. 求至少,那么就根据这个最大照亮三个点的情况来贪心 一个灯贪心照亮三个.*/
public class Light {public static int minLight1(String road) {if (road == null || road.length() == 0) {return 0;}return process(road.toCharArray(), 0, new HashSet<>());}// str[index....]位置,自由选择放灯还是不放灯// str[0..index-1]位置呢?已经做完决定了,那些放了灯的位置,存在lights里// 要求选出能照亮所有.的方案,并且在这些有效的方案中,返回最少需要几个灯public static int process(char[] str, int index, HashSet lights) {if (index == str.length) { // 结束的时候for (int i = 0; i < str.length; i++) {if (str[i] != 'X') { // 当前位置是点的话if (!lights.contains(i - 1) && !lights.contains(i) && !lights.contains(i + 1)) {return Integer.MAX_VALUE;}}}return lights.size();} else { // str还没结束// i X .int no = process(str, index + 1, lights);int yes = Integer.MAX_VALUE;if (str[index] == '.') {lights.add(index);yes = process(str, index + 1, lights);lights.remove(index);}return Math.min(no, yes);}}//贪心思想public static int minLight2(String road) {//转换成字符数组 定义索引 与结果值char[] chars = road.toCharArray();int i = 0;int ans = 0;//遍历字符数组while(i < chars.length){//遇到X,不需要照亮,索引往下if(chars[i] == 'X'){i++;}else{//遇到. 进来先灯+1ans++;//如果i+1 是超过边界 也就是i 是最后一个索引的时候 就可以直接退出了。即使当前i是. 需要照亮,我们已经在前面先+1灯了if(i + 1 == chars.length){break;}else {// 还没到最后边界 那么分析几种情况://1. 下个字符 i+1 如果是X 那么灯+1,并且索引跳过X,来到i+2//2. 下个字符 i+1 如果是. 那么灯也要+1 这次索引来到i+3 因为不管i+3 是X还是. 都不需要去判断,因为灯可以照亮3个.//这里不管那么种情况,都是需要+1灯,所以统一放前面+1 这么负责索引的走向if(chars[i+1] == 'X'){i = i+2;}else {i = i+3;}}}}//最后返回ansreturn ans;}// 更简洁的解法// 两个X之间,数一下.的数量,然后除以3,向上取整// 把灯数累加public static int minLight3(String road) {char[] str = road.toCharArray();int cur = 0;int light = 0;for (char c : str) {if (c == 'X') {light += (cur + 2) / 3;cur = 0;} else {cur++;}}light += (cur + 2) / 3;return light;}// for testpublic static String randomString(int len) {char[] res = new char[(int) (Math.random() * len) + 1];for (int i = 0; i < res.length; i++) {res[i] = Math.random() < 0.5 ? 'X' : '.';}return String.valueOf(res);}public static void main(String[] args) {int len = 20;int testTime = 100000;for (int i = 0; i < testTime; i++) {String test = randomString(len);int ans1 = minLight1(test);int ans2 = minLight2(test);int ans3 = minLight3(test);if (ans1 != ans2 || ans1 != ans3) {System.out.println("oops!");}}System.out.println("finish!");}
}
一块金条切成两半,是需要花费和长度数值一样的铜板的。
比如长度为20的金条,不管怎么切,都要花费20个铜板。一群人想整分整块金条,怎么分最省铜板?
例如,给定数组{10,20,30},代表一共三个人,整块金条长度为60,金条要分成10,20,30三个部分。
如果先把长度60的金条分成10和50,花费60;再把长度50的金条分成20和30,花费50;一共花费110铜板。
但如果先把长度60的金条分成30和30,花费60;再把长度30金条分成10和20,花费30;一共花费90铜板。
输入一个数组,返回分割的最小代价。
package class14;import java.util.PriorityQueue;/*** 一块金条切成两半,是需要花费和长度数值一样的铜板的。* 比如长度为20的金条,不管怎么切,都要花费20个铜板。 一群人想整分整块金条,怎么分最省铜板?** 例如,给定数组{10,20,30},代表一共三个人,整块金条长度为60,金条要分成10,20,30三个部分。** 如果先把长度60的金条分成10和50,花费60; 再把长度50的金条分成20和30,花费50;一共花费110铜板。* 但如果先把长度60的金条分成30和30,花费60;再把长度30金条分成10和20, 花费30;一共花费90铜板。* 输入一个数组,返回分割的最小代价。*/public class LessMoneySplitGold {// 纯暴力!public static int lessMoney1(int[] arr) {if (arr == null || arr.length == 0) {return 0;}return process(arr, 0);}// 等待合并的数都在arr里,pre之前的合并行为产生了多少总代价// arr中只剩一个数字的时候,停止合并,返回最小的总代价public static int process(int[] arr, int pre) {if (arr.length == 1) {return pre;}int ans = Integer.MAX_VALUE;for (int i = 0; i < arr.length; i++) {for (int j = i + 1; j < arr.length; j++) {ans = Math.min(ans, process(copyAndMergeTwo(arr, i, j), pre + arr[i] + arr[j]));}}return ans;}public static int[] copyAndMergeTwo(int[] arr, int i, int j) {int[] ans = new int[arr.length - 1];int ansi = 0;for (int arri = 0; arri < arr.length; arri++) {if (arri != i && arri != j) {ans[ansi++] = arr[arri];}}ans[ansi] = arr[i] + arr[j];return ans;}//贪心思想:将每个数放到小根堆,依次取堆最小的两段合并,合并值就为当前的代价,再将合并的值添加回堆中进行上一次的合并//这个思路是反向的做法,相当于已经切好的段,从最下面开始两两合并直到最后我们堆合并成只有一个数,也就是整个数组的和时就//得到了这个最小代价public static int lessMoney2(int[] arr){//定义小根堆,把数组存放进去PriorityQueue heap = new PriorityQueue<>();for(int num:arr){heap.add(num);}//定义分割总代价值与int sum = 0;//遍历每段数值,直到合并到只剩一个 也就是总和就退出while(heap.size() > 1){//合并最小两段,并且这两段的代价按照题意就是两端和,累加到sumint merge = heap.poll() + heap.poll();sum += merge;//然后需要把这次合并的段加回堆中,继续给上层合并heap.add(merge);}//最后返回sum就能得到最小代价分割值return sum;}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) (Math.random() * (maxValue + 1));}return arr;}public static void main(String[] args) {int testTime = 100000;int maxSize = 6;int maxValue = 1000;for (int i = 0; i < testTime; i++) {int[] arr = generateRandomArray(maxSize, maxValue);if (lessMoney1(arr) != lessMoney2(arr)) {System.out.println("Oops!");}}System.out.println("finish!");}}
package class14;import java.util.Arrays;
import java.util.Comparator;/*** 一些项目要占用一个会议室宣讲,会议室不能同时容纳两个项目的宣讲。* 给你每一个项目开始的时间和结束的时间* 你来安排宣讲的日程,要求会议室进行的宣讲的场次最多。* 返回最多的宣讲场次。** [1,3],[2,5],[3,6]比如三个会议 起始点 同步安排会议最多场次就是安排第一和第三场* 两者时间不交集*/public class BestArrange {//会议类结构public static class Program{public int start;public int end;public Program(int s,int e){start = s;end = e;}}//贪心思想 将会议按照会议结束时间升序排序 早结束的排前面,然后就依次开始从头遍历匹配,//当前会议如果开始时间大于等于我们当前的时间,一开始时间初始值0, 那么就安排这个会议,并且//当前时间来到这个会议的结束时间,再往下个会议看,添加下个会议开始时间是大于等于当前时间的,//直到结束 就可以得到安排最多场次会议public static int bestArrange2(Program[] programs){//按照会议的结束时间 升序排序,先结束的会议放到数组前面Arrays.sort(programs, (o1, o2) -> o1.end - o2.end);//定义能安排多少场次会议, 当前时间节点 初始为0int ans = 0;int timeNow = 0;for(Program pro:programs){//遍历排好序的会议,如果当前会议开始时间大于等于 当前时间,那么就可以安排会议,并将当前时间赋值为该会议室的结束时间if(pro.start >= timeNow){ans++;timeNow = pro.end;}}return ans;}// 暴力!所有情况都尝试!public static int bestArrange1(Program[] programs) {if (programs == null || programs.length == 0) {return 0;}return process(programs, 0, 0);}// 还剩下的会议都放在programs里// done之前已经安排了多少会议的数量// timeLine目前来到的时间点是什么// 目前来到timeLine的时间点,已经安排了done多的会议,剩下的会议programs可以自由安排// 返回能安排的最多会议数量public static int process(Program[] programs, int done, int timeLine) {if (programs.length == 0) {return done;}// 还剩下会议int max = done;// 当前安排的会议是什么会,每一个都枚举for (int i = 0; i < programs.length; i++) {if (programs[i].start >= timeLine) {Program[] next = copyButExcept(programs, i);max = Math.max(max, process(next, done + 1, programs[i].end));}}return max;}public static Program[] copyButExcept(Program[] programs, int i) {Program[] ans = new Program[programs.length - 1];int index = 0;for (int k = 0; k < programs.length; k++) {if (k != i) {ans[index++] = programs[k];}}return ans;}// for testpublic static Program[] generatePrograms(int programSize, int timeMax) {Program[] ans = new Program[(int) (Math.random() * (programSize + 1))];for (int i = 0; i < ans.length; i++) {int r1 = (int) (Math.random() * (timeMax + 1));int r2 = (int) (Math.random() * (timeMax + 1));if (r1 == r2) {ans[i] = new Program(r1, r1 + 1);} else {ans[i] = new Program(Math.min(r1, r2), Math.max(r1, r2));}}return ans;}public static void main(String[] args) {int programSize = 12;int timeMax = 20;int timeTimes = 1000000;for (int i = 0; i < timeTimes; i++) {Program[] programs = generatePrograms(programSize, timeMax);if (bestArrange1(programs) != bestArrange2(programs)) {System.out.println("Oops!");}}System.out.println("finish!");}}
package class14;import java.util.PriorityQueue;/*** 输入: 正数数组costs、正数数组profits、正数K、正数M* costs[i]表示i号项目的花费* profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)* K表示你只能串行的最多做k个项目* W表示你初始的资金* 说明: 每做完一个项目,马上获得的收益,可以支持你去做下一个项目。不能并行的做项目。* 输出:你最后获得的最大钱数。* * 贪心思想:* 将每个项目的cost profit 都存放到一个类中 然后定义小根堆 大根堆 小根堆按cost排序 大根堆按profit排序* 然后从小根堆判断 取出来就是最小花费项目 与初始资金W比较 小的就可以做,就将其出堆,然后入大根堆* 最后我们判断入大根堆多个中的第一个 就是利益最大的 就做那个项目,同步刷新M 直到我们项目做完,或者我们资金不够做 退出*/
public class IPO {// 最多K个项目// W是初始资金// Profits[] Capital[] 一定等长// 返回最终最大的资金public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {//定义小根堆 按花费排序 大根堆 按利润排序PriorityQueue minCostsHeap = new PriorityQueue<>((a, b) -> (a.costs - b.costs));PriorityQueue maxProfitsHeap = new PriorityQueue<>((a, b) -> (b.profits - a.profits));//遍历数组 利润和花费数组长度都是一样的 将利润 花费项目创建对象并入小根堆for (int i = 0; i < Profits.length; i++) {minCostsHeap.add(new Program(Profits[i], Capital[i]));}//开始判断能做多少项目使得最大Mfor (int i = 0; i < K; i++) {//当小根堆项目非空 并且资金W不小于小根堆顶项目的消费值 循环都入到大根堆,表示这些项目是可以做的while (!minCostsHeap.isEmpty() && minCostsHeap.peek().costs <= W){maxProfitsHeap.add(minCostsHeap.poll());}//这里需要提前判断 是否是存在能做的项目 假如costs 远大于当前W 那么就无法做,到不了K个项目 需要判空提前退出返回资金值if(maxProfitsHeap.isEmpty()){return W;}//入大根堆后,取堆顶项目做,利益最大,将其出堆 并累计利润给WW += maxProfitsHeap.poll().profits;}return W;}//定义一个类 存放项目的花费和利润public static class Program {public int profits; //利润public int costs; //花销public Program(int p, int c) {profits = p;costs = c;}}}
下一篇:【嵌入式开发】iperf