数据结构基础知识
3/31/2022 数据结构
# 线性表
问如果要对一个顺序表插入、查找都是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
- 非循环链队
- front指针：head
- rear指针：链尾
# 串
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算法：
# 排序算法
| 算法 | 稳定性 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|---|
| 选择排序 | × | N2 | 1 | |
| 冒泡排序 | √ | N2 | 1 | |
| 插入排序 | √ | N ~ N2 | 1 | 时间复杂度和初始顺序有关 |
| 希尔排序 | × | N 的若干倍乘于递增序列的长度 | 1 | 改进版插入排序 |
| 快速排序 | × | NlogN | logN | |
| 三向切分快速排序 | × | N ~ NlogN | logN | 适用于有大量重复主键 |
| 归并排序 | √ | NlogN | N | |
| 堆排序 | × | NlogN | 1 | 无法利用局部性原理 |
# 插入排序
- 有序区：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]
package com.walegarrett.sort;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/**
* 快速排序的实现：时间复杂度：平均O(nlogn)，最坏：O(n^2)，空间复杂度O(n)(栈空间会占用空间)，不稳定排序
* @Author WaleGarrett
* @Date 2021/3/6 19:43
*/
public class QuickSort {
/**
* 一趟排序：确定基准在数组中的序号。
* @param nums
* @param l
* @param r
* @return
*/
public int partition(int[] nums, int l, int r){
int value = nums[l];
int i = l;//i表示基准
while(l<r){
while(l<r && nums[r--] >= value);
if(l<r){
nums[l] = nums[r];
l++;
}
while(l<r && nums[l++] <= value);
if(l<r){
nums[r] = nums[l];
r--;
}
}
//最后确定value的值
nums[l] = value;
return l;
}
/**
* 归并排序的递归过程：根据已经确定的基准的值不断递归
* @param nums
* @param l
* @param r
*/
public void sort(int[] nums, int l, int r){
if(r <= l)
return;
int index = partition(nums, l, r);
sort(nums, l, index-1);//注意这里是index-1，因为index的位置已经确定了，不需要再考虑index的值
sort(nums, index+1, r);
}
/**
* 为了保证快速排序的性能：如果一开始数组就是有序的，那么需要比较的次数会很多，导致最终的时间复杂度为O(n^2)
* @param nums
*/
public void shuffle(Integer[] nums){
List<Integer> list = Arrays.asList(nums);
Collections.shuffle(list);
list.toArray(nums);
}
}
# 归并排序
- 自底而上：子文件两两归并，每次对于两个有序子文件的归并是依次遍历并且比较两部分当前元素值的大小。
- 自顶向下
- 时间复杂度最好和最坏都是O(nlogn)，需要logn趟二路归并，每次归并时间为O(n)
- 稳定的排序
package com.walegarrett.sort;
/**
* 归并排序：时间复杂度O(nlogn)，空间复杂度O(n)，稳定排序
* @Author WaleGarrett
* @Date 2021/3/6 19:14
*/
public class MergeSort {
/**
* 一次归并：需要一个临时数组用来存放未归并时的数组的值；接着从左边界开始循环，根据左右指针（low, high）所指数的大小来归并。
* @param nums
* @param l
* @param r
* @param mid
*/
public void merge(int[] nums, int l, int r, int mid){
int[] temp = new int[nums.length];
for(int i=l; i<=r; i++)
temp[i] = nums[i];
int low=l, high = r;
for(int k=l; k<=r; k++){
if(low > mid)
nums[k] = temp[high++];
else if(high > r)
nums[k] = temp[low++];
else if(temp[low] <= temp[high])//<=用于保证排序的稳定性
nums[k] = temp[low++];
else nums[k] = temp[high++];
}
}
/**
* 归并排序，自顶向下根据mid划分数组
* @param nums
* @param l
* @param r
*/
public void sort(int[] nums, int l, int r){
if(r >= l)
return;
int mid = (l + r) >> 1;
sort(nums, l, mid);
sort(nums, mid+1, r);
merge(nums, l, r, mid);
}
public static void main(String[] args) {
}
}
# 选择排序
- 有序区在前半部分，每趟从未排序的元素中选择一个最小值，记录最小值下标，将该最小值插入到有序区的末尾。
- ==不稳定的排序==
- 时间复杂度最好和最坏都是O(n^2)，因为每趟都需要在未排序的元素里比较找到一个最小值。
# 堆排序
- ==不稳定的排序==
- 一趟堆调整：O（logn），建树：O(nlogn)，排序：O(nlogn)
- 建堆：从每个非叶子结点开始，进行堆调整
- 排序：每次选择堆顶元素放入无序区的首部，再进行堆调整，使树满足大根堆的性质。
# 希尔排序
- ==不稳定的==
- 设置一个增量，所有距离为该增量倍数的元素放在同一个组内，在该组内再进行直接插入排序。
- 在同组中把所有大于当前排序元素的都后移
- 属于插入排序
# 桶排序和基数排序
- 稳定的排序
- 分配和收集实现排序，无需关键字比较
- 设置箱子数为基数：10，按照低位到高位依次进行每趟排序。
- 使用了静态链表存储，设置一个next指针。front数组和end数组存放基数排序各队列的队头和队尾。
- 排序时间是线性的：O(n)
# 搜索查找算法
# 二叉排序树
- 删除：如果左右子树均不为空，在左子树中查找数据域最大的结点，该结点为左子树最右边的一个结点，而且该结点没有左子树。只需要把该最右结点的双亲指向它的指针修改为指向该结点的左子树，然后删除该结点即可。
# 平衡二叉排序树（AVL）
- LL型插入：非平衡结点的左子树的左子树上插入叶子结点
- 以非平衡结点左子树的根为轴，顺时针旋转
- LR型插入：
- 首先以非平衡结点的左子树的右子树根为轴，逆时针旋转
- 以非平衡结点的左子树根为轴，做顺时针旋转
- RR插入
- RL插入
# 哈希表
- 解决冲突
- 开放地址法
- 拉链法
- 开放地址法：线性探测再哈希；二次探测再哈希；双哈希函数探查法；随机探测再哈希。
- 优点：
- 哈希表上的查找优于顺序查找和折半查找。
- 缺点：
- 开放地址法为减少冲突，要求装填因子α较小，故当关键字规模较大时会浪费很多空间。
- 对于开放地址法构造的哈希表，删除关键字不能简单将被删除关键字 的空间置空，否则将截断在它之后填入哈希表的同义词关键字的查找路径。（因为在开放地址法中，空地址单元都是查找失败的条件，故删除关键字只能在被删关键字上做删除标记，不能做物理删除。）
- 优点：
- 拉链法：将所有同义词的关键字链接在一个单链表中。（插入链尾）
- 优点：
- 平均查找长度相较于开放地址法更短。
- 拉链法中各链表关键字的结点都是动态申请的，所以适合于哈希表的长度无法确定的情况。
- 当关键字较大时，拉链法中新增的指针域可以忽略不计，因此节省空间。
- 删除关键字的操作容易实现，只要简单地删除链表上相应的关键字即可。
- 缺点；
- 指针需要额外的空间，故当关键字规模较小时，开放地址法更节省空间。
- 若将节省的指针空间用来扩大哈希表的规模，可使装填因子变小，这又减少了开放地址法中的冲突，从而提高平均查找速度。
- 优点：
# 常见面试题
找到数组中第二小的元素
- 一个简单的解决方案是按递增顺序对数组进行排序，堆排、快排、归并排序等等都可以达到目的。排序数组中的前两个元素是两个最小的元素。这个解的时间复杂度是O(nlogn)。
- 更好的解决方案是扫描数组两次。在第一次遍历中找到最小元素。让这个元素为x，在第二次遍历中，找到最小的元素大于x，这个解的时间复杂度是O(n)。
- 初始化2个最小值,firstmin,secondmin。然后遍历所有元素,假如当前元素小于firstmin,那么将更新firstmin,secondmin.如果小于secondmin直接更新secondmin
找到数组中第一个没有重复的整数
- 双重循环，找到第一个不重复的数
合并两个分类数组
重新排列数组中的正值和负值
翻转列表
检测链表中的循环
返回链表中倒数第 n 个节点
移除链表中的重复值
使用队列来实现堆栈
- 每入队一个元素，就将该元素之前的所有元素重新入队，使得第一个元素始终是栈top的元素
颠倒队列中前 k 个元素的顺序
使用队列生成从 1 到 n 的二进制数
使用堆栈计算后缀表达式
对堆栈中的值进行排序
- 这道题的麻烦点在于，我们不能分配新的内存，如果可以的话，我们可以先构造另一个堆栈，把原堆栈的元素全部弹到新堆栈中，同时记录下元素中的最大值，然后把最大值压入元堆栈，再把新堆栈中的所有元素除去其中的最大值压入原堆栈，这样一来，堆栈元素中的最大值就压入底部了，这个过程反复进行，最后就可以完成所需要的排序。
- 对堆栈排序时，现将栈顶元素弹出，把剩下的堆栈元素进行排序，排好序后，把原来栈顶元素使用insert重新插入堆栈即可。
检查表达式中的括号是否匹配
1）出现左括号则进栈
2）出现右括号则首先检判断栈是否为空，如果不为空，则判断与栈顶元素是否与之匹配，如果匹配则弹出栈顶元素。
3）最后若栈空，则表明匹配成功；否则表明不匹配。
实现广度优先搜索和深度优先搜索
检查一个图是否为树
- 该图是一个连通图
- 该图的边数为结点数-1
计算一张图中的边的数量
- 总度数(D)等于边数(E)的两倍
- 求度数，遍历每个顶点
找到两个顶点之间的最短路径
找到一个二叉树的高度
找到一个二叉搜索树中第 k 个最大值
- 最朴素的想法，中序遍历就是二叉搜索树的递增序列，那直接写出整棵树的中序遍历即可。
找到距离根部“k”个距离的节点
找到一个二叉树中给定节点的祖先（ancestors）
两个结点的公共祖先
- 1， 从给定的节点出发，根据其父节点往上走，一直走到根节点为止，先确定两个节点在二叉树中的高度。例如节点401经过第一步后得到的高度是4，节点29高度是3.
- 2， 从高度大的节点出发，通过父指针往上走，一直走到高度与另个一高度较小的节点高度一样为止。例如从节点401开始，先回到父节点1，因为此时节点1的高度与节点29的高度一样，都是3
- 3，两个节点分别往上走一步，然后判断是否重合，如果重合，那么当前节点就是两节点的最近祖先，若不然则继续重复步骤3，例如从节点1，和节点29开始，每往上走一步就判断是否重合，那么他们分别往上走两步后，将会在节点7相遇，因此，节点7将是节点401和节点29的最近共同祖先。
常问的哈希面试问题：
- 找到数组中的对称对
- 追踪遍历的完整路径
- 查看一个数组是否为另一个数组的子集
- 检查给定数组是否不相交