网站虚拟交易技术怎么做,o2o平台都有哪些网站公司,网站即将上线 模板,开工作室做网站怎样找资源数据结构与算法-贪心算法 1 贪心算法的概念 2 贪心算法的套路 3 贪心算法常用技巧 4 会议问题 5 字典序问题 1 贪心算法的概念 在某一标准下,优先考虑最满足标准的样本,最后考虑不满足标准的样本,最终得到一个答案的算法,叫做贪心算法
也就是说 不是从整体上加以考虑,所… 数据结构与算法-贪心算法 1 贪心算法的概念 2 贪心算法的套路 3 贪心算法常用技巧 4 会议问题 5 字典序问题 1 贪心算法的概念 在某一标准下,优先考虑最满足标准的样本,最后考虑不满足标准的样本,最终得到一个答案的算法,叫做贪心算法
也就是说 不是从整体上加以考虑,所做出的是某种意义上的最优解
局部最优-----整体最优 2 贪心算法的套路 实现一个不依靠贪心策略的解法X可以用最暴力的尝试脑补出贪心策略A、贪心策略B、贪心策略C…用解法X和对数器去验证每一个贪心策略用实验的方式得知哪个贪心策略正确不要去纠结贪心策略的证明 3 贪心算法常用技巧 根据某标准建立一个比较器来排序根据某标准建立一个比较器来组成堆 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 ComparatorProgram {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 ComparatorString{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;}
