字典树的应用与实现

字典树的应用与实现

字典树又称为单词查找树或者前缀树,是一种用于快速检索的树形结构,比如小写字母词典数是一个26叉数,数字的字典树是一个10叉数。字典数的键并未保存在节点中,而是由节点在树中的位置决定的。 根节点一般对应空信息。字典树的优点是查询效率高,其核心思想是利用空间换时间,利用字符串的公共前缀来提高效率

字符串的最小包含子串

问题 给定字符串str1,str2,获取字符串str1中包含str2的最小字符子串。 str1=“abcde”, str2=“bd” -> bcd str1=“abcde”, str2=“cg” -> “” 思路 假定字符编码范围0~255 创建一个size为256的整形数组charCount,用来保存字符串str2所有字符的出现次数 整形变量match用来表示当前差几个字符未匹配 将str1、str2分

判断两个单词是否为变形词

问题 给定两个单词word1,word2,判断两个单词是否是变形词,即两个单词中的每个字符出现的次数一致。 word1=“abcc”, word=“acbc”, 返回true word1=“abcc”, word=“abbc”, 返回false word1=“abc”, word=“cba”, 返回true 思路 假定字符串的编码范围0~255。 新建一个size为256的int数组 分别将单词word1、word2转换为对应的字符数组word1C

从数组中获取指定数量的随机元素

问题 从给定的一个整型数组中,随机获取指定数量的数组元素。 思路一 新建一个与整型数组相同长度的boolean类型数组用来做标志位,标志位值为true表示当前元素是否已经获取,如果数组元素未被获取,则取出该元素,同时把对应的标志位置位true,如果发现当前元素已经获取,则重新随机获取。 public static int[] get(int[] array,