O(n)的大O是什么意思？什么是时间复杂度?
大O符号，又称为渐进符号，是用于描述函数渐近行为的数学符号。
更确切地说，它是用另一个通常更简单的函数来描述一个函数数量级的渐近上界。
O(n)这个大O表示的是最坏情况下的时间复杂度。
时间复杂度：一个用于度量一个算法的运算时间的一个描述，本质是一个函数，它描述的只是代码执行时间随数据规模增长的变化趋势
空间复杂度：度量一个算法在计算机内执行时所需的存储空间，它也是数据规模n的函数
解释一下顺序存储与链式存储
顺序存储结构把逻辑上相邻的元素存放到物理位置上相邻的存储单元中，数据元素之间的逻辑关系由存储单元的邻接位置关系来体现。
链接存储方法不要求逻辑上相邻的元素在物理位置上也相邻，元素之间的逻辑关系由附加的指针指示。
线性存储结构和链式存储结构的优点、缺点
线性存储结构：
优点：地址空间连接，可快速的存取表中的任一位置元素；无需为表示表中元素之间的逻辑关系而增加额外的存储空间。
缺点：插入和删除操作需要移动大量元素；当线性表长度变化比较大时，难以确定存储空间的容量；容易造成存储空间碎片。
链式存储结构：
优点：不要求逻辑上相邻的元素在物理位置上是相邻，节省空间，不会出现空间碎片；插入和删除数据快速，只用更改指针域。
缺点：存取元素慢，不支持任意存取的，需要从头走到尾。
头指针和头结点的区别？
以单链表为例，
头指针就是指向链表第一个结点的指针，链表的第一个结点的地址可以通过链表的头指针找到，对单链表中任一元素的访问必须首先根据头指针找到第一个结点。头指针为NULL时表示一个空表。
而头结点是一个附加结点，头结点的data域可以不存储任何信息，也可以存放特殊标志或表长，单链表带头结点时，头指针会指向头节点。
头结点的存在可以优化单链表的增删操作，使得对于空表或者在非空表第一个结点之前插入不用作为特殊情况专门处理，而是使用通用方法。
链表反转
头插法：建立一个新的链表头，遍历原链表，将每个节点插到新链表头的前面
迭代法——三指针：定义cur（指向当前链表的头）、nextnode（保存cur的next节点）、prev（表示链表最后的节点，指向空）；
栈和队列的区别
栈：后进先出，只允许在表的末端进行插入和删除的线性表，允许插入和删除的一端叫做栈顶，不允许插入和删除的一端叫做栈底。
队列：先进先出，只允许在表的一端插入，在另一端删除的线性表。允许插入元素的一端称为队尾，允许删除的一端称为队首。
栈和队列的内存结构
均分为基于数组的顺序存储结构和基于链表的链式存储结构
栈：
顺序存储结构：存放栈中元素的数组、栈顶指针、最大容纳元素个数
链式存储结构：栈顶指针
队列：
顺序存储结构：利用一个一维数组作为存储结构，并设置头指针和尾指针两个指针来指示队首和队尾的位置。
链式存储结构：由队首指针和队尾指针构成。
数据结构中的栈和计算机里的栈有什么不同
数据结构中的“栈”是一个概念，是逻辑存在的，是管理数据的一种手段和方法。
计算机操作系统中的栈是指一块内存区域，该区域的管理(内存空间的分配与回收)采用类似数据结构中“栈”的特点进行操作。操作系统中的栈是物理存在的，是对数据结构中的栈这种手段的实现。
无论哪一种栈，都遵循“后进先出”的特点。
有一个循环队列Q，里面的编号是0到n-1，头尾指针分别是f，p，现在求Q中元素的个数？
(p-f+n)%n
如何区分循环队列是队空还是队满？
front表示队头指针（指向队列内首元素）
rear表示队尾指针（指向队列内尾元素的下一个位置）
m表示队列的容量（包括那个留空的位置）
方式一：牺牲一个空间
队空：front=rear
队满：front=(rear+1)%m
队内元素个数：（rear-front+m）%m
方式二：设置tag变量
Tag=-1，有数据出队，tag=1时有数据入队。这样rear==front时tag=-1，则为空，tag=1时则为满。
如何判断链表是否有环？
快慢指针：用一个快指针、一个慢指针。
快指针一次走两步、慢指针一次走一步，当快指针追上慢指针时，就说明有环。
如何找到环的起点？
再用一个慢指针从头开始遍历，直至两个慢指针相遇，这个相遇点就是环的起点。
为什么是两步和一步？
有无其他方式？
哈希表。
穷举法，每到一个节点就遍历它前面的节点。
树、二叉树、满二叉树、完全二叉树、二叉搜索树（二叉排序树）、平衡二叉树、最优二叉树（哈夫曼树）的区别及如何构造
树：没有回路的连通无向图
树的特性：
- 一棵树中的任意两个结点有且只有唯一的路径相连
- 如果一棵树有n个结点，那么它一定恰好有n-1条边
- 在一棵树中加一条边会构成一个回路
二叉树：树的每个父结点最多有两个子结点
满二叉树：树的非叶子结点都有两个子结点，即所有叶子结点的深度都一致
完全二叉树：假设二叉树的高度为h，则除了第h层外，其它所有层都达到最大结点数，第 h 层从右向左缺少若干结点。即某结点若含有右子结点，则一定含有左子结点
二叉排序树（二叉搜索树）：左子树的值小于根节点，右子树的值大于根节点，左右子树都是二叉搜索树。便于查找。且对二叉排序树进行中序遍历，即可得到从小到大的排序
二叉排序树的构造方法主要执行插入操作，进行插入之前必须先检查是否该节点的关键码已经在树中存在，也就是要先查找，假如查找成功，不执行任何操作，假如搜索不成功，就在搜索停止的地方添加新元素。
平衡二叉树（AVL树）：一种特殊的二叉搜索树，左右子树的高度差不超过1，且左右子树都是平衡二叉树。
构造一棵平衡二叉树仍然是通过插入节点的方式，每插入一个结点，都应该检查平衡因子，并通过旋转操作使之平衡化。
最优二叉树（哈夫曼树（Huffman Tree））：给定N个带权的叶子节点，构造的带权路径最小的二叉树。可以发现，权值较大的节点离根较近。
每次选择两个最小权值的节点作为左右子树，他们的根节点权值为这两点相加，如2+4=6
用途：构造 霍夫曼编码（Huffman Code）
如果字符出现的频率不同，让频率高的字符采用尽可能短的编码，频率低的字符采用尽可能长的编码，来构造出一种 不等长编码，从而获得更好的空间效率。
规定哈夫曼编码树的左分支代表 0 ，右分支代表 1 ，则从根结点到每个叶结点所经过的路径组成的 0 、1 序列即为该叶结点对应字符的编码
如何由遍历序列构造一颗二叉树？/已知先序序列和后序序列能否重现二叉树？（笔试经常考）
若是中序和先序或者中序和后序，则可。
首先先序中我们可以锁定当前第一个点为根，中序中找到这个点，去把子树分割成左子树和右子树两个部分，再依次递归下去即可
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
先序和中序不能重现一颗唯一的二叉树。但有可能找出满足此的二叉树。
前序、中序、后序遍历 层次遍历
中序：左孩子->根节点->右孩子
前序：根节点->左孩子->右孩子
后序：左孩子->右孩子->根节点
B树和B+树的区别
B树：多路平衡查找树，能够保持数据有序，够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。
m 阶的 B 树，m表示这个树的每一个节点最多可以拥有的子节点个数。
特点：在存储同等数据量的情况下，平衡二叉树的高度一定大于B树高度。
B+ 树是 B 树的一个升级，它比 B 树更适合实际应用中操作系统的文件索引和数据库索引。
B+树和B树有两个区别：
① B+树内部有两种结点，一种是索引结点，一种是叶子结点。B+树的索引结点并不会保存记录，只用于索引，所有的数据都保存在B+树的叶子结点中。而B树则是所有结点都会保存数据。
B+树的叶子结点都会被连成一条链表。叶子本身按索引值的大小从小到大进行排序。即这条链表是从小到大的。因此可以直接通过遍历链表实现范围查找。
② B树的子树数量为关键字（元素）数量+1，B+树的子树数量为关键字数量。
B树在数据库中有什么应用？
用途：在数据库查询中，以树存储数据。树有多少层，就意味着要读多少次磁盘IO。所以树的高度越矮，就意味着查询数据时，需要读IO的次数就越少。（众所周知，读IO是一件费事的操作）当数据量大的时候，用AVL树存的话，就算AVL是平衡树，但是也扛不住数据量大，数据量大，AVL树的树高肯定很高，那么读取数据的IO次数也会多。B树的一个结点可以装多个值，读取时，是把整个结点读到内存，然后在内存中，对结点的值进行处理，在内存中处理速度肯定比磁盘快。所以只要树的高度低，IO少，就能够提升查询效率，这是B树的好处之一。
B树的缺点是：不利于范围查找(区间查找)，如果要找 0~100的索引值，那么B树需要多次从根结点开始逐个查找。
B+树在数据库中的应用？ 为什么索引结构默认使用B+树，而不是B-Tree，Hash哈希，二叉树，红黑树?
Mysql的索引结构默认使用B+树，B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n
范围查询很高效，例如查找区间[a, b]，从根节点开始寻找值为a的叶子节点，之后遍历链表，直到找到b
Hash哈希索引等值查询速度最快，但不支持范围查询
二叉树在极端情况下可以退化成链表，效率低下
红黑树原理是什么？建立过程？
红黑树：一种特殊的二叉搜索树。在每个节点上增加一个存储位置表示节点的颜色，red/black。 复杂度O(lgn)
红黑树通过如下的性质定义实现自平衡：
- 节点是红色或黑色。
- 根是黑色。
- 所有叶子都是黑色（叶子是NIL节点）。
- 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）。
对节点的着色方式有5条限制。红黑树确保没有任何一条路径会比其它路径长出两倍，是接近平衡的，他的节点插入、删除效率较高
堆、大顶堆、小顶堆实现及应用
堆是一种特殊的完全二叉树
小顶堆：父结点的值小于其子结点
大顶堆：父结点的值大于其子结点
堆排序：时间复杂度O(NlogN)。例如从小到大排序，建立小顶堆，每次输出第一个结点的值并删除该结点，剩下的结点重新排序。
哈希表的概念、构造方法、哈希有几种类型？
哈希表：哈希表（Hash Table）又称散列表，是一种数据结构。它含有key-value键值对。
它通过散列函数将key映射到内存空间的某个位置，将键值对储存在这里。所以哈希表的本质是数组。可以由数组+链表/数组+二叉树实现。
构造方法：
- 直接定址法：
Hash(key)=a * key+b (a、b为常数)
优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突。
缺点：要占用连续地址空间，空间效率低。
- 除留余数法:
Hash(key)=key mod p (p是一个整数)
特点：以关键码除以p的余数作为哈希地址。
关键：如何选取合适的p？
技巧：若设计的哈希表长为m，则一般取p≤m且为质数(也可以是不包含小于20质因子的合数)，这样可以减少冲突的发生
- 数字分析法:
特点：某关键字的某几位组为哈希地址。
所选的位应当是：各种符号在该位上出现的频率大致相同。不太常用，除非非常有规律。
- 平方取中法:
特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址
理由：因为中间几位与数据的每一位都相关
例：2589的平方值为6702921，可以取中间的029为地址
- 折叠法:
特点：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。
适用于：每一位上各符号出现概率大致相同的情况
- 随机数法:
Hash(key) = random(key) (random为随机函数)
适用于：关键字长度不等的情况，造表和查找都很方便
哈希表便于查找，复杂度是O(1)
哈希冲突的解决办法？
为了解决冲突（即不同的 key映射到了同一个存储位置），可以使用
开放地址法(再散列法)：即该位置已经被前个key占用了，则这个key排到紧邻的下一个存储单元中
链地址法（HashMap 采用的这个方法）：每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
再哈希法 Rehash：有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。
建立一个公共溢出区：在创建哈希表的同时，再额外创建一个公共溢出区，专门用来存放发生哈希冲突的元素。查找时，先从哈希表查，查不到再去公共溢出区查。
二分搜索和单纯的线性搜索的区别/时间复杂度
线性搜索：O(n) 遍历范围内的所有数据，找到与key相同的数据。
二分搜索：O(logn) 需要待搜索数据有序排列，每次将搜索区间一分为二，与中间的数字进行比较，并依据比较结果选择左区间或者右区间。
冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等排序算法的基本思想是什么？时间复杂度？是否稳定？
选择排序：
时间复杂度O()，不稳定
每趟在未排序的元素中直接选择最大的元素，放到未排序数的尾端，进行n-1次。
冒泡排序：
时间复杂度为O()，稳定
每趟比较相邻两个元素大小，每趟会将最大的数放到未排序数的尾端，会进行n-1趟。
插入排序：
时间复杂度O()，稳定
插入排序（英语：Insertion sort）是一种简单直观的排序算法。它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。
计数排序 Counting sort：
时间复杂度是O(n+w)，w表示待排序数据的值域大小，稳定
非比较类的排序算法。它首先找到最大和最小值，统计所有数的出现次数，存到另一个数组中，然后依次顺序填充回原数组。
基数排序 Radix sort：
时间复杂度O(n)，稳定
按照个位、十位、百位排序。
快速排序：
时间复杂度O(nlogn)，不稳定
通过分治的方式来将一个数组排序。每次遍历会设置一个基准值来将数组分为两个子数组，遍历后，左边的数均比该数小，右边的数均比此数大，随后通过递归方式对子数组进行排序。
Quicksort is an in-place sorting algorithm. it is still a commonly used algorithm for sorting. Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.
归并排序 merge sort：
时间复杂度nlog(n)，稳定
分治思想。将待排序元素分成若干个子序列，使其有序后合并。
MergeSort is a typical application of Divide and Conquer. It is an effective algorithm with a nlgn time complexity and it is stable but not in place. Merge sort is a good choice for external sort. The basic step of the algorithm is to merge the ordered subsequences into a complete ordered sequence.If two ordered subsequences are merged into one, it is called two-way merge.
堆排序 heap sort：
时间复杂度O(nlogn)，不稳定
堆排序的本质是建立在堆上的选择排序。
首先建立大顶堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质；
之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质；
以此类推，在第n-1次操作后，整个数组就完成了排序。
桶排序 Bucket sort：
时间复杂度O(n)，如果使用稳定的内层排序，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法。
将处于某区间的数放入各个桶中，然后对桶中的数字排序。
希尔排序：
时间复杂度O()，不稳定
希尔排序是一种改进的插入排序算法，通过分组比较相距一定间隔的元素，逐步减小间隔，最终实现排序。
给一个例子，问冒泡和快速排序在最坏的情况下比较几次？（排序必考）
冒泡排序最坏情况：如4,3,2,1升序排序，需要比较 3+2+1=6=4*3/2 次
快速排序最坏情况：已经排好顺序的（包括升序、降序、所有元素都一样）
邻接表和邻接矩阵（如何存储大数据）
邻接矩阵的大小只与节点数量有关，即N^2，其中N为节点数量。因此，当边数量明显少于节点数量时，使用邻接矩阵存储图会造成较大的内存浪费。
- 邻接表适合存储稀疏图（顶点较多、边较少）
- 邻接矩阵适合存储稠密图（顶点较少、边较多)
介绍一下字符串匹配算法：朴素的匹配算法和KMP算法。（如何实现要会用语言描述）
朴素的：暴力求解。对主串的每一个字符作为模式串的开头，依次于模式串进行匹配。每次匹配不成功，主串字符后移一位，直至匹配成功或者全部遍历为止。
KMP：每次匹配失败后模式串不必完全回退，找已经成功匹配成功的模式串的子串，找其相同的最大前缀和最大后缀（小于该字串长度），然后将模式串直接后移到后缀的位置开始新的匹配。这里的后移就是便于解释，真正实现的时候是通过数组的下标来进行操作。
介绍一下深度优先搜索和广度优先搜索是如何实现的？
深度优先：沿着一条路径不断向下搜索，直至不能继续再折返，搜索下一条路径。
广度优先：根据离起点的位置，从近至远地对各节点搜索。
基本思想是：首先访问起始顶点v，接着由顶点出发，依次访问v的各个未访问过的邻接顶点， 在从这些顶点出发依次访问未被访问过的他们的邻接顶点…..直至所有顶点都被访问过为止。若此时仍有顶点未被访问，则从剩下的未被访问的顶点中选取一个作为起始点，重复上述过程，直至图中所有的顶点都被访问到为止。
最小生成树用什么算法来实现？算法的基本思想是什么？算法的时间复杂度？如何进行优化？
图的最小生成树：一个不包含回路的连通无向图
Kruskal和Prime算法时间复杂度均为
Kruskal算法（贪心）
一步步将森林中的树合并，适用于稀疏图（因为时间复杂度与边数有关系）
按边的权值进行从小到大排序，每次从剩余的边中选择权值较小且两个顶点不在一个集合的边（即不会产生回路），加入生成树中。
优化：使用最小堆来存放边的集合，这样每次选择最小权值边只需要O(log E),时间复杂度为O(ElogE)
Prime算法（贪心）
通过每次增加一条边来建立一棵树，适用于稠密图
将顶点分为两类：树顶点（已被加入生成树的顶点）和非树顶点（未被加入生成树的顶点）。首先任意选择一个顶点加入生成树，然后找一条边加入生成树（需枚举每一个树顶点到非树顶点所有边，找到最短边加入树），时间复杂度为O()
优化：使用邻接表储存图，时间复杂度降至O(NlogN)
最短路径用什么算法来实现？算法的基本思想是什么？算法的时间复杂度？如何进行优化？
多源最短路径：任意两点的最短路径
单源最短路径：一个源点到其余各个顶点的最短路径
① Floyd弗洛伊德算法（多源最短路径）（动态规划）
c(i, j, k) 表示从顶点i到顶点j的最短路径的长度，其中该路径允许经过的顶点都不大与k
上式表示 min { 路径不含中间顶点k ， 路径含中间顶点k }
即：最开始只允许经过1号顶点中转，接下来只允许经过1号顶点和2号顶点中转……允许经过1-n号顶点中转。i→j的距离可以被优化成经过中间点k,i→k→j
② Dijkstra算法（单源最短路径）（贪心）普通Dijkstra是，堆优化的Dijkstra是
贪心策略（选当前的最小边），每一次选择dis数组中最小的边，当选择一个小边后，把小边另一端的顶点M遍历过后，就不再更新源点到M的最小距离（一次选定，不再回头）而实际上可能大边+负边优于小边，（贪心不是最优）
核心思想是每次选择离源点最近的点，并以此点进行扩张，得到源点到其余点最短路径
具体为，它将所有顶点分为两部分：已知最短路径点集P和未知最短路径点集Q。每次在Q中选择一个离源点最近的点u，找到它的所有出边，做松弛操作。意思是，假如存在从u到v的边，那么比较从源点到u再到v的总路径长度，与s到v路径长度的大小，如果小则替代原路径长度。在对u的所有出边做松弛操作后，将u放入已知最短路径集P。
详细步骤：
①将顶点分为已知最短路径的顶点集合P（book[i]=1）和未知最短路径的顶点集合Q（book[i]=0），最开始只有源点在P中
② 初始化最短路径数组dis[s]。源点为0，dis[i]为e[s][i]，其余为∞
③ 在Q中所有顶点选择距离s最近的顶点u（即dis[u]最小）加入P。对u的出边做松弛操作，比较dis[u]+e[u][v]和已知dis[v]大小。小则替代。直至Q为空，结束算法。dis数组是最短路径结果
③ Bellman-Ford算法（单源最短路径，解决带权负边）
贪心、动态规划、分治
贪心（自上而下）：指在对问题求解时，采用某种贪心策略，总是做出在当前看来是最好的选择，也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
分治：将原问题分解为n个规模小，和原问题类似的子问题，通过子问题的解合并为原问题的解。
动态规划（自下而上）：动态规划是一种多阶段最优解模型，一般用来求最值问题，多数情况下可以采用自下而上的递推方式来得出每个子问题的最优解（即最优子结构），进而自然而然地得出依赖子问题的原问题的最优解。
动态规划三要素：最优子结构、状态转移方程、重叠子问题
什么是拓扑排序
在图论中，拓扑排序（Topological Sorting）是一个有向无环图的所有顶点的线性序列。且该序列必须满足下面两个条件：
- 每个顶点出现且只出现一次
- 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
如何用两个栈实现队列
假设初始两个栈为空；一个栈A用于维护push数据，另一个用于维护pop数据；当需要push的时候，直接添加到栈A的顶端即可；如果要pop，直接从栈B弹出数据，但是如果栈B为空，则需要将A中所有的对象，依次弹出存入B中，然后再进行pop
如何用两个队列实现栈
假设初始两个队列为空，维护一个存入元素个数的变量n；当需要push元素的时候，直接加入到非空的队列（都为空就任加一个）；当需要pop元素的时候，将非空的队列依次取出前n-1个元素，存入另一个空队列，然后将第n个元素取出即可，如此反复
m 叉树，度为 Ni 的结点有 i 个 (i=1,2,…m)，问度为 0 的结点有多少个？
这里对树的节点的度的定义，与离散数学图论中对图的度的定义不同，指的是每个节点子节点的数目
叶子结点数目 = 总度数 - 非叶子节点数
NP-hard问题
P类问题:(polynominal) 存在多项式时间算法的问题，即在多项式时间内可解的问题；例如：冒泡排序、快速排序等问题；
NP类问题:(Nondeterministic polynominal) 能在多项式时间内验证出一个正确解的问题，也就是说这个问题不一定在多项式时间内可解，但可以在多项式时间内验证；
NPC类问题（Nondeterminism Polynomial complete）存在这样一个NP问题，所有的NP问题都可以约化成它。
NP-Hard类问题（Nondeterminism Polynomial hard）所有的NP问题都可以约化成它。
约化(Reducibility)
定义是，如果能找到一个变化法则，对任意一个A程序的输入，都能按照这个法则变换成B程序的输入，使两程序的输出相同，那么我们说，问题A可以约化为问题B。一个问题A可以约化为问题B的含义是，可以用问题B的解法解决问题A。
举例：旅行商问题，0-1背包，最大割，最小顶点覆盖问题
