外贸做的好的网站,野花香视频在线观看免费高清版,网站建设教程ppt, 天堂8资源中文在线一、贪心算法概念贪心算法概念#xff1a;1#xff09;最自然智慧的算法2#xff09;用一种局部最功利的标准#xff0c;总是做出在当前看来是最好的选择3#xff09;难点在于证明局部最功利的标准可以得到全局最优解4#xff09;对于贪心算法的学习主要以增加阅历和经验…一、贪心算法概念贪心算法概念1最自然智慧的算法2用一种局部最功利的标准总是做出在当前看来是最好的选择3难点在于证明局部最功利的标准可以得到全局最优解4对于贪心算法的学习主要以增加阅历和经验为主二、给定一个由字符串组成的数组strs必须把所有的字符串拼接起来返回所有可能的拼接结果中字典序最小的结果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 ;}//有序表保存全部排序情况返回首元素就是最小排序TreeSetString ans process(strs);return ans.size() 0 ? :ans.first();}//递归思路从左到右依次取字符串然后递归 排除当前字符串的下个字符串数组将其追加在当前字符串后public static TreeSetString process(String[] strs){//定义一个有序表结构保存结果集用于返回TreeSetString ans new TreeSet();//当字符串减少到0的时候就直接返回空字符串if(strs.length 0){//注意要加空字符返回给上层调用才会有空异常ans.add();return ans;}//依次遍历每个字符串for(int i 0; i strs.length; i){//取当前遍历到的字符串拼接在首部String first strs[i];//排除当前字符串 再将数组进行下层递归直到空的时候开始向上返回TreeSetString 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, 如果字符串数组 字符串ab ba compareTo返回负数a排前面 返回正数 b排前面Arrays.sort(strs,(a,b)-(ab).compareTo(ba));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不要去纠结贪心策略的证明五、给定一个字符串str只由‘X’和‘.’两种字符构成。X’表示墙不能放灯也不需要点亮‘.’表示居民点可以放灯需要点亮如果灯放在i位置可以让i-1i和i1三个位置被点亮返回如果点亮str中所有需要点亮的位置至少需要几盏灯package class14;import java.util.HashSet;/*** 给定一个字符串str只由‘X’和‘.’两种字符构成。* ‘X’表示墙不能放灯也不需要点亮* ‘.’表示居民点可以放灯需要点亮* 如果灯放在i位置可以让i-1i和i1三个位置被点亮* 返回如果点亮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, HashSetInteger 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;//如果i1 是超过边界 也就是i 是最后一个索引的时候 就可以直接退出了。即使当前i是. 需要照亮我们已经在前面先1灯了if(i 1 chars.length){break;}else {// 还没到最后边界 那么分析几种情况//1. 下个字符 i1 如果是X 那么灯1并且索引跳过X来到i2//2. 下个字符 i1 如果是. 那么灯也要1 这次索引来到i3 因为不管i3 是X还是. 都不需要去判断因为灯可以照亮3个.//这里不管那么种情况都是需要1灯所以统一放前面1 这么负责索引的走向if(chars[i1] X){i i2;}else {i i3;}}}}//最后返回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金条要分成102030三个部分。如果先把长度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金条要分成102030三个部分。** 如果先把长度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){//定义小根堆把数组存放进去PriorityQueueInteger 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!);}}
八、输入: 正数数组costs、正数数组profits、正数K、正数M costs[i]表示i号项目的花费 profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润) K表示你只能串行的最多做k个项目 M表示你初始的资金 说明:每做完一个项目马上获得的收益可以支持你去做下一个项目。不能并行的做项目。输出你最后获得的最大钱数。 package class14;import java.util.PriorityQueue;/*** 输入: 正数数组costs、正数数组profits、正数K、正数M* costs[i]表示i号项目的花费* profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)* K表示你只能串行的最多做k个项目* W表示你初始的资金* 说明: 每做完一个项目马上获得的收益可以支持你去做下一个项目。不能并行的做项目。* 输出你最后获得的最大钱数。* p* 贪心思想* 将每个项目的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) {//定义小根堆 按花费排序 大根堆 按利润排序PriorityQueueProgram minCostsHeap new PriorityQueue((a, b) - (a.costs - b.costs));PriorityQueueProgram 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;}}}
