博客

前缀树 ：建立好前缀树后可以把下面的题目快速地解决，便于实现前缀查找

题目：一个字符串类型的数组arr1，另一个字符串类型的数组arr2.arr2中有哪些字符，是arr1中出现的，请打印。arr2中有哪些字符，是作为arr1中某些字符串前缀出现的？请打印。arr2中有哪些字符是arr1中某个字符串前缀出现的？请打印arr2中出现次数最多的前缀。

public class TrieNode {
    public static class TrieNode{
        public int pass;//表示通过该节点的次数
        public int end;//表示以该节点为终点的次数
        public TrieNode[] next;//表示下一节点的情况
        public void TrieNode(){
            pass = 0;
            end =0;
            next = new TrieNode[26];//表示后续可以有26个字母
        }
    }
    public static class Trie{
        private TrieNode root;
        public Trie(){
            root = new TrieNode();//默认根节点为只有后续的空节点
        }
        /*某个字符串出现的次数*/
        public int insert(String word){//插入一个字符串
            if(word == null){
                return 0;
            }
            char[] chs = word.toCharArray();//用array把word装起来
            TrieNode node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i]-'a';
                if(node.next[index]==null){
                    return 0;//有，不做任何动作
                }
                node = node.next[index];
            }
            return node.end;
        }
        /*判断是否含有某一个字符串的次数*/
        public int search(String word){
            if(word == null){
                return 0;
            }
            char[] chs = word.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i]-'a';
                if(node.next[index]==null){
                    return 0
                }
                node = node.next[index];
                return node.end;
            }
            return 0;
        }
       /*查找有多少个字符串是以某个字符串为前缀的*/
       public int search1(String word){
           if(word == null){
               return 0;
           }
           char[] chs = word.toCharArray();
           TrieNode node = root;
           int index = 0;
           for (int i = 0; i < chs.length; i++) {
               index = chs[i]-'a';
               if(node.next[index]==null){
                   return 0;
               }
               node = node.next[index];
               return node.pass;
           }
           return 0;
       }
       public void delete(String word){
           if(word == null){
               return ;
           }
           char[] chs = word.toCharArray();
           TrieNode node = root;
           int index = 0;
           for (int i = 0; i < chs.length; i++) {
               index = chs[i]-'a';
               if(node.next[index]==null){
                   return ;
               }
               else {
                   node.pass--;
                   if(node.pass==0) {
                       node.next=null;
                       return;
                   }
                   node = node.next[index];
               }
           }
           node.end--;
           return;
       }
       }
    }
}

贪心算法：在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，称为贪心算法。可以理解为先考虑局部最优再考虑全局最优。

套路：

题目一：

贪心策略：哪一个会议结束时间早就安排哪一个会议。

package greedyAl;

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

/**
 * @author 咕噜大飞侠
 * @version 1.0
 * Create by 24/2/2022 下午3:49
 */


public class BestArrange {
    public static class program{
        int star;
        int end;
        public void program(int star,int end){
            this.star=star;
            this.end=end;
        }
    }
    public static class ProgramComparator implements Comparator<program>{
        public int compare(program o1,program o2){
            return o1.end-o2.end;
        }
    }
    public static int bestArrange(program[] programs,int timePoint){
        Arrays.sort(programs,new ProgramComparator());
        int count=0;//记录能够满足的会议数量
        for (int i = 0; i < programs.length; i++) {
            if(timePoint<programs[i].end){
                count++;
                timePoint=programs[i].end;
            }
        }
        return count;
    }

}

贪心算法在笔试中的套路：

实现一个不依靠贪心策略的解法x，可以用最暴力的尝试；脑补出贪心策略A、贪心策略B、贪心策略C；用解法x和对数器，去验证每一个贪心策略，用实验的方式得知哪一个贪心策略正确，不去纠结贪心策略的证明。

字典序：哪一个单词在字典里面排前面就谁排前面。不同长度的字符串字典序处理：将短的后面补0使其等于长的。

拼接技巧：A B=A*K^B+B，其中K是该单个字符的进制

贪心策略在实现时的技巧：根据某标准建立一个比较器来排序；根据某标准建立一个比较器来组成堆

题目二

算法策略：采用哈夫曼树算法

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

题目三：

策略：每次选择已有资金能够支持的利润最大的项目

一个小根堆，依靠花费排队；一个大根堆，能够满足花费的项目进堆，依靠利润最大存。

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author 咕噜大飞侠
 * @version 1.0
 * Create by 25/2/2022 上午9:40
 */


public class MostProfits {
    public static class Node{
        int c;
        int p;
        public Node(int c,int p){
            this.c=c;
            this.p=p;
        }
    }
    public static  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 class int mostProfits(int[] costs,int[] profits,int k,int m){
        PriorityQueue<Node> minCost=new PriorityQueue<Node>(new MinCostComparator());
        PriorityQueue<Node> maxPrifit=new PriorityQueue<>(new MaxProfitComparator());
            for (int i = 0; i < costs.length; i++) {
                minCost.add(new Node(costs[i],profits[i]));
            }
            for (int i = 0; i < k; i++) {
                while (!minCost.isEmpty()&&minCost.peek().p<=m){
                    maxPrifit.add(minCost.poll());
                }
                //跳出语句，没办法找到满足m的项目了
                if(maxPrifit.isEmpty()){
                    return m;
                }
                m+=maxPrifit.poll().p;
            }
            return m;
    }
}

题目四：在一个数据流中随时找到他的中位数。

策略：准备一个大根堆和小根堆；cur<=大根堆.peek？入大根堆：入小根堆；比较大根堆和小根堆的size，两差>=二，平衡调整

题目5：N皇后问题

public class NQueens {
    public static int nQueens(int n){//返回值为可以找到的摆法
        if(n<1){
            return 0;
        }
        int[] record = new int[n];
        return process(0,record,n);
    }
    public static int process(int i,int[] record,int n){ //i代表初始行数，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+=process(i+1,record,n);
            }
        }
        return res;
    }
    public static boolean isValid(int[] record,int i,int j){
        for(int k=0;k<i;k++){//这里遍历的是之前i行的情况
            if(j==record[k]||Math.abs(record[k]-j)==Math.abs(i-k)){//列一致或者成45度都误
                return false;
            }
        }
        return true;
    }
}

优化思路，使用位运算代替原来的record数组。0代表可以插入的位置，1代表不可以拜访的位置