线性表
-
问如果要对一个顺序表插入、查找都是O(logn)的复杂度，应该如何组织这个顺序表？
答：可以利用排序二叉树的思路，将顺序表组织成符合排序二叉树的结构的顺序表。
-
删除单链表中的重复值（时间复杂度：O(n^2)）
答：外循环当前遍历的结点为cur，内循环从链表头开始遍历至cur，只要碰到与cur值相同的结点就删除该结点cur，同时内循环结束，因为与cur相同的结点只可能存在一个（如果存在多个，在前面的遍历过程中已经被删除了）
-
判断链表是否存在环
- 对于这个问题我们可以采用“快慢指针”的方法。就是有两个指针fast和slow，开始的时候两个指针都指向链表头head，然后在每一步操作中slow向前走一步即：slow = slow->next，而fast每一步向前两步即：fast = fast->next->next。由于fast要比slow移动的快，如果有环，fast一定会先进入环，而slow后进入环。当两个指针都进入环之后，经过一定步的操作之后二者一定能够在环上相遇，并且此时slow还没有绕环一圈，也就是说一定是在slow走完第一圈之前相遇。
-
寻找链表中环的起点
- 从链表起点head开始到入口点的距离a,与从slow和fast的相遇点（如图）到入口点的距离相等。
- 我们就可以分别用一个指针（ptr1, prt2），同时从head与slow和fast的相遇点出发，每一次操作走一步，直到ptr1 == ptr2，此时的位置也就是入口点！
-
计算链表中环的结点个数
- 从相遇点开始slow和fast继续按照原来的方式向前走slow = slow -> next; fast = fast -> next -> next；直到二者再次相遇，此时经过的步数就是环上节点的个数 。
-
顺序表和链表的对比
- 存储密度：结点数据本身所占的存储量和整个结点所占的存储量。
- 存取方式：顺序表适用于查找操作较多的应用，任意一个结点都可以在O(1)时间内取得。
- 插入删除操作：顺序表平均要移动一半的结点。
栈
- 本质是一种线性表
- 中缀表达式
- 当前字符为数字字符，直接进栈
- 当前是左括号，直接进栈
- 当前是右括号云算法，连续弹出栈顶元素直到左括号。
- 如果当前是运算符，按照优先级弹出运算符栈顶较高级别的运算符。
- 链栈：head改成top
队列
- 只允许在一端进行插入，而在另一端进行删除的受限线性表。
- 循环顺序队列
- 队头指针：front，队尾指针：rear
- 模运算
- 判断是否为空：front==rear
- 判断是否已满：(rear+1)%queuesize==front
- 非循环链队
串
-
KMP算法：求next数组
static int []next=new int[1000006];
/*
* 求模板串的前缀数组
*/
public static void Pi(String s) {
int len=s.length();
next[0]=0;//第一个字符的
for(int i=1;i<len;i++) {
int j=next[i-1];
while(j>0&&s.charAt(j)!=s.charAt(i)) {
j=next[j-1];
}
if(s.charAt(i)==s.charAt(j)) {
j++;
}
next[i]=j;
}
}
矩阵
- 稀疏矩阵：三元组表顺序存储
- 计算稀疏矩阵的转置矩阵
- 该列非零元素的个数
- 该列第一个非零元素在三元组表中的序号
- 稀疏矩阵：采用十字链存储
- 列链表表头指针数组
- 行列表表头指针数组
- 同列后继指针
- 同行后继指针
树
完全二叉树
- n个结点的完全二叉树深度为：logn+1。
- 深度为k的二叉树最多有2^k-1个结点。
- 二叉树的叶子结点编号：n/2。下标大于等于n/2的结点都是叶子结点。
树相关算法
-
树的非递归中序遍历过程中，进栈的顺序对应前序遍历的顺序，出栈的顺序对应中序遍历的顺序。
-
写一个算法判断一个无向图是不是树。
答：一个无向图必须是无回路的连通图或者是n-1条边的连通图才能是一棵树。
bool GraphIsTree(Graph &G) {
for (int i = 0; i < G.vexnum; i++)
{
visited[i] = false;
}
int VNum = 0;
int ENum = 0;
//这里判断边时，把一条边分成两条有向边
if (VNum == G.vexnum&& ENum == 2 * (G.vexnum - 1))
return true;
else
return false;
}
//遍历树
void DFS(Graph &G, int v, int &VNum, int &ENum, int visited[]) {
visited[v] = true;
VNum++;
int w = FirstNeighbor(G, v);
while (w!=-1)
{
ENum++;//只要一个顶点有邻边，边数就加一
if (!visited[w])
DFS(G, v, VNum, ENum, visited);
w = NextNeighbor(G, v, w);
}
}
平衡二叉树和红黑树
一、AVL树性质
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。
如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理。
二、红黑树性质
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
1 节点是红色或黑色。
2 根节点是黑色。
3 每个叶节点（NIL节点，空节点）是黑色的。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
![技术分享图片]()
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(logn)，效率非常之高。
例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
三、两者的区别
- 红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构 能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。
- 红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。当然，红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。在实际的系统中，例如，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性，典型的用途是实现关联数组。
- AVL树是最先发明的自平衡二叉查 找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(logn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
中序穿线二叉树
- n个结点共有2*n个指针域，其中有n+1个空指针域。利用这些空指针域存放线索。
树的存储结构
- 顺序存储的双亲表示法：data+parent
- 孩子链表表示法：
- 孩子兄弟链表表示法
树/森林与二叉树之间的转换
- 所有兄弟结点之间加一条线
- 对每个结点，除了保留与其长子的连线外，去掉该结点与其他孩子的连线。
- 以第一棵树的根节点为旋转点，将修正后的树/森林旋转一定角度
- 前序遍历森林的序列等于前序遍历该森林对应的二叉树
- 后序遍历森林的序列等于中序遍历该森林对应的二叉树。
二叉搜索树
二叉搜索树的基本性质
- 二叉搜索树的前序遍历序列就是二叉搜索树的插入序列。
- 二叉搜索树的中序遍历就是排序后的序列。
图论
图的基础知识
- 简单路径：顶点p到q存在一条路径，顶点各不相同。
- 连通分量：无向图的极大连通子图。连通图的连通分量只有一个即其自身。非连通图的无向图有多个连通分量。
- 强连通图vs有向完全图（边数n^2-n）
最小生成树
- Prim算法：没有进入最小生成树的顶点，与当前最小生成树的距离最短的顶点。
- Kruskal算法：选择不同连通分量上的邻接的两个顶点
最短路
- Dijkstra算法：从剩余顶点选择最短路径值最小的顶点。修改剩余顶点的最短路径值。
- Floyd算法：
排序算法
插入排序
- 有序区：0-i，前半部分，当前元素和无序区元素比较，后移元素
- 反序的时间复杂度为\(O(n^2)\)，正序时间复杂度为：O(n)
- 稳定的排序
冒泡排序
- 稳定的排序
- 正序时间复杂度O(n)，逆序时间复杂度O(n^2)
- 有序区在后半部分，每次从头找到一个最大值放入数组的后半部分。每次符合条件的交换相邻元素的位置。
- 设置一个flag，如果一趟冒泡排序后元素符合大小关系，则无需进行后面的冒泡排序，已经有序了。
- 属于交换排序
快速排序
- 每趟排序确定一个基准的值，并且返回该值的位置即表示排序的序号
- 根据返回的序号，递归划分左右部分进行排序。
- 每次所取都是中值记录。如果已经有序，所花费的比较次数最多。
- 不稳定排序，栈空间最坏O(n)，最好O(logn)
- 时间复杂度：O(nlogn)，最坏\(O(n^2)\)
- 属于交换排序,elem[i]=elem[j],elem[j]=elem[i]
归并排序
- 自底而上：子文件两两归并，每次对于两个有序子文件的归并是依次遍历并且比较两部分当前元素值的大小。
- 自顶向下
- 时间复杂度最好和最坏都是O(nlogn)，需要logn趟二路归并，每次归并时间为O(n)
- 稳定的排序
选择排序
- 有序区在前半部分，每趟从未排序的元素中选择一个最小值，记录最小值下标，将该最小值插入到有序区的末尾。
- 不稳定的排序
- 时间复杂度最好和最坏都是O(n^2)，因为每趟都需要在未排序的元素里比较找到一个最小值。
堆排序
- 不稳定的排序
- 一趟堆调整：O（logn），建树：O(nlogn)，排序：O(nlogn)
- 建堆：从每个非叶子结点开始，进行堆调整
- 排序：每次选择堆顶元素放入无序区的首部，再进行堆调整，使树满足大根堆的性质。
希尔排序
- 不稳定的
- 设置一个增量，所有距离为该增量倍数的元素放在同一个组内，在该组内再进行直接插入排序。
- 在同组中把所有大于当前排序元素的都后移
- 属于插入排序
桶排序和基数排序
- 稳定的排序
- 分配和收集实现排序，无需关键字比较
- 设置箱子数为基数：10，按照低位到高位依次进行每趟排序。
- 使用了静态链表存储，设置一个next指针。front数组和end数组存放基数排序各队列的队头和队尾。
- 排序时间是线性的：O(n)
搜索查找算法
二叉排序树
- 删除：如果左右子树均不为空，在左子树中查找数据域最大的结点，该结点为左子树最右边的一个结点，而且该结点没有左子树。只需要把该最右结点的双亲指向它的指针修改为指向该结点的左子树，然后删除该结点即可。
平衡二叉排序树（AVL）
- LL型插入：非平衡结点的左子树的左子树上插入叶子结点
- LR型插入：
- 首先以非平衡结点的左子树的右子树根为轴，逆时针旋转
- 以非平衡结点的左子树根为轴，做顺时针旋转
- RR插入
- RL插入
哈希表
- 解决冲突
- 开放地址法：线性探测再哈希；二次探测再哈希；双哈希函数探查法；随机探测再哈希。
- 优点：
- 缺点：
- 开放地址法为减少冲突，要求装填因子α较小，故当关键字规模较大时会浪费很多空间。
- 对于开放地址法构造的哈希表，删除关键字不能简单将被删除关键字 的空间置空，否则将截断在它之后填入哈希表的同义词关键字的查找路径。（因为在开放地址法中，空地址单元都是查找失败的条件，故删除关键字只能在被删关键字上做删除标记，不能做物理删除。）
- 拉链法：将所有同义词的关键字链接在一个单链表中。（插入链尾）
- 优点：
- 平均查找长度相较于开放地址法更短。
- 拉链法中各链表关键字的结点都是动态申请的，所以适合于哈希表的长度无法确定的情况。
- 当关键字较大时，拉链法中新增的指针域可以忽略不计，因此节省空间。
- 删除关键字的操作容易实现，只要简单地删除链表上相应的关键字即可。
- 缺点；
- 指针需要额外的空间，故当关键字规模较小时，开放地址法更节省空间。
- 若将节省的指针空间用来扩大哈希表的规模，可使装填因子变小，这又减少了开放地址法中的冲突，从而提高平均查找速度。
常见面试题
数据结构基础知识 + 面试相关问题
原文：https://www.cnblogs.com/GarrettWale/p/14465598.html
