算法初级-06-贪心算法系列

年轻即出发...

简书：https://www.jianshu.com/u/7110a2ba6f9e

知乎：https://www.zhihu.com/people/zqtao23/posts

GitHub源码：https://github.com/zqtao2332

个人网站：http://www.zqtaotao.cn/ （停止维护更新内容，转移简书）

QQ交流群：606939954

​ 咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。

最后：喜欢编程，对生活充满激情

本节内容预告

实例1：前缀树

实例2：贪心算法理解，例题字典序字符串拼接

实例3：黄金分割问题

实例4：项目收益问题

实例5：会议时间安排问题

从实例2开始都是贪心算法问题

实例1

前缀树

初始化一个头结点
每次新进一个字符串都是从头结点开始查

插入"abc"

查看 有指向 a 的路吗？
没有，添加
有，复用
注意：不是将a添加到节点上，而是路径上。
重复上述过程，建立前缀树如下图

此时，再加上一个字符串怎么办？如"bce"，同样过程
查看 有指向b 的路吗？
没有，添加
有，复用
...
添加后如图

继续添加"abd"
查看 有指向 a 的路吗？
没有，添加
有，复用

具体过程如图

1_1_前缀树建立过程.png

一个字符串加入前缀树的过程，总是从头结点开始，然后依次看有没有沿途的路
有，复用
没有，新建

前缀树作用
比如已经添加了N个字符串，查看N个字符串中，是否某一个字符串是以 "be" 开头的

扩展1：你加入的字符串有 "be"吗？
这个问题，上述形成的前缀树，已经无法满足现在的需求了，如上图，你无法确定-b-e-路是你添加字符串"bef"形成的还是添加"be"形成的

解决：给每个节点添加上数据项。数据项：有多少个字符串是以当前节点结尾的。
加上这个数据项好处
1、前缀树是否加入了某个字符串
2、某个字符串在前缀树中添加的次数

1_2_数据项扩展.png

如图
加上数据项（有多少个字符串是以当前节点结尾的）后可以轻松查看1、是否存在某个字符2、某个字符串在前缀树中的个数
如图：abd 3个 be 2个 其他字符串都是一个

扩展2：有多少个节点以某字符串作为前缀？
解决：再添加一个数据项：添加字符串时当前节点被滑过了几次
比如依次添加字符串：["abc", "abd", "ace"],统计有多少以"ab"为前缀的字符串

在添加的时候每次滑过某个节点，都记录滑过次数
abc
a 1
b 1
c 1

abd
a 2
b 2
d 1

ace
a 3
c 1
e 1

很清晰的查出以ab 为前缀的字符串有 2 个，以 a 为前缀的有3 个，以ac 为前缀的有 1个

前缀树在添加，和查的过程中代价都非常的低，跟样本量N没有关系，和样本的长度有关。

/**
 * @description:
 * @version: 1.0
 */
public class Code_36_TrieTree {

    // 前缀树数据项结构
    public static class TrieNode {
        public int pathNum; // 字符串滑过当前节点是次数
        public int endNum; // 以此节点结尾的字符串个数

        //        public HashMap<Character, TrieNode> nexts; // 结构复杂使用map
        public TrieNode[] nexts; // 这里为了方便使用数组，假设涉及数据都是小写的26个字母

        public TrieNode() {
            this.pathNum = 0;
            this.endNum = 0;
            this.nexts = new TrieNode[26];
        }
    }

    // 前缀树
    public static class Trie {
        private TrieNode root; // 前缀树加上数据项

        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            if (word == null) return;
            TrieNode node = this.root;

            char[] chars = word.toCharArray();
            int index = 0; // 用来标记路线，默认26个字母，每个节点26条路线

            for (int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                if (node.nexts[index] == null) {
                    node.nexts[index] = new TrieNode();
                }

                node = node.nexts[index];
                node.pathNum++;
            }
            node.endNum++;// 结尾节点
        }

        public void delete(String word) {
            if (search(word) != 0) {
                TrieNode node = this.root;
                char[] chars = word.toCharArray();
                int index = 0;

                for (int i = 0; i < chars.length; i++) {
                    index = chars[i] - 'a';
                    if (--node.nexts[index].pathNum == 0) { // 如果节点滑过次数只有一次，直接置为null，后序节点无需再遍历
                        node.nexts[index] = null;
                        return;
                    }
                    node = node.nexts[index];
                }
                node.endNum--;
            }
        }


        // 查找是否存在某个字符串
        public int search(String word) {
            if (word == null) return 0;

            TrieNode node = this.root;
            char[] chars = word.toCharArray();
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.endNum;
        }

        public int prefixNumber(String pre) {
            if (pre == null) {
                return 0;
            }
            char[] chs = pre.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pathNum;
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        System.out.println(trie.search("test"));
        trie.insert("test");
        System.out.println(trie.search("test"));
        trie.delete("test");
        System.out.println(trie.search("test"));
        trie.insert("test");
        trie.insert("test");
        trie.delete("test");
        System.out.println(trie.search("test"));
        trie.delete("test");
        System.out.println(trie.search("test"));
        trie.insert("testa");
        trie.insert("testac");
        trie.insert("testab");
        trie.insert("testad");
        trie.delete("testa");
        System.out.println(trie.search("testa"));
        System.out.println(trie.prefixNumber("test"));

    }
}

实例2

贪心算法：对问题进行求解时，总是做出当前来看是最好的选择。

笔试解决贪心算法的技巧

提出什么策略很容易，但是证明一个贪心策略是对的很难，最简单的证明就是使用对数器验证，
在对数器的样本（如5000个）是对的，那就认为它是对的。

举例一个非常难的贪心算法问题：做法简单，证明难。

字符串字典排序拼接

给你一个字符串数组，目的是把所有的字符串拼起来，不能遗漏，这样会得到很多
拼接的结果，请你找到拼接的字符串，字典序最小的结果。
如："ab", "cd", "ef"
拼接结果
abcdef
abefcd

cdabef
cdefab

efabcd
efcdab

这六种结果，其中，字面值最小的是abcdef。

理解一个概念：字典序
长度一样，当做26进制的数，比较大小，小在前
长度不等，补全，补位为字面值最小的数 如 "abc" 和 "b" 比较，补位 "b00"。a < b
所以"abc"在前，"b"在后

贪心策略:两个字符串排序时先拼接再比较
str1 + str2 <= str2 + str1 ？ str1 : str2

import java.util.Arrays;
import java.util.Comparator;

/**
 * @description: 字符串字典序拼接
 * 给你一个字符串数组，目的是把所有的字符串拼起来，不能遗漏，这样会得到很多
 * 拼接的结果，请你找到拼接的字符串，字典序最小的结果。
 * 如："ab", "cd", "ef"
 * 拼接结果
 * abcdef
 * abefcd
 *
 * cdabef
 * cdefab
 *
 * efabcd
 * efcdab
 *
 * 这六种结果，其中，字面值最小的是abcdef。
 *
 * 理解一个概念：字典序
 * 长度一样，当做26进制的数，比较大小，小在前
 * 长度不等，补全，补位为字面值最小的数 如 "abc" 和 "b" 比较，补位 "b00"。a < b
 * 所以"abc"在前，"b"在后
 *
 *
 *
 * 思路：进行字典排序
 * @version: 1.0
 */
public class Code_37_TX_LowestLexicography {

    // 贪心策略:两个字符串排序时先拼接再比较
    // str1 + str2 <= str2 + str1 ？ str1 : str2

    public static class MyComparator implements Comparator<String>{

        @Override
        public int compare(String strA, String strB) {
            return (strA + strB).compareTo((strB + strA));
        }
    }

    public static String lowestLexicography(String[] str){
        if (str == null || str.length == 0)
            return "";
        Arrays.sort(str, new MyComparator());
        String res = "";
        for (int i = 0; i < str.length; i++) {
            res += str[i];
        }
        return res;
    }

    public static void main(String[] args) {
        String[] strs1 = { "abc", "bc", "ac", "aa", "abb" };
        System.out.println(lowestLexicography(strs1));

        String[] strs2 = { "ba", "b" };
        System.out.println(lowestLexicography(strs2));
    }
}

实例3

黄金分割问题

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如 长度为20的 金条，不管切成长度多大的两半，都要花费20个铜 板。一群人想整分整块金 条，怎么分最省铜板？ 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为 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铜板。

输入一个数组，返回分割的最小代价

从题意中提取出两个信息

1、花费和长度数值一样

2、总和要最小，且总和是由一个个子金额累加的

哈夫曼编码策略
总代价是由子带价累加，累乘的这类问题，都可以使用哈夫曼编码来进行求解。

理解哈夫曼建树过程

3_1_哈法曼编码.png
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @description: 黄金分割
 * 一块金条切成两半，是需要花费和长度数值一样的铜板的。
 * 比如 长度为20的 金条，不管切成长度多大的两半，都要花费20个铜 板。
 * 一群人想整分整块金 条，怎么分最省铜板？
 * 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为 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铜板。
 *
 * 输入一个数组，返回分割的最小代价。
 * @version: 1.0
 */
public class Code_38_TX_LessMoney {

    public static int lessMoney(int[] arr) {
        // 堆，小根堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            minHeap.add(arr[i]); // 如小根堆
        }

        int res = 0;
        int cur = 0;
        while (minHeap.size() > 1) {
            cur = minHeap.poll() + minHeap.poll();
            res += cur;
            minHeap.add(cur);
        }
        return res;
    }

    // 小根堆比较器
    public static class MinHeapComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2; // < 0  o1 < o2  负数
        }
    }

    //大根堆比较器
    public static class MaxHeapComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1; // <   o2 < o1
        }

    }

    public static void main(String[] args) {
        // solution
        int[] arr = {6, 7, 8, 9};
        System.out.println(lessMoney(arr));

        int[] arrForHeap = {3, 5, 2, 7, 0, 1, 6, 4};


        // 测试大根堆，小根堆，优先级队列（实际就是小根堆）

        // min heap 默认情况下，PriorityQueue 就是小根堆
        PriorityQueue<Integer> minQ1 = new PriorityQueue<>();
        for (int i = 0; i < arrForHeap.length; i++) {
            minQ1.add(arrForHeap[i]);
        }
        while (!minQ1.isEmpty()) {
            System.out.print(minQ1.poll() + " ");
        }
        System.out.println();

        // min heap use Comparator
        System.out.println("min heap use Comparator");
        PriorityQueue<Integer> minQ2 = new PriorityQueue<>(new MinHeapComparator());
        for (int i = 0; i < arrForHeap.length; i++) {
            minQ2.add(arrForHeap[i]);
        }
        while (!minQ2.isEmpty()) {
            System.out.print(minQ2.poll() + " ");
        }
        System.out.println();

        // max heap use Comparator
        System.out.println("max heap use Comparator");
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(new MaxHeapComparator());
        for (int i = 0; i < arrForHeap.length; i++) {
            maxQ.add(arrForHeap[i]);
        }
        while (!maxQ.isEmpty()) {
            System.out.print(maxQ.poll() + " ");
        }
    }
}

实例4

项目收益

输入： 参数1，正数数组costs

参数2，正数数组profits

参数3，正数k

参数4，正数m

costs[i]表示i号项目的花费

profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)

k表示你不能并行、只能串行的最多做k个项目

m表示你初始的资金

说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个 项目。
输出： 你最后获得的最大钱数。

贪心策略

每次从可选择的项目中，选取花费最小的几个；从这几个中选取收益最高的项目。

4_1.png

项目收益

4_2_项目收益.png
import java.util.Comparator;
import java.util.PriorityQueue;

public class Code_39_IPO {

    // 构建项目数据结构
    public static class Node{
        public int cost; // 花费
        public int profits; // 利润

        public Node(int cost, int profits){
            this.cost = cost;
            this.profits = profits;
        }
    }

    // 最小花费，小根堆
    public static class MinCostHeapComparator implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            return o1.cost - o2.cost;
        }
    }

    // 最大收益，大根堆
    public static class MaxProfitsHeapComparator implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            return o2.profits - o1.profits;
        }
    }

    /**
     *
     * @param k 表示你不能并行、只能串行的最多做k个项目
     * @param m 表示你初始的资金
     * @param profits profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
     * @param costs costs[i]表示i号项目的花
     * @return 你最后获得的最大钱数。
     *
     * @Description 说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个 项目
     */
    public static int findMaximizedCapital(int k, int m, int[] profits, int[] costs) {
        Node[] nodes = new Node[profits.length];
        // 结构化项目数据
        for (int i = 0; i < profits.length; i++) {
            nodes[i] = new Node(costs[i], profits[i]);
        }

        // 使用自定义的排序规则，即自定义的比较器，建立最小花费小根堆，最大收益大根堆
        PriorityQueue<Node> minCostsHeap = new PriorityQueue<>(new MinCostHeapComparator());
        PriorityQueue<Node> maxProfitsHeap = new PriorityQueue<>(new MaxProfitsHeapComparator());

        for (int i = 0; i < nodes.length; i++) {
            minCostsHeap.add(nodes[i]);
        }

        for (int i = 0; i < k; i++) { // 表示最多可以做 k 个项目
            while (!minCostsHeap.isEmpty() && minCostsHeap.peek().cost <= m){ // 小根堆不为空且存在花费小于当前可用的金额
                maxProfitsHeap.add(minCostsHeap.poll());
            }
            if (maxProfitsHeap.isEmpty()){
                return m; // 大根堆为空，表示没有花费小于当前可用金额的项目进入大根堆
            }
            m += maxProfitsHeap.poll().profits;
        }

        return m;
    }
}

实例5

会议时间安排

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

贪心策略：每次选取会议结束时间最早的

​

5_1_会议选取方案.png
import java.util.Arrays;
import java.util.Comparator;

/**
 * @description: 会议时间安排
 *
 * 一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目 的宣讲。
 *
 * 给你每一个项目开始的时间和结束的时间(给你一个数 组，里面 是一个个具体的项目)，
 * 你来安排宣讲的日程，要求会 议室进行 的宣讲的场次最多。
 * 返回这个最多的宣讲场次。
 *
 * 贪心策略：每次选取结束时间最早的
 * @version: 1.0
 */
public class Code_40_TX_BestArrange {

    // 构建会议数据结构
    public static class Program{
        public int startTime;
        public int endTime;

        public Program(int startTime, int endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }
    }

    // 会议比较器，按照项目结束时间进行排序，结束时间早放前
    public static class ProgramComparator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o1.endTime - o2.endTime;
        }
    }

    /**
     * @param programs 具体的会议信息
     * @param curTime 当前时间
     * @return 返回这个最多的宣讲场次
     */
    public static int bestArrange(Program[] programs, int curTime){
        if (programs == null || programs.length == 0) return 0;

        Arrays.sort(programs, new ProgramComparator()); // 按照结束时间排序

        int res = 0;
        for (int i = 0; i < programs.length; i++) {
            if (curTime <= programs[i].startTime){ // 可以进行的会议，其他都排除
                res++;
                curTime = programs[i].endTime; // 重置当前时间为会议结束时间
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Program[] programs = new Program[9];
        int[] startTime = {7, 7, 8, 9, 10, 10, 12, 14, 16};
        int[] endTime = {9, 8, 11, 10, 12, 13, 15, 19, 17};

        for (int i = 0; i < startTime.length; i++) {
            programs[i] = new Program(startTime[i], endTime[i]);
        }

        int res = bestArrange(programs, 6);
        System.out.println(res);
    }
}

以上均为学习总结

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,125评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,293评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 162,054评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,077评论 1赞 291
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,096评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,062评论 1赞 295
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,988评论 3赞 417
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,817评论 0赞 273
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,266评论 1赞 310
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,486评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,646评论 1赞 347
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,375评论 5赞 342
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,974评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,621评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,796评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,642评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,538评论 2赞 352