数据结构及算法知识1.字典树构造及其优化与应用字典树的核心就是空间换时间，利用字符串的公共前缀来避免无谓的字符串比较，降低查询时间性质：- 根结点不包含字符，除了根结点每个结点都包含一个字符- 从根结点到某一结点的路径经过的字符连接起来就是该结点对于的字符串- 查询和建树可以同时进行有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。

返回频数最高的100个词。

思路：首先要求得每个词的频率，1G无法放入内存，需要分成多个小文件，对每个小文件的词进行统计（1）散列分治：顺序读取文件，对每个词，可以hash(x)P00(只要不小于1024个文件，是为了保证每个小文件可以放入内存)，这样被映射为5000个小文件，每个文件大概200K，每个文件最少1250个单词（2）对于每个小文件，利用hash_map/字典树记录每个单词出现的频率，（3）用100个元素的最小堆，选出每个文件中的频率最大的100个单词（4）对这5000个小文件进行归并排序，选出最大的100个。

2.大规模文本文件，全是单词，求前10词频的单词（Top k问题是热门问题）3.如何判断时间，空间复杂度是否为O（logn）最直观的判断就是程序中采用了二分，且二分后只运算数据的一半。

但如果两部分都运算的话，时间复杂度就是O(nlogn)了。

其实不一定是二分，只不过二分比较常用罢了4.各个算法的时间和空间复杂度5.M个有序链表取前k大个元素6.红黑树的调整红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍1.每个节点要么是红色，要么是黑色。

2.根节点必须是黑色3.红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。

4.对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。

在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的条件。

调整可以分为两类：一类是颜色调整，即改变某个节点的颜色；另一类是结构调整，即改变检索树的结构关系。

结构调整过程包含两个基本操作：左旋（Rotate Left），右旋（RotateRight）。

红黑树是一种自平衡二叉查找树。

它对于二叉树有了“颜色”上的限制，我们可以看下它的五点性质：1.树中的结点是红色或黑色。

2.根结点是黑色。

3.空结点(NIL)为叶子结点，并且为黑色。

4.红结点的子结点一定是黑色结点。

5.从一个结点到该结点的叶子结点的所有路径上包含相同数目的黑结点。

如果空结点的父结点是红色结点时，那么空结点的兄弟结点一定也是空结点。

通俗点说，红结点下面一旦出现空结点就是两个，不会出现黑+空，或者红+空的情况。

如果是黑+空，那么违反了性质5，如果出现红+空，那么违反了性质4.如果空结点的父结点是黑结点时，那么空结点的兄弟结点一定不是黑结点。

一样的道理，如果出现了黑+空，就会违反性质5。

总结一下，红黑树最底层只会出现两种情况，一种是底层两个都是空结点，另外一个是父结点为黑结点，子结点一个红色，一个为空，并且该红结点的两个子结点都是空。

增加结点实际上可以看作先对该结点进行查找，如果存在，就把该结点的值更新，如果不存在，就在查找到最后返回时的空结点位置处增加该结点。

对于红黑树而言，我们需要在增加完结点后，对这个树的结构进行一些调整，使树满足红黑树条件。

首先，为了算法的简便，我们默认插入的是红结点，因为，红结点的增加，不会改变树中的黑色结点数，即不会影响性质5。

现在考虑插入的情况，从我们上节中总结的规律可以看出，在树的最底层只有3种情况，其中父亲结点为黑时，你可以在下面直接插入红结点，不需要做出任何改变。

因为黑色结点下面是可以有红色的，不违背红黑树的任意一条规则。

所以，只有一种情况需要进行结构调整，那就是父节点为红，并且此时插入结点的兄弟结点为空。

对于删除操作，实际上就是找到待删除结点的后继结点，然后把后继结点删除，并把后继结点的值给到删除结点。

7.贪心算法与其弊端8.判断一个链表是否有环，如何找到这个环的起点剑指offer的题目，利用快慢指针是否会相会来判断是否有环，如果快指针都跑到结尾了还没碰到慢指针则无环。

先让快慢指针跑，当快慢指针相交的时候一定是在环中，那么这个时候再让慢节点跑，再次和快节点相会的时候，走过的长度就是环的长度len，这个时候定义两个速度一样的指针，指针1先跑len，这时指针2再从起点跑，两指针相交的地方就是环的起点。

9.红黑树在STL上的应用avl用于搜索，插入删除次数少场景，用在win的内核中很多；红黑：查找，用在STL中map set，java 中的treemap，linux进程调度公平调度用于管理进程控制块；B/B++用于文件系统、数据库中做索引。

10.动态规划的原理与本质（动态规划dynamic programming是笔试热门题型）根据状态转移方程和临界条件，要求全局最大解，动态规划的本质也是通过分治的方法将大问题分解成小问题。

11.统计二进制中1的个数12. 背包问题的详细解释动态规划，建表，保存之前的最优状态。

13.大数量整数的去重问题14.算法题：环形公路上加油站算法问题（此题比较经典，可百度到）15.实现bitmap数据结构，包括数据的存储与插入方式16.实现unordered_map，键为string，value不限17.实现unordered_map过程中的冲突解决办法18.字符串hash成状态位的具体实现方式19.Epoll怎么实现的？通过epoll-create系统调用eventpoll类型的句柄，其中包括红黑树节点和双向链表头结点，通过epoll-ect系统调用，向epoll中添加，删除，修改感兴趣的事件，返回0表示成功，返回-1表示失败，最后通过epoll-wait系统判断双向链表是否为空，为空则阻塞，当文件状态符改变时，fd上的回调函数被调用，将fd加入到双向链表中，此时epoll-wait被唤醒。

20.hash函数如何保证冲突最小解决hash冲突的方式，1.链址开放法，2.拉链法21.算法题1：给定有序数组，取前面某段调整到最后，即进行一次旋转操作后，对任意元素进行快速查询。

敲代码不运行22.算法题2：n对括号正常匹配情况的枚举输出。

敲代码不运行23.算法题1：无序数组查找第Top k元素。

手写代码实现24.算法题2：并查集。

手写代码实现https:///UFv59to8/article/details/78466907这个博客并查集讲的很好25.算法题3：链表反转。

手写代码实现26.算法题1：枚举给定数组中的所有非递减子序列27.算法题2：枚举给定数组的全排列28.算法题1：给定二叉树，假设相连接的两结点间距离为1，求所有结点中距离其他所有结点距离和最小的结点。

29.算法题1：给定数组，快速求出所有数右边第一个比其大的数30.算法题2：给定k个数组，每个数组都是有序的，且每个数组最大值-最小值<1000，1<k<1000，求所有数的中位数。

31.红黑树的了解与其查找复杂度（红黑树的特性和复杂度是热门问题）32.快速排序的优化1.优化一：三数取中法，解决数据基本有序的（就是找到数组中最小下标，最大下标，中间下标的数字，进行比较，把中间大的数组放在最左边）2.优化二：随机选取基准引入的原因：在待排序列是部分有序时，固定选取枢轴使快排效率底下，要缓解这种情况，就引入了随机选取枢轴，思想：取待排序列中任意一个元素作为基准3.优化三：优化小数组的交换，就是为了解决大才小用的问题，原因：对于很小和部分有序的数组，快排不如插排好。

当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排4.优化四：在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割具体过程：在处理过程中，会有两个步骤第一步，在划分过程中，把与key相等元素放入数组的两端第二步，划分结束后，把与key相等的元素移到枢轴周围33.字符串匹配算法KMP算法（没看懂，就了解了是一段字符进行匹配）34.游戏中打怪时已经各个小怪的坐标，你放一个技能是圆形范围，快速求能打到的小怪（范围搜索问题，热门场景考察题）35.魔兽世界10人房间，现在组队规模有3人，有5人，如何让每个人等待的时间尽可能少，即将时间线上哪些队伍组合在一起开始一个游戏（01背包问题的应用题）36.快速排序的稳定化算法（此方法可百度到）37.算法题：平面上百万个点，设计数据结构求每个点最近的k个点（范围搜索问题）38.判断二叉树是不是镜像，手写翻转二叉树39.算法题：字符串转整数，敲代码40.手写二叉树最近公共祖先41.手写层序遍历二叉树并输出结点层数42.手画字典树对每一个节点而言，从根节点到它的路径就是一个单词，如果该节点被标记为红色则说明该单词存在。

以第一节定义的时间单位为准，从查找效率来看，假设将文章读入字典树后，在每一个单词的末字母节点上标记上它出现的次数，则后续查找一个单词出现的总次数所花费的时间仅是O(d)。

从存储空间上来看，第一节的三种结构都需要存储所有的单词，比如ab、abc、abde三个词需要存储所有单词的所有字母共9个字母，而字典树则可以利用相同前缀的单词共享前缀空间的特性，只需要存储5个字母。

所以无论从时间效率还是空间容量来说，字典树对于大量字符串数据的处理都是优于一般的数据结构的。

43.介绍更高效的建树判重数据结构44.范围搜索算法（仍然是这个热门场景题45.算法题：n乘m的矩形填充到N乘M的矩形中能否填充满问题46.算法题2：快速排序47.二叉树的遍历1.先序遍历非递归先序遍历算法基本思路：使用堆栈a. 遇到一个节点，访问它，然后把它压栈，并去遍历它的左子树；b. 当左子树遍历结束后，从栈顶弹出该节点并将其指向右儿子，继续a步骤；c. 当所有节点访问完即最后访问的树节点为空且栈空时，停止。

2.中序遍历48.动态规划与贪心算法的区别与联系动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解不同点：贪心算法：1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。

2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。

动态规划算法：1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解3.边界条件：即最简单的，可以直接得出的局部最优解贪心算法典型问题：给钱问题。