算法类核心算法总结

package com.peter.algorithm.tree; import java.util.HashMap; /** * 前缀树【用于搜索某个字符是否在某些字符集合中存在，或者用于搜索某个字符集中是否包含以某个字符为前缀的字符并且有多少个】 * <p> * 前缀树insert方法 * 1、初始化构造一个空的TrieNode[pass=0,end=0,nexts=new int[26]] * 2、将字符串拆分为char[]数组 * 3、循环字符数组，当前TrieNode的pass++，并且判断当前TrieNode的 next[字符对应的index]是否存在TrieNode，如果没有则新建 * 4、当前TrieNode的 next[字符对应的index]的pass++，当前TrieNode=next[字符对应的index] * 5、循环结束当前TrieNode的end++ */ public class TrieTree { private TrieNode root; public TrieTree(TrieNode root) { this.root = new TrieNode(); } public void insert(String word) { if (word == null) { return; } TrieNode currentNode = root; currentNode.pass++; int index = 0; char[] chars = word.toCharArray(); for (char c : chars) { index = c - 'a'; if (currentNode.nexts[index] == null) { currentNode.nexts[index] = new TrieNode(); } currentNode = currentNode.nexts[index]; currentNode.pass++; } currentNode.end++; } /** * 删除某个之前加入的字符串 * * @param word */ public void delete(String word) { if (search(word) > 0) { TrieNode currentNode = root; int index = 0; char[] chars = word.toCharArray(); for (char c : chars) { index = c - 'a'; if (--currentNode.nexts[index].pass == 0) { currentNode.nexts[index] = null; return; } currentNode = currentNode.nexts[index]; } currentNode.end--; } } /** * 搜索某个字符串之前加入过多少次 * * @param word * @return */ public int search(String word) { TrieNode currentNode = searchEndTrieNode(word); return currentNode == null ? 0 : currentNode.end; } /** * 搜索该前缀树中由多少个以某字符为前缀的字符串数量 * * @param word * @return */ public int searchPre(String word) { TrieNode currentNode = searchEndTrieNode(word); return currentNode == null ? 0 : currentNode.pass; } public TrieNode searchEndTrieNode(String word) { if (word == null) { return null; } TrieNode currentNode = root; int index = 0; char[] chars = word.toCharArray(); for (char c : chars) { index = c - 'a'; if (currentNode.nexts[index] == null) { return null; } currentNode = currentNode.nexts[index]; } return currentNode; } public class TrieNode { public int pass; public int end; /** * 此处使用数组代办26个字符，若元素过多，也可以用下面的结构代替 */ //public TreeMap<Character, TrieNode> nexts; //public HashMap<Character, TrieNode> nexts = new HashMap<>(); public TrieNode[] nexts; public TrieNode() { this.pass = 0; this.end = 0; /** * nexts[0]:表示字母a对应连接的TrieNode * nexts[1]:表示字母b对应连接的TrieNode * ... * nexts[25]:表示字母z对应连接的TrieNode */ this.nexts = new TrieNode[26]; } } /** * 测试java中的有序TreeMap */ public static void main(String[] args) { HashMap<Character, Integer> treeMap = new HashMap<Character, Integer>(); treeMap.put('b', 2); treeMap.put('c', 1); treeMap.put('a', 3); treeMap.entrySet().forEach(item -> { System.out.println(item.getKey()); }); } }