笔试过程中数据结构和算法是必不可少的部分，下面分享一些刷题中常见的知识点,可能题目会感觉有点乱，都是零碎的知识点。
(有不对的地方请指正)
多数都是自己笔试中碰到的。
最近忙于项目，结束后会补全！
1、数组
1、二分查找
二分查找是针对有序数组来进行操作的
主要思想就是每次取mid，让mid位置的值和查找值进行比较
如果大于查找值就在左侧，范围每次缩小一半，这样一直递归就可以找到最后的值
最大比较次数是[log2n]向下取整再加1
时间复杂度:**O(log2n);
public int BinarySearch(int[] array, int T) { int low, high, mid; low = 0; high = array.Length - 1; while (low <= high) { mid = (low + high) / 2; if (array[mid] < T) { low = mid + 1; } else if (array[mid]>T) { high = mid - 1; } else { return mid; } } return -1; }
2、快排
大概思想就是每次找一个基准数(我习惯取中间的数)，然后定义两个数来模拟指针操作，分别从头和尾往中间走，
左边的遇到比自己大，右边遇到比自己小的时候就交换位置，直到i和j碰面，然后这个位置就是基准数的正确位置，
然后递归左右两部分，最后就得到了排好的序列。
平均时间复杂度： O(NlogN)
#include <iostream>
using namespace std;
const int N = 1000010;
int q[N];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
return 0;
}
3、平均时间复杂度的比较
补充：
顺序查找的时间复杂度为o(n)
分块查找的时间复杂度为o(log2n)到o(n)之间
二分查找的时间复杂度为o(log2n)
哈希查找的时间复杂度为o(1)
4、分块查找
设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找
并且索引表和块内均采用顺序查找 ，则其平均查找长度为 ( ) 。
总的平均查找长度为：分块查找的平均长度+顺序查找的平均长度
5、线性表
①线性表的顺序存储结构是一种 (随机存取 ) 的存储结构。用一组地址连续的存储单元依次存储线性表的数据元素(数组)，
存入的时候是顺序的，前后位置关系在内存中也是固定的，取出的时候直接依据编号就可以找到，不需要遍历一遍，所以是随机取出的。
②线性表的链式存储结构，顺序存取。数据元素在内存中的位置是动态分配的无序的(链表)，所以取出的时候并不知道其具体位置，必须要从头开始遍历，是顺序取出的。
6、双指针
链表和指针经常遇到的相关节点的问题有的时候就要考虑双指针模拟过程
题目链接：https://www.acwing.com/problem/content/86/
这里就要模拟两个指针来操作，通过计算指针的轨迹可以得出节点的位置
可以看做一种思想，有的时候可以巧妙的解决问题。
class Solution {
public:
ListNode *entryNodeOfLoop(ListNode *head) {
if (!head || !head->next) return 0;
ListNode *first = head, *second = head;
while (first && second)
{
first = first->next;
second = second->next;
if (second) second = second->next;
else return 0;
if (first == second)
{
first = head;
while (first != second)
{
first = first->next;
second = second->next;
}
return first;
}
}
return 0;
}
};
2、树
1、平衡二叉树（AVL树）
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
插入？
2、完全二叉树
除了最后一层其它层每个节点的度数都为2
3、树的常见计算
非空二叉树叶子结点数 = 度为2的结点数 + 1
具有n个结点的完全二叉树（包括满二叉树）的高度为【log2 n】+1
n个节点的二叉树一共有((2n)!)/(n! * (n+1)!)种
对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1
4、编程题
已知两种遍历返回另一种
例如，已知后续和中序求层次遍历
思路就是以后续的最后一个为根来分中序，然后递归
都放到一个map或者unordered_map里，
也可以通过数的结构来实现
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
vector<int> post, in;
map<int, int> level;
void pre(int root, int start, int end, int index) {
if(start > end) return ;
int i = start;
while(i < end && in[i] != post[root]) i++; //找到根节点在中序中的位置
level[index] = post[root];
pre(root - 1 - end + i, start, i - 1, 2 * index + 1);
pre(root - 1, i + 1, end, 2 * index + 2);
}
int main() {
int n;
scanf("%d", &n);
post.resize(n);
in.resize(n);
for(int i = 0; i < n; i++) scanf("%d", &post[i]);
for(int i = 0; i < n; i++) scanf("%d", &in[i]);
pre(n-1, 0, n-1, 0);
auto it = level.begin();
printf("%d", it->second);
while(++it != level.end()) printf(" %d", it->second);
return 0;
}
树节点的结构:
struct BTreeNode{ int data = 0; BTreeNode *left; BTreeNode *right; };
二叉树具体实现可以参考https://blog.csdn.net/hellowd123/article/details/99692395
3、图的应用
1、存储结构(大佬的链式前向星)
https://blog.csdn.net/acdreamers/article/details/16902023
2、最短路径
4、算法
1、正则表达式
2、并查集
3、动态规划
4、字符串操作
5、dfs
5、常用的零碎知识点
1、多值排序
两个值可以用pair，再多了就用结构体，也可以重载运算符
pair的使用并排序
typedef pair<int,int> PII;
PII cows[N];
cin >> cows[i].first >> cows[i].second;
sort(cows, cows + n);
2、同余取模定理
(a * b) % m = ((a % m) * (b % m)) % m
(a + b) % m = (a % m + b % m) % m
3、cbrt(n)三次方根
4、字符操作
isalpha(n)//是不是字母
isdigit(n)//是不是数字
tolower(n)//转小写
5、s.find(S1);s.rfind(s1);左右匹配左坐标
6、set的常见用法
set<int>s;集合自动去重
set<int>::iterator it;
for(it=s.begin ();it!=s.end ();it++)
{
cout<<*t;
}
cout<<"s.begain() "<<*s.begin ()<<endl;
//lower_bound()--返回指向大于（或等于）某值的第一个元素的迭代器
cout<<"lower_buond 3 "<<*s.lower_bound (3)<<endl;
//upper_bound()--返回大于某个值元素的迭代器
cout<<"upper_bound 3 "<<*s.upper_bound (3)<<endl;
//find()--返回一个指向被查找到元素的迭代器
cout<<"find() 3 "<<*s.find (3)<<endl;
cout<<"s.size() "<<s.size ()<<endl;
7、小根堆
priority_queue<int, vector<int>, greater<int>> heap;