万能的头文件<bits/stdc++.h>
#include<bits/stdc++.h>包含了目前c++所包含的所有头文件！！！！
i++和++i的区别？哪个效率更高？
i++ 就是i = i + 1 ，但是表达式是i+1之前的值，首先它把这个值保存到一个副本中。
++i 就是 i= i+1 ，它不需要保存到副本中，因此效率更高一些。
inline和宏的区别?
1、内敛函数在编译时展开，宏在预编译时展开
2、在编译时内敛函数会嵌入到目标代码中，宏只是一个简单的文本替换
3、内敛函数会进行安全检查，宏不会
4、宏不是函数，inline是一个函数
5、inline可以不展开，宏必须展开
简述内敛函数？
内敛函数是在类声明体内定义的函数或在类的实现部分定义的，其前用inline修饰，它将简单的函数内嵌到调用它的函数代码中，这样做节省了调用函数的开销。
普通函数的调用要经过“保存现场、转到被调函数执行、执行完毕返回调用处、恢复现场”这一过程，产生时空开销。
内联函数是通过代码膨胀来执行的，在内联函数调用处复制函数代码，这样省去了普通函数调用的时空开销，提高了程序执行效率，但是由于代码复制增加了内存开销，所以内联函数应当是小函数、执行耗时短的函数。
select和epoll的区别？
select是通过轮询的方式找到读取或写入的数据流对他们进行操作。具有O(n)的无差别轮询复杂度，处理的流越多无差别的轮询时间就越长。
poll和select没什么太大的差别，它将用户传入的数组拷贝到内核空间，查找每个fd对应的设备状态。它没有最大连接数的限制，因为它是基于链表存储的。时间复杂度O(n)。
epoll是基于事件驱动的，哪个流发生I/O事件会直接通知。时间复杂度O(1)。
select，poll，epoll都是IO多路复用的机制。I/O多路复用就通过一种机制，可以监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知程序进行相应的读写操作。但select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间。
水平触发:如果文件描述符已经就绪可以非阻塞的执行IO操作了,此时会触发通知。允许在任意时刻重复检测IO的状态。select,poll就属于水平触发。
边缘触发:如果文件描述符自上次状态改变后有新的IO活动到来,此时会触发通知。在收到一个IO事件通知后要尽可能多的执行IO操作，因为如果在一次通知中没有执行完IO那么就需要等到下一次新的IO活动到来才能获取到就绪的描述符。信号驱动式IO就属于边缘触发。
1、 time_wait的作用
TIME_WAIT状态存在的理由：
1）可靠地实现TCP全双工连接的终止
保证客户端发送的最后一个ACK报文能够到达服务器，因为这个ACK报文可能丢失，站在服务器的角度看来，我已经发送了FIN+ACK报文请求断开了，客户端还没有给我回应，应该是我发送的请求断开报文它没有收到，于是服务器又会重新发送一次，而客户端就能在这个2MSL时间段内收到这个重传的报文，接着给出回应报文，并且会重启2MSL计时器。
2）允许老的报文在网络中消逝
防止类似与“三次握手”中提到了的“已经失效的连接请求报文段”出现在本连接中。客户端发送完最后一个确认报文后，在这个2MSL时间中，就可以使本连接持续的时间内所产生的所有报文段都从网络中消失。这样新的连接中不会出现旧连接的请求报文。
2、大量TIME_WAIt造成的影响
在高并发短连接的TCP服务器上，当服务器处理完请求后立刻主动正常关闭连接。这个场景下会出现大量socket处于TIME_WAIT状态。如果客户端的并发量持续很高，此时部分客户端就会显示连接不上。
为什么我们要关注这个高并发短连接呢？有两个方面需要注意：
高并发可以让服务器在短时间范围内同时占用大量端口，而端口有个0~65535的范围，并不是很多，刨除系统和其他服务要用的，剩下的就更少了。
在这个场景中，短连接表示“业务处理+传输数据的时间 远远小于 TIMEWAIT超时的时间”的连接。
TCP处于TIMEWAIT状态时，别的请求过来后，没有空闲的端口可供tcp连接，大大影响服务器响应请求。 长连接业务的服务就不需要考虑TIMEWAIT状态。同时，假如你对服务器业务场景非常熟悉，你会发现，在实际业务场景中，一般长连接对应的业务的并发量并不会很高。
3、TIME_WAIT状态如何避免
首先服务器可以设置SO_REUSEADDR套接字（so_reuseaddr）选项来通知内核，如果端口忙，但TCP连接位于TIME_WAIT状态时可以重用端口。在一个非常有用的场景就是，如果你的服务器程序停止后想立即重启，而新的套接字依旧希望使用同一端口，此时SO_REUSEADDR选项就可以避免TIME_WAIT状态。
堆和栈的区别？
1、生长方向：堆自下向上，栈自上向下；
2、分配方式：堆手动分配，栈自动分配；
3、分配大小：堆很大，栈很小；
4、碎片化：堆易产生，栈不会产生。
数组第k小的数
#include <iostream>
using namespace std;
int findK(int arrayNum[], int p, int r, int k) {
/**
*在数组arrayNum[p:r]中查找第k（k > 0)个元素（下标为p+k-1)
* p <= r && 0 < k && k <= p - r +1 （合法输入说明）
*渐进时间复杂度/平均时间复杂度 O(N)
*/
int i = p, j = r, key = arrayNum[i];
while (i < j) {
while (arrayNum[i] <= key)
++i;
while (arrayNum[j] >= key)
--j;
if (i < j)
{
swap(arrayNum[i++], arrayNum[j--]);
}
}//循环结束后 i = j,其实前面这些语句就是快排的一次划分
int lefts = i - p + 1;
if (lefts == k)
return arrayNum[i];//找到中位数了
if (lefts > k) //比关键字小的数的个数大于k，则中位数在左边
return findK(arrayNum, p, i - 1, k);
else
return findK(arrayNum, i + 1, r, k - lefts);
}
int main()
{
int tmp[11] = { 3, 4 , 5, 2, 4, 6,0, 8, 1,324 };
cout << "请输入要查找第几个最小数,数字要小于等于10" << endl;
int m = 0;
cin >> m;
int result = 0;
result = findK(tmp, 0, 10, m);
cout << "结果为" << result << endl;
return 0;
}
Top-K问题
1、直接全部排序（只适用于内存够的情况）
当数据量较小的情况下，内存中可以容纳所有数据。则最简单也是最容易想到的方法是将数据全部排序，然后取排序后的数据中的前K个。
这种方法对数据量比较敏感，当数据量较大的情况下，内存不能完全容纳全部数据，这种方法便不适应了。即使内存能够满足要求，该方法将全部数据都排序了，而题目只要求找出top K个数据，所以该方法并不十分高效，不建议使用。
2、快速排序的变形 （只使用于内存够的情况）
这是一个基于快速排序的变形，因为第一种方法中说到将所有元素都排序并不十分高效，只需要找出前K个最大的就行。
这种方法类似于快速排序，首先选择一个划分元，将比这个划分元大的元素放到它的前面，比划分元小的元素放到它的后面，此时完成了一趟排序。
如果此时这个划分元的序号index刚好等于K，那么这个划分元以及它左边的数，刚好就是前K个最大的元素；如果index > K，那么前K大的数据在index的左边，那么就继续递归的从index-1个数中进行一趟排序；如果index < K，那么再从划分元的右边继续进行排序，直到找到序号index刚好等于K为止。再将前K个数进行排序后，返回Top
K个元素。这种方法就避免了对除了Top K个元素以外的数据进行排序所带来的不必要的开销。
3、最小堆法
这是一种局部淘汰法。先读取前K个数，建立一个最小堆。然后将剩余的所有数字依次与最小堆的堆顶进行比较，如果小于或等于堆顶数据，则继续比较下一个；否则，删除堆顶元素，并将新数据插入堆中，重新调整最小堆。当遍历完全部数据后，最小堆中的数据即为最大的K个数。
4、分治法
将全部数据分成N份，前提是每份的数据都可以读到内存中进行处理，找到每份数据中最大的K个数。此时剩下NK个数据，如果内存不能容纳NK个数据，则再继续分治处理，分成M份，找出每份数据中最大的K个数，如果M*K个数仍然不能读到内存中，则继续分治处理。直到剩余的数可以读入内存中，那么可以对这些数使用快速排序的变形或者归并排序进行处理。
5、Hash法
如果这些数据中有很多重复的数据，可以先通过hash法，把重复的数去掉。这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间。处理后的数据如果能够读入内存，则可以直接排序；否则可以使用分治法或者最小堆法来处理数据。
6、队列
可以将前K个数据放入有序队列中，剩余的数据依次与队列中的数据比较，如果比队列中的最小值小或等于，则继续，否则，就替换，调整有序队列。遍历结束后，队列中的数据就是前K大的元素。
讲一下哈希算法，有什么用；解决哈希冲突的方法？
哈希算法，用于将任意长度的二进制值串映射为固定长度的二进制值串，映射之后得到的二进制值就是哈希值（散列值）。
哈希表就是一种以 键-值(key-indexed) 存储数据的结构。
用于文件校验、数字签名、鉴权协议。
解决哈希冲突的方法
1、开放地址法
用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的 地址则表明表中无待查的关键字，即查找失败。
2、拉链法
拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数 组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于 1，但一般均取α≤1。
3、再散列法
再散列法其实很简单，就是再使用哈希函数去散列一个输入的时候，输出是同一个位置就再次散列，直至不发生冲突位置
下面我在介绍另一种解决哈希表的方法，开链法，也叫哈希桶。下面我介绍一下这种方法的思路。
基本思路：
1.先给一个数组，这个数组中存的是指针数组，每个指针数组都指向一个数组。
2.用元素除以存储指针数组的数组的大小。
3.余数与指针数组下标相同的，都链到数组指针指向的这一个数组。
我在进一步用图表示一下：
代码如下：
static关键字？
static修饰的内置类型变量分为静态全局变量和静态局部变量，静态变量内存分配在 .data段。静态变量只初始化一次，未初始化的静态变量会默认初始化为0。静态全局变量只在本文件可见，外部文件无法访问。而静态局部变量只在定义的作用域内可见，但他们的生存周期都是整个程序运行时期。
static修饰的函数为静态函数，静态函数主要是起到函数的隐藏作用，static修饰的函数只允许在当前文件中使用，在其他文件中无法找到该函数的地址。
static修饰的数据成员属于类的组成部分，static修饰的数据成员不在栈上分配内存而在.data段分配内存，static修饰的数据成员不能通过调用构造函数来进行初始化，因此static修饰的数据成员必须在类外进行初始化且只会初始化一次。
static修饰的成员方法为静态成员方法，静态成员方法可以在类内或类外定义，但必须在类内声明；static成员方法没有this指针，所以不能直接引用非static数据成员或调用类的非static成员方法，只能调用类的static成员数据和static成员方法；static成员不是任何对象的组成，不依赖对象的调用所以static成员方法不能被声明为const，因为const只限定该类的对象；static成员方法不能同时被声明为虚函数。
extern关键字
extern可以置于变量或者函数前，以标示变量或者函数的定义在别的文件中，提示编译器遇到此变量和函数时在其他模块中寻找其定义。此外extern也可用来进行链接指定。
extern有两个作用：
第一个,当它与"C"一起连用时，如: extern "C" void fun(int a, int b);则告诉编译器在编译fun这个函数名时按着C的规则去翻译相应的函数名而不是C++的。
第二，当extern不与"C"在一起修饰变量或函数时，如在头文件中: extern int g_Int; 它的作用就是声明函数或全局变量的作用范围的关键字，其声明的函数和变量可以在本模块活其他模块中使用，记住它是一个声明不是定义!也就是说B模块(编译单元)要是引用模块(编译单元)A中定义的全局变量或函数时，它只要包含A模块的头文件即可,在编译阶段，模块B虽然找不到该函数或变量，但它不会报错，它会在连接时从模块A生成的目标代码中找到此函数。
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
红黑树的性质
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点（NIL节点，空节点）是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
C++的STL中。如map和set都是用红黑树实现的
301 redirect: 301 代表永久性转移(Permanently Moved)
302 redirect: 302 代表暂时性转移(Temporarily Moved )
301表示旧地址A的资源已经被永久地移除了（这个资源不可访问了），搜索引擎在抓取新内容的同时也将旧的网址交换为重定向之后的网址；
302表示旧地址A的资源还在（仍然可以访问），这个重定向只是临时地从旧地址A跳转到地址B，搜索引擎会抓取新的内容而保存旧的网址。
