数据结构与算法--贪心算法

 

1 贪心算法的概念

 
在某一标准下,优先考虑最满足标准的样本,最后考虑不满足标准的样本,最终得到一个答案的算法,叫做贪心算法

也就是说 不是从整体上加以考虑,所做出的是某种意义上的最优解

局部最优----->整体最优

---

 

2 贪心算法的套路

 

1. 实现一个不依靠贪心策略的解法X，可以用最暴力的尝试
2. 脑补出贪心策略A、贪心策略B、贪心策略C…
3. 用解法X和对数器，去验证每一个贪心策略，用实验的方式得知哪个贪心策略正确
4. 不要去纠结贪心策略的证明

---

 

3 贪心算法常用技巧

 

1. 根据某标准建立一个比较器来排序
2. 根据某标准建立一个比较器来组成堆

---

 

4 会议问题

 

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。
给你每一个项目开始的时间和结束的时间(给你一个数 组，里面是一个个具体
的项目)，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。
返回这个最多的宣讲场次

贪心策略 : 从结束时间最早的开始选择

coding

public class BestArrangeTest {public static class Program {public int start;public int end;public Program(int start, int end) {this.start = start;this.end = end;}}public static class ProgramComparator implements Comparator<Program> {@Overridepublic int compare(Program o1, Program o2) {return o1.end - o2.end;}}public static int bestArrange(Program[] programs,int start){Arrays.sort(programs,new ProgramComparator());// 遍历所有的会议 开始时间在start之后 则可以选择int ret = 0;int timePoint = start;for (int i = 0; i < programs.length;++i){if (programs[i].start >= timePoint){ret ++;// 时间点来到会议的结束时间点timePoint = programs[i].end;}}return ret;}
}

---

 

5 字典序问题

 

给定一个字符串类型的数组strs，找到一种拼接方式，使得把所有字符串拼起来之后形成的
字符串具有最小的字典序

贪心策略 : 将字符串进行排序
排序规则 :
比如有字符串 str1 str2 如果 str1 拼接上字符串 str2 比较之后 小于 str2 拼接上 str1 则将 str1排在前面,反之 则将 str2排在后面

遍历所有的字符串然后拼接起来

coding

 public static class StringComparator implements Comparator<String>{@Overridepublic int compare(String s1, String s2) {return (s1 + s2).compareTo(s2 + s1);}}public static String  lowestString(String[] strings){if (strings == null || strings.length == 0){return null;}Arrays.sort(strings,new StringComparator());String retStr = "";for (int i = 0; i < strings.length; i++){retStr += strings[i];}return retStr;}