左程云 Java 笔记--前缀树 贪心算法

文章目录

• 前缀树
• 贪心算法
• • 例1
  • 字典序排序
  • 例3---哈夫曼编码
  • 例四
• 堆的一个应用
• N皇后
• 总结

---

前缀树

介绍前缀树
何为前缀树?如何生成前缀树?
例子:
一个字符串类型的数组arr1,另一个字符串类型的数组arr2。

• arr2中有哪些字符，是arr1中出现的?请打印。
• arr2中有哪些字符，是作为arr1中某个字符串前缀出现的?请打印。
• arr2中有哪些字符，是作为arr1 中某个字符串前缀出现的?请打印
• arr2中出现次数最大的前缀。

    public static class TireNode{
        public int pass;
        public int end;
//        public HashMap next;
//        public TreeMap next;
        public TireNode[] nexts;

        public TireNode(){
            pass = 0;
            end = 0;
            nexts = new TireNode[26];
        }
    }
    public static class Tire{
        private TireNode root;

        public Tire(){
            root = new TireNode();
        }

        //加入一个字符串
        public void insert(String word){
            if (word == null){
                return;
            }
            char[] chs = word.toCharArray();
            TireNode node = root;
            node.pass++;
            int index  = 0;
            for (int i = 0; i < chs.length; i++) {//从左向右遍历字符
                index = chs[i] - 'a';// 由字符对应走向哪条路
                if (node.nexts[index] == null){
                    node.nexts[index] = new TireNode();
                }
                node = node.nexts[index];
                node.pass++;
            }
            node.end++;
        }


        //word这个词之前加入过几次
        public int search(String word){
            if (word == null){
                return 0;
            }
            char[] chs = word.toCharArray();
            TireNode 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.end;
        }

        //所有加入的字符串中，有几个是一pre为前缀的
        public int prefixNumber(String pre){
            if (pre == null){
                return 0;
            }
            char[] chs = pre.toCharArray();
            TireNode 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.pass;
        }

        //删除一个节点 沿途p--，最后e--
        public void delete(String word){
            if (search(word) != 0){
                char[] chs = word.toCharArray();
                TireNode node = root;
                node.pass--;
                int index = 0;
                for (int i = 0; i < chs.length; i++) {
                    index = chs[i] - 'a';
                    if (--node.nexts[index].pass == 0){
                        node.nexts[index] = null;
                        return;
                    }
                    node = node.nexts[index];
                }
                node.end--;
            }
        }
        

    }

贪心算法

在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫作贪心算法。
也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。
局部最优-?-> 整体最优

例1

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

public class BestArrange {
    public static class Program{
        public int star;
        public int end;

        public Program(int star,int end){
            this.star = star;
            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 bastArrange(Program[] programs,int timePoint){
            Arrays.sort(programs,new ProgramComparator());
            int res = 0;
            //依次遍历所有的会议
            for (int i = 0; i < programs.length; i++) {
                if (timePoint > programs[i].star){
                    res++;
                    timePoint = programs[i].end;
                }
            }
            return res;
        }
    }
}

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

字典序排序

public class lowstString {
    public static void main(String[] args) {

    }
    public static class MtComparator implements Comparator<String>{
        @Override
        public int compare(String o1, String o2) {
            return (o1+o2).compareTo(o2+o1);
        }
    }

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

贪心策略在实现时，经常使用到的技巧:
1，根据某标准建立一个比较器来排序
2，根据某标准建立一个比较器来组成堆.

例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铜板。
输入一个数组，返回分割的最小代价。

public static int lessMoney(int[] arr){
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            pQ.add(arr[i]);
        }
        int sum = 0;
        int cur = 0;
        while (pQ.size() > 1){
            cur = pQ.poll() + pQ.poll();
            sum += cur;
            pQ.add(cur);
        }
        return sum;
    }

例四

输入:
正数数组costs – costs[i]表示i号项目的花费
正数数组profits – profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
正数k – k表示你只能串行的最多做k个项目
正数m – m表示你初始的资金

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

public class IPo {
    public static class Node{
        public int p;
        public int c;

        public Node(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }

    public static class MinCostComparator implements Comparator<Node>{
        @Override
        public int compare(Node o1, Node o2) {
            return o1.c-o2.c;
        }
    }

    public static class MaxProfitComparator implements Comparator<Node>{

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

    public static int fingMaximizedCapital(int k ,int w, int[] Profits,int[] Capital){
        PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());
        PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MinCostComparator());

        for (int i = 0; i < Profits.length; i++) {
            maxProfitQ.add(new Node(Profits[i], Capital[i]));
        }
        for (int i = 0; i < k; i++) {
            while (!maxProfitQ.isEmpty() && minCostQ.peek().c <= w){
                maxProfitQ.add(minCostQ.poll());
            }
            if (maxProfitQ.isEmpty()){
                return w;
            }
            w += maxProfitQ.poll().p;
        }
        return w;
    }

}

堆的一个应用

一个数据流中， 随时可以取得中位数

N皇后

public class Nqueens {
    public static int num1(int n){
        if (n < 1){
            return 0;
        }
        int[] record = new int[n];
        return process1(0,record,n);
    }

    private static int process1(int i, int[] record, int n) {
        if (i == n){
            return 1;
        }
        int res = 0;
        for (int j = 0; j < n; j++) {
            if (isValid(record,i,j)){
                record[i] = j;
                res += process1(i+1,record,n);
            }
        }
        return res;
    }

    public static boolean isValid(int[] record,int i, int j){
        for (int k = 0; k < i; k++) {
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i-k)){
                return false;
            }
        }
        return true;
    }
}

位运算

    public static int num2(int n){
        if (n < 1|| n > 32){
            return 0;
        }
        int limit = n == 32? -1:(1<<n)-1;
        return process2(limit,0,0,0);
    }

    // colLim 列的限制，1的位置不能放皇后，0的位置可以
    // leftDiaLim 左斜线的限制，1的位置不能放皇后，θ的位置可以
    // rightDiaLim 右斜线的限制，1的位置不能放皇后，θ的位置可以
    private static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
        if (colLim == limit){
            return 1;
        }
        int pos = 0;
        int mostRightOne = 0;

        pos = limit & (~(colLim | leftDiaLim | rightDiaLim));//可以填皇后的位置

        int res = 0;
        while (pos != 0){
            mostRightOne = pos & (~pos+1);
            pos = pos -mostRightOne;
            res += process2(limit,colLim|mostRightOne,
                    (leftDiaLim | mostRightOne) <<1,
                    (rightDiaLim | mostRightOne)>>>1);
        }
        return res;
    }

总结