数据结构与算法/trie

前缀树

“abc”,”ab”

root(pass = 2 , end = 0)

a (pass=2,end =0)

b(pass=2 ,end = 1)

c(pass = 1,end = 1)

package trie;

import java.util.HashMap;

/**
 * @author 忘忧症
 * @Distribute
 */
public class Trie {

    private  final TrieNode root = new TrieNode();


    public  void process(String str){
        TrieNode node = root;
        root.pass+=1;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            String cStr = c+"";
            if (i == str.length()-1) {
               node = node.insertTrie(cStr,true);
            }else{
               node =  node.insertTrie(cStr,false);
            }
        }
    }

    public void remove(String str){
        _remove(str,root,0);
    }

    private boolean  _remove(String str,TrieNode node,int index){
        char c = str.charAt(index);
        String cStr = c+"";
        TrieNode trieNode = node.children.get(cStr);
        if (trieNode == null ) {
            return  false;
        }
        if (index== str.length()-1){
            trieNode.pass --;
            trieNode.end--;
            if (trieNode.pass == 0){
                node.children.remove(cStr);
            }
        }
        else if (_remove(str,trieNode,index+1)){
            trieNode.pass --;
            if (trieNode.pass == 0){
                node.children.remove(cStr);
            }
        }
        return true;
    }

    public static void main(String[] args) {

        Trie trie = new Trie();

        trie.process("abc");
        trie.process("ab");
        trie.process("dc");
        trie.process("abdc");
        trie.process("abcd");
        System.out.println(trie.root);


        trie.remove("abc");
        trie.remove("abcd");
        System.out.println(trie.root);
    }


    private static class TrieNode{

        private int pass = 0;
        private int end = 0;
        private HashMap<String,TrieNode> children = new HashMap<>();

        private TrieNode insertTrie(String str,Boolean isEnd){

            TrieNode child = children.get(str);
            if (null == child) {
                //新前缀
                child = new TrieNode();
                children.put(str,child);
            }
            child.pass = child.pass+1;
            child.end = isEnd? child.end+1: child.end;

            return child;
        }


        @Override
        public String toString() {
            return "TrieNode{" +
                    "pass=" + pass +
                    ", end=" + end +
                    ", children=" + children +
                    '}';
        }
    }
}

桶排序

package bucket;


import merger.MergerAlgorithm;

import static merger.MergerAlgorithm.printArray;

/**
 * @author 忘忧症
 * @Distribute
 */
public class BucketSorting {


    public static int findMax(int[] arr,int start,int end){
        int result = start;
        for (int i = start; i <= end; i++) {
            if (arr[i]>arr[result]){
                result = i;
            }
        }
        return arr[result];
    }

    public static void countSort(int[] arr,int start,int end){

        int max = findMax(arr,start ,end);
        int[] help = new int[max+1];
        for (int i = 0; i < arr.length; i++) {
            help[ arr[i] ] ++;
        }
        int j =0 ;
        for (int i = start; i <= end ; i++) {
           while (help[j]-->0){
               arr[i++] = j;
           }
        }
    }

    public static int  digit(int num){

        int result = 0;
        while ( num >0){
            num/=10;
            result++;
        }
        return result;
    }


    public static int  findDigit(int num, int type){

        while (type>0){
            num/=10;
            type --;
        }
        return  num%10;
    }

    public static void radixSort(int[] arr,int start,int end){

        int max = findMax(arr,start,end);
        int digit = digit(max);

        int [] help = new int[end -start+1];

        for (int i = 0; i < digit; i++) {

            int[] radix = new int[10];
            for (int j = start; j <= end ; j++) {
                int digit1 = findDigit(arr[j], i);
                radix[digit1]++;
            }

            for (int j = 1; j < 10; j++) {
                radix[j]=radix[j]+radix[j-1];
            }

            for (int j = end; j >= start ; j--) {
                int digit1 = findDigit(arr[j], i);
                int radix1 = radix[digit1];
                radix[digit1]--;
                help[ radix1-1 ] = arr[j];
            }

            MergerAlgorithm.copyArray(arr,start,help,start,end);
        }
    }


    public static void main(String[] args) {

        int[] arr = new int[]{55,33,11,798,2,648,2,3,78,6};
        radixSort(arr,0,arr.length-1);
        printArray(arr);

    }
}

O（N^2）的常数项 可以很低

O （N*logN ） 常数一般比较高

所以 O （N*logN ）算法和 O（N^2）算法可以一起用

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： 忘忧症
• 本文链接： https://NepenthesZGW.github.io/2020/09/07/数据结构与算法/trie/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！