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

 

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> {

        @Override
        public 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

 

5 字典序问题

 

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

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

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

coding

 public static class StringComparator implements Comparator<String>{

        @Override
        public 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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19