[数据结构与算法]我要进大厂-算法-第八天（动态规划&贪心~好难呀）

阅读该文章预计90分钟

一：前缀树

1.1：举个例子说明前缀树

举个例子：

"abc" 加到头节点
如果头节点没有走向a的路，就创建一个a，依次建立a、b、c

“bce" 加到头节点
如果头节点没有走向b的路，就创建b，如果没有b-c的路，依次加入c、e

”abd“ 加入到头节点
头节点有走向a的路，那么来到a，有a-》b，来到b，没有b-d，则b的下面创建一个d

总的来说，依次看看有没有头节点到这个路，如果没有则创建出来

1.2：作用

判断某个字符串，是不是以某个字符串开头的

给出n个字符串，生成一个前缀树
然后再给一个字符串，判断是否存在某个开头（前缀）     ---满足
然后再给一个字符串，判断是否存在该字符串	       ---不满足，需要改造点1
然后再给一个字符串，判断有多少个字符串以它作为前缀   ---不满足，需要改造点2

改造点1：需要增加每个节点有多少个以该节点的字符串结尾的。如果超过0的，那就肯定存在该字符串
改造点2：需要增加每个节点被经过多少次，如果经历过n次，则有n个字符串以它作为前缀

1.3: Java代码

package xyz.fudongyang.basic.class_07.my;

public class Code_01_TrieTree {

    /**
     * 前缀树的节点的数据结构
     */
    public static class TrieNode {
        int path;   // 有多少个节点来过此路径
        int end;    // 有多少个节点以它为结尾
        TrieNode[] next;  // 我的下一个路径有26条

        public TrieNode() {
            // 默认我有26条路 a~z
            this.next = new TrieNode[26];
        }
    }

    /**
     * 前缀树节点
     */
    public static class Trie {
        // 前缀树拥有一个头节点
        TrieNode head;

        public Trie() {
            this.head = new TrieNode();
        }

        // 插入一个字符串
        public void insert(String req) {
            if (req == null) {
                return;
            }
            TrieNode node = head;
            char[] charArray = req.toCharArray();
            for (char c : charArray) {
                // 求出该字符串的字符在a~z的哪一个位置上
                int index = c - 'a';
                if (node.next[index] == null) {
                    // 如果从来没来过，则创建数据
                    node.next[index] = new TrieNode();
                }
                node = node.next[index];
                // 路过该节点的都+1
                node.path++;
            }
            // 以它结尾的都+1
            node.end++;
        }

        // 删除一个字符串
        public void delete(String req) {
            // 当这个字符串存在才删除
            if (search(req) != 0){
                TrieNode node = head;
                char[] charArray = req.toCharArray();
                for (char c : charArray) {
                    int index = c - 'a';
                    // 如果是最后一个来过该元素的，则后序元素也是只来过一次，则删除掉吧
                    if (--node.next[index].path == 0){
                        node.next[index] = null;
                        return;
                    }
                    node = node.next[index];
                }
                // 以它结尾的就要被删掉一次啦
                node.end--;
            }
        }


        // 判断当前字符串是否存在过几次
        public int search(String req) {
            if (req == null){
                return 0;
            }
            TrieNode node = head;
            char[] charArray = req.toCharArray();
            for (char c : charArray) {
                int index = c - 'a';
                if (node.next[index] == null){
                    return 0;
                }
                node = node.next[index];
            }
            return node.end;
        }

        // 判断当前字符串以它开头的有几次
        public int prefixNumber(String req){
            if (req == null){
                return 0;
            }
            TrieNode node = head;
            char[] charArray = req.toCharArray();
            for (char c : charArray) {
                int index = c - 'a';
                if (node.next[index] == null){
                    return 0;
                }
                node = node.next[index];
            }
            return node.path;
        }

    }


    public static void main(String[] args) {
        Trie trie = new Trie();
        System.out.println(trie.search("zuo"));
        trie.insert("zuo");
        System.out.println(trie.search("zuo"));
        trie.delete("zuo");
        System.out.println(trie.search("zuo"));
        trie.insert("zuo");
        trie.insert("zuo");
        trie.delete("zuo");
        System.out.println(trie.search("zuo"));
        trie.delete("zuo");
        System.out.println(trie.search("zuo"));
        trie.insert("zuoa");
        trie.insert("zuoac");
        trie.insert("zuoab");
        trie.insert("zuoad");
        trie.delete("zuoa");
        System.out.println(trie.search("zuoa"));
        System.out.println(trie.prefixNumber("zuo"));

    }

}

二：贪心

2.1:前提知识

贪心策略不要证明