搜索引擎的搜索关键词提示功能不用讲了吧,相信大家都用过.那么他是如何实现的呐?今天就来说一说它底层最基本的原理:Trie 树 什么是“Trie 树”? Trie 树,也叫“字典树”。顾名思义,它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。 当然,这样一个问题可以有多种解决方法,比如散列表、红黑树,或者一些字符串匹配(KMP,BM)算法,但是,Trie 树在这个问题的解决上,有它特有的优点。不仅如此,Trie 树能解决的问题也不限于此,我们一会儿慢慢分析。…

2019年1月26日 0条评论 0点热度 阅读全文

文章目录 题目链接 题目描述 示例 解析 代码 题目链接 Problem.110:https://leetcode.com/problems/balanced-binary-tree/ 题目描述 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 输入1: [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 输出1: true 输入2: [1,2,2,3,3,null,null,4…

2019年1月11日 0条评论 0点热度 阅读全文

我们在使用搜索引擎进行搜索时,会发现当我们输入一部分内容后,搜索引擎会弹出很多关键词提示,如果发现有你要查找的内容,你可以直接选中它进行搜索,一定程度上节省了我们的时间。究竟如何实现这种功能呢,它使用的底层数据结构和算法是什么呢? 没错,就是今天要说的Trie树。 Trie树 也叫“字典树”,根据它名称,它本身就是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找字符串的问题。那Trie树究竟有何特殊之处呢,它是通过字符串之间的公共前缀,将重复的前缀合并在一样,并组织成一棵树。 …

2019年1月10日 0条评论 0点热度 阅读全文

一、进制转换基础 二进制转为十进制: 把二进制数的各个位拆开,分别乘以2的次幂再累加。末尾位乘2的0次幂,依次类推。  比如:1011 十进制=1*2^3+1*2^2+1*2^1+1*2^0 =11.   十进制转为二进制 除k取余法:主要用于把十进制的数化为k进制的数。 例如: 把89化为二进制的数 89÷2=44 余1 44÷2=22 余0 22÷2=11 余0 11÷2=5 余1 5÷2=2 余1 2÷2=1 余0 1÷2=0 余1 然后把余数由下往上排序 1011001(2) 这样就把8…

2019年1月8日 0条评论 0点热度 阅读全文

字符串匹配KMP算法 KMP算法的流程 假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符; 如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。一直回溯到匹配或者-1; next数组的含义 next 数组各值的含义:代表当前字符之前的字符串中,有多大长度的相同前缀后缀。 例如如果next [j] = k,代表j 之前的字符串中有最大长度为k…

2019年1月5日 0条评论 0点热度 阅读全文

4、两大集合接口 在Java集合中,有两大集合,一个是Collection接口及其实现类,另一个是Map接口及其实现类。下面给出这两种集合的框架图。如下所示。 4.1Collection接口框架图 4.2Map接口框架图 从上面两个框架图可以看出,Cllection接口和Map接口是两大顶层接口。二者最为显著的区别是:Cllection接口的实现类及其子类的元素都是单一的,不可分割的元素,而Map接口的实现类及其子类的元素key-value键值对映射型的元素,其元素可以分成键和值。集合在数据的增删改查应用中具有十分…

2018年12月31日 0条评论 1点热度 阅读全文

前缀树 Trie 1 什么是Trie树 Trie树,又叫字典树 前缀树 单词查找树 键树 是一种树形结构,是一种哈希树的变种 是一种多叉树. 1.1 基本性质: 根节点不包含字符. 除了根节点之外,每个子节点包含一个字符. 从根节点到某一节点,路径通过经过的字符连接.为该节点对应字符串 每个节点的所有子节点包换的字符互不相同 通常,会在节点结构中设置一个标志,用来标记该结点处是否构成一个单词(关键字). 2 Tire树的优缺点 Tire树的核心思想是通过 空间来换时间. 利用字符串的公共前缀来减少无谓的字符串比较 …

2018年12月22日 0条评论 0点热度 阅读全文

java进制转换(十进制转八进制,十进制转二进制,十六进制转八进制) 这几天在复习C语言的数据结构栈和队列那一章的时候,看到利用栈的特性FILO实现的进制转换十分简洁 想起了java中实现栈的操作十分方便(不用自己写.h文件,内部util.Stack包已经封装好) 所以用这个来写一个进制转换作为记录 十进制怎么转化为二进制呢? public void Dex2Bin(int n){ int x; Stack<Integer> stack = new Stack<>(); while(n>…

2018年12月19日 0条评论 0点热度 阅读全文

友情链接: https://blog.csdn.net/zgqj1/article/details/82859102

2018年12月17日 0条评论 0点热度 阅读全文

//图的深度优先遍历 void DFS(int v, ALGraph *G) {     visited[v] = true;     printf("%d ", G->adjlist[v].data);                //访问     ArcNode *p = G->adjlist[v].first;  &n…

2018年12月14日 0条评论 0点热度 阅读全文