八股文——数据结构
https://visualgo.net/zh/sorting 算法可视化
查找
1、二分查找
元素必须是有序的，如果是无序的则要先进行排序操作。 最坏情况下，关键词比较次数为 l o g 2 n + 1 且期望时间复杂度为l o g 2 n
2、插值查找
按比例查找：
mid=low+(key-a[low])/(a[high]-a[low])*(high-low)//按照数据在首尾数据间的比例查找
排序
1.希尔排序（组内插入排序）
int d = a.length;
while (d!=0) {
d=d/2;
for (int x = 0; x < d; x++) {//分的组数
for (int i = x + d; i < a.length; i += d) {//组中的元素，从第二个数开始
int j = i - d;//j为有序序列最后一位的位数
int temp = a[i];//要插入的元素
while(j >= 0 && temp < (a[j -= d])) {//从后往前遍历。
a[j + d] = a[j];//向后移动d位
}
a[j + d] = temp;
}
}
}
}
2.简单选择排序
第一次选择一个最小的数，放在第一个，然后一直循环做n次。
3.堆排序
堆中某个节点的值总是不大于（或不小于）其父节点的值(左右子树谁大谁小并没有规定，左子树可以比右子树大)。
插入、删除、建堆都是l o g 2 n
最坏情况可能是O(n)
//1.构建大顶堆
for(int i=arr.length/2-1;i>=0;i--){
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(arr,i,arr.length);
}
public static void adjustHeap(int []arr,int i,int length){
int temp = arr[i];//先取出当前元素i
for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
k++;
}
if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
2、从堆顶中取出元素
swap(arr,0,j);//将堆顶元素与末尾元素进行交换
adjustHeap(arr,0,j);//重新对堆进行调整
public static void adjustHeap(int []arr,int i,int length){
int temp = arr[i];//先取出当前元素i
for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
k++;
}
if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
public static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
4.快排排序
public void quickSort(int[] arr, int l, int r){
if(l < r){
int temp = arr[l];
int i = l;
int j = r;
while(l <= r){
while(arr[i] <= temp && i < j ){
i++;
}
while(arr[j] > temp && i < j){
j--;
}
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
arr[i] = temp;
quickSort(arr,l,i -1);
quickSort(arr, i + 1, r);
}
最好：O(n l o g 2 n )
最坏：O ( n 2 ） (接近有序的时候)
空间复杂度：o（nlog2n）
稳定性：不稳定
5.归并排序
#include<iostream>
using namespace std;
void Merge(int arr[],int low,int mid,int high){
//low为第1有序区的第1个元素，i指向第1个元素, mid为第1有序区的最后1个元素
int i=low,j=mid+1,k=0; //mid+1为第2有序区第1个元素，j指向第1个元素
int *temp=new(nothrow) int[high-low+1]; //temp数组暂存合并的有序序列
if(!temp){ //内存分配失败
cout<<"error";
return;
}
while(i<=mid&&j<=high){
if(arr[i]<=arr[j]) //较小的先存入temp中
temp[k++]=arr[i++];
else
temp[k++]=arr[j++];
}
while(i<=mid)//若比较完之后，第一个有序区仍有剩余，则直接复制到t数组中
temp[k++]=arr[i++];
while(j<=high)//同上
temp[k++]=arr[j++];
for(i=low,k=0;i<=high;i++,k++)//将排好序的存回arr中low到high这区间
arr[i]=temp[k];
delete []temp;//删除指针，由于指向的是数组，必须用delete []
}
//用递归应用二路归并函数实现排序——分治法
void MergeSort(int arr[],int low,int high){
if(low<high){
int mid=(low+high)/2;
MergeSort(arr,low,mid);
MergeSort(arr,mid+1,high);
Merge(arr,low,mid,high);
}
}
平均时间复杂度：O(nlogn)
最佳时间复杂度：O(n)
最差时间复杂度：O(nlogn)
空间复杂度：O(n)
归并排序比较占用内存，但效率高且稳定。
6.基数排序
用于大量数，很长的数进行排序时。
1将所有的数的个位数取出，按照个位数进行排序，构成一个序列。
2将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列
图论
图的存储方式，广度搜索和深度搜索
邻接矩阵：本质就是2*2的数组
邻接表：数组+列表，和哈希表的存储方式差不多
深度搜索（dfs）：可以使用递归或者栈来实现
广度搜索（bfs）：使用列表实现
最短距离
Dijkstra最短路径算法（求一个点到其他点的最短距离）
Floyd算法（求各个点的最短距离） 本质就是动态规划，
公式：顶点i 到 顶点j 的新距离 = Min（顶点i 到 顶点j 的旧距离，顶点i 到 顶点n 的距离+顶点n 到 顶点j 的距离）
最小生成树
prim算法（贪心算法）：
任意点为起点，将边加入点集合中。
复杂度：O（v2）
karsual
边排序，从小到大构建。 O(ElogE)
并查集
主要用于解决一些元素分组的问题。它管理一系列不相交的集合， 并支持两种操作：
合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。
性能跟树的深度有关系，并查集的时间复杂度为 O(logn)
拓扑排序
// deg是入度，在存图的时候需要录入数据
// A是排序后的数组
int deg[MAXN], A[MAXN];
bool toposort(int n)
{
int cnt = 0;
queue<int> q;
for (int i = 1; i <= n; ++i)
if (deg[i] == 0)
q.push(i);
while (!q.empty())
{
int t = q.front();
q.pop();
A[cnt++] = t;
for (auto to : edges[t])
{
deg[to]--;
if (deg[to] == 0) // 出现了新的入度为0的点
q.push(to);
}
}
return cnt == n;
}
``
##海量数据去重
需要从海量数据中查询某字符串是否存在
缓存穿透：server端请求数据时，server缓存db，redis和mysql都不存在数据。
server请求数据过程：
1先访问redis，如果存在，直接返回，
2不存在则访问mysql，
3mysql如果不存在，返回，
4如果存在，将mysql存在的key写回redis
解决缓存穿透：
1.在redis端设置<key,null>键值对，以此避免访问mysql；
缺点：<key,null>过多，占用内存
*可以给key设计过期expire key 600ms，停止攻击后最终由redis自动清除无用的key；
方法2：在**server端**存储一个布隆过滤器，将mysql包含的key放入布隆过滤器中，布隆过滤器能过滤一定不存在的数据
###布隆过滤器
