2021-02-23-基本的算法和数据结构(包含多线程)
为什么写这个？通用的方法常常隐藏常见的方法。
1 抽象，实现和STL
1.1 STL 数据结构VECTOR
- O(1)时间的快速访问
- 顺序存储，所以插入到非尾结点位置所需时间复杂度为O(n)，删除也一样
- 当我们新建一个vector的时候，会首先分配给他一片连续的内存空间，如
std::vector<int> vec，当通过push_back向其中增加元素时，如果初始分配空间已满，就会引起vector扩容，其扩容规则在gcc下以2倍方式完成：首先重新申请一个2倍大的内存空间；然后将原空间的内容拷贝过来；最后将原空间内容进行释放，将内存交还给操作系统； - 执行插入/删除后，所有执行点之后迭代器和指针引用失效，同理，扩容之后的所有迭代器指针和引用也失效。
- 常用的函数：push_back 在数组的最后添加一个数据，pop_back 去掉数组的最后一个数据，**begin 得到数组头的指针 end 得到数组的最后一个单元+1的指针 capacity 当前vector分配的大小 size 当前使用数据的大小 erase 删除指针指向的数据项 clear 清空当前的vector empty 判断vector是否为空
1.2 map和multimap
- 两个都是关联容器，也就是提供一对一key-value的数据处理能力。map与multimap的区别在于，multimap允许关键字重复，而map不允许重复。
- 这两个关联容器的底层数据结构均为红黑树。根据红黑树的原理，map与multimap可以实现O(lgn)的查找，插入和删除。
- 常用的函数：clear(） 删除所有元素，empty() 如果 map 为空则返回 true，find() 查找一个元素， insert() 插入元素，end() 返回指向 map 末尾的迭代器，insert(pair < int,string > (1,”Jim”)) 插入元素的时候要把元素的类型组织出来，size()返回map的大小，erase() 删除一个元素
1.3 unordered_map 与unordered_multimap
- map与multimap为有序的
- 而unordered_map与unordered_multimap中key为无序排列，其底层实现为hash table，因此其查找时间复杂度理论上达到了O(1)
- 常用的函数为
1.4 set & multiset
- set系列的数据结构是只有值，因此可以认为set是只保存关键字的容器。
- set与multiset有序存储元素，这两种容器的底层实现与map一样都是红黑树，所以能实现O(lgn)的查找，插入，删除操作。
- 常用的函数为
1.5 优先队列priority_queue
- 优先级队列相当于一个有权值的单向队列queue，在这个队列中，所有元素是按照优先级排列的。
- priority_queue根据堆的处理规则来调整元素之间的位置，根据堆的特性，优先级队列实现了取出最大最小元素时间复杂度为O(1),对于插入和删除，其最坏情况为O(lgn)。
- 常用的函数为：priority_queue<Type, Container, Functional>Type数据类型，Container是容器类型，Functional是排序的函数,常，一般Functional默认是std::less<Type>小顶堆，不过我们可以穿进去std::greater<Type>来构建大顶堆，这个用于声明。push(const T& obj)：将obj的副本放到容器的适当位置，这通常会包含一个排序操作。push(T&& obj)：将obj放到容器的适当位置，这通常会包含一个排序操作。top()：返回优先级队列中第一个元素的引用。pop()：移除第一个元素。size()：返回队列中元素的个数。empty()：如果队列为空的话，返回true。
1.6 list
- 底层一般是
1.7 stack
- 底层一般是链表
- 常用的函数为：std::stack<std::string,std::list<std::string» fruit; 用于初始化。top()：返回一个栈顶元素的引用，类型为 T&。如果栈为空，返回值未定义。push(const T& obj)：可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。pop()：弹出栈顶元素。empty()：在栈中没有元素的情况下返回 true。size()：返回栈中元素的个数。
2 排序
基于比较的排序算法，其时间复杂度不可能低于 n∗lognn∗log**n，这是由排序过程中的决策树模型决定的
决策树模型：
- 节点表示比较： 决策树上的每个节点都代表一次元素比较操作（例如，比较数组中两个元素的大小）。
- 分支表示比较结果： 每个节点根据比较结果产生不同的分支，例如，大于、小于或等于。
- 叶子节点表示排序结果： 每一种可能的排序结果都对应着决策树上的一个叶子节点。
为什么最优时间复杂度是 n*logn：
- 叶子节点数量： 对于 N 个元素，共有 N! (N 的阶乘) 种不同的排列方式，也就是 N! 种可能的排序结果。因此，决策树必须至少包含 N! 个叶子节点才能表示所有情况。
- 树的高度与比较次数： 决策树的高度（从根节点到最深叶子节点的路径长度）代表了排序算法在最坏情况下需要进行的最多比较次数。
- 树的高度限制： 对于一棵二叉树（大多数比较排序都是基于二叉比较），高度为 h 的树最多拥有 2h2h 个叶子节点。
- 推导出最优高度： 为了容纳 N! 个叶子节点，树的高度 h 必须满足 2h>=N!2h>=N! 。 使用斯特林公式近似计算阶乘：N!≈2πN(Ne)NN!≈2πN*(*eN)N，可以推导出 h>=log2(N!)≈N∗log2Nh>=log2(N!)≈N∗log2N。
结论：
由于决策树的高度决定了比较次数，而为了表示所有可能的排序结果，树的高度至少为 N∗log2NN∗log2N，所以任何基于比较的排序算法，其时间复杂度都不可能低于 n∗lognn∗log**n。 这被称为比较排序算法的时间复杂度下限。
2.1 最简单的排序
常见的排序算法就不多赘述了：
- 选择排序：每次选择出来最小的元素然后交换到检查数组的首部，因此对于长度为N的数组选择排序需要大约N^2/2次比较和N次交换。问题是这个算法运行时间和输入无关（这不是个好消息）。但是数据移动最少。
- 插入排序：我更喜欢叫做插扑克排序，每次将当前元素插入到已经拍好的合适的位置。这个算法的时间和原本数组的排序有关。但是插入排序最惨情况也需要N^2/2的比较和N^2/2的交换，最好情况只需要N-1比较和0次交换。
2.2 归并排序
比较方法做的排序上限是多少？答案是：没有任何基于比较的算法能保证使用少于lg(N!)~NlgN的比较次数，将长度为N的数组排序。
归并排序，一种思考的方法
-
归并排序依托的原理是：两个有序的数组（长度都为N/2)，在整体重排的时候最多只需要比较N次。由于每次都是一半次数的缩减，因此这种复杂度直接减少到了N*log(N)。
-
实际上归并排序就是典型的分治思想，将问题拆解为两份（如果拆解相等，一般是最优的），两个部分都做处理。整体的有序处理会简单很多。
-
归并排序有两种实现，一种从上向下，一种从下向上。
2.3 快速排序
快速排序大概是最著名的排序了，基本所有人都知道快排，实际上快排也是基于分治法。由于快排的特殊性，所以将伪码写上。
- 快排平均需要2N*lnN次比较，以及1/6次交换。
- 快排最惨需要N^2/2次比较，但打乱数组会避免这种算法
public class quick
{
public static void sort(Comparele[] a)
{
Random.shuffle(a);
sort(a,0,a.length-1);
}
private static void sort(Comparable[] a, int lo, int hi)
{
if (hi < lo) return;
int j = partition(a,lo,hi);
sort(a,lo,j-1);
sort(a,j+1,hi);
}
private static int partition(Comparable[] a, int lo, int hi)
{
int i = lo, j = hi + 1;
Comparable v = a[lo];
while(1)
{
while(less(a[++i],v)) if(i==hi) break;
while(less(v,a[--j])) if(j==lo) break;
if (i >= j) break;
exchange(a, i, j);
}
exchange(a,lo,j);
return j;
}
}
2.4 堆排序
简单来说我觉得堆排序是一个非常好玩的问题，实际上对常见问题的考虑都是一致的。堆大多都是大顶堆/小顶堆
代码如下:
private void sink(int k)
{
while(2*k <= N)
{
int j = 2*k;
if (j < N && less(j,j+1)) j++;
if(!less(k,j)) break;
exchange(k,j);
k = j;
}
}
2.5 从排序向外发散
一个很常见的问题实际上是，最小的第K个数，这个问题的答案就是两种堆排序和快排思路
3 查找
3.1 二叉树（二叉查找树）
常见的先序遍历，中序遍历和后序遍历都是递归，下面给个迭代版本的实现。实际上还是利用非常常见的思想，也就是模拟计算机的栈而已。具体流程不明白的，就看下知乎上画的那个遍历的图片。
先序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> preOrderList = new ArrayList<>(); //存放访问顺序
Stack<TreeNode> stack = new Stack<>(); //存放结点，用于回溯
while(root != null || !stack.empty()) { //迭代遍历二叉树
while(root != null) { //使root指向当前子二叉树的最左结点
stack.push(root);
preOrderList.add(root.val); //将当前子二叉树的根节点入栈，并访问
root = root.left;
}
while(root == null && !stack.empty()) {
root = stack.pop().right; //自底向上找到栈中跟结点第一个非空右孩子，第一个未访问过的右孩子！
}
}
return preOrderList;
}
}
中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> inOrderList = new ArrayList<>(); //存放访问顺序
Stack<TreeNode> stack = new Stack<>(); //存放结点，用于回溯
while(root != null || !stack.empty()) { //迭代遍历二叉树
while(root != null) { //使root指向当前子二叉树的最左结点
stack.push(root);
root = root.left;
}
root = stack.pop();
inOrderList.add(root.val); //出栈当前子二叉树的根结点，并访问
root = root.right; //更新root结点：当前子二叉树的右孩子 or 树的父结点
}
return inOrderList;
}
}
后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> postOrderList = new ArrayList<>(); //用于存放访问顺序
Stack<TreeNode> stack = new Stack<>(); //存放结点，用于回溯
TreeNode pre = null; //记录之前访问过的结点
while(root != null || !stack.empty()) { //迭代访问二叉树
while(root != null) { //使root指向当前子二叉树的最左结点
stack.push(root);
root = root.left;
}
root = stack.peek();
if(root.right == null || root.right == pre) { //当前结点为叶子结点 或者 当前结点的右孩子是上个访问结点
pre = root; //更新上一次访问的结点
postOrderList.add(stack.pop().val); //出栈，表示访问了当前结点
root = null; //让root到下一次循环再更新，避免发生空栈错误
}else {
root = root.right; //访问当前结点的右孩子
}
}
return postOrderList;
}
}
linux内核的基础知识
1 进程调度
时间片，分配给每个可运行进程的处理器时间段。linux为抢占式系统。
调度算法有基于优先级，linux为动态优先级
2 缺页中断
结尾
唉，尴尬
