1.协程了解过么？
协程是更轻量级的线程。用于解决线程间切换和进程间切换开销大的问题。协程各个状态（阻塞、运行）的切换是由程序控制，而不是内核控制，不需要内核态和用户态之间的切换，减少了开销。
2.C和C++ static的区别：
C++有静态成员和静态成员函数，其他应该都是一样的吧。
3.C和C++ 中struct的区别：
如没有typedef，struct Student{};…C++中可以直接使用 Student zhangsan; 而C中必须 struct Student zhangsan。
C++中struct可以当做类来使用，不过struct中的所有成员默认是public属性的
4.虚函数和纯虚函数的区别：
纯虚函数在基类中没有被实现，虚函数在基类中有实现。
有纯虚函数的类不能实例化对象，必须在子类中实现了纯虚函数之后才可以实例化对象。
5.进程和线程：
进程是资源分配的最小单位，有独立的虚拟内存，线程是CPU调度的最小单位，线程共享进程的如堆内存，文件句柄，全局变量，代码段等资源。一个进程可以有多个线程组成，线程没有独立的资源，所以必须依赖进程运行。
进程的切换开销很大，需要切换页表全局目录，内核态堆栈，硬件上下文(寄存器)，刷新TLB，执行操作系统调度代码（还有缓存失效导致的缓存穿透到内存问题）。线程切换的开销较小，因为虚拟内存是不变的，不用切换TLB，没有缓存失效问题。
6.页表：
页：把进程空间和内存空间划成等带下的片，一般为4K。
进程访问虚拟内存，CPU执行时通过分页机制转换成物理内存访问，虚拟地址到物理内存的转换表称为页表，这个转换是个查表的过程。在进程调度过程中，上下文切换阶段会做页表的切换。
7.TLB（快表）:
TLB是一个内存管理单元用于改进虚拟地址到物理地址转换速度的缓存.
TLB是位于内存中的页表的cache，如果没有TLB，则每次取数据都需要两次访问内存,即查页表获得物理地址和取数据.
8.磁盘缓存：
将下载到的数据先保存于系统为软件分配的内存空间中，当保存到内存池中的数据达到一个程度时，便将数据保存到硬盘中。这样可以减少实际的磁盘操作，有效的保护磁盘免于重复的读写操作而导致的损坏
9.read/write和mmap的区别
read/write 1.访问文件，用户态->内核态 2.需要访问100字节，内核按照4K(页大小)存储在page cache中 3.用户从page cache中将数据拷贝到用户缓冲区。（两次拷贝，两次态的切换）
mmap将硬盘文件映射到内存中，即将page cache中的页直接映射到用户进程地址空间。和read/write的区别在与不需要在page cache和用户缓冲区之间拷贝
(内核会为每个文件单独维护一个page cache，用户进程对于文件的大多数读写操作会直接作用到page cache上，内核会选择在适当的时候将page cache中的内容写到磁盘上，这样可以大大减少磁盘的访问次数，从而提高性能)
10.进程通信：
1).管道 （半双工，一端读，一端写；只能用于父子进程和兄弟进程；看成特殊的文件，用read和write函数操作）int pipe(int fd[2])
2).FIFO （可用于无关系的进程通信，mkfilo(name,mode)，mode参数和open的mode一样）
3).消息队列 （是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标识。进程终止，消息队列内容不会删除）
int msgget(key, flag); int msgsnd(msgid, ptr, size, flag); int msgrcv(int msgid, ptr, size, type, flag; msgctl(id,…))
4).信号量 (信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据) 创建：semget(); 操作：semop();控制：semctl()
5).共享内存 （创建：shmget， 连接：shmat， 断开：shmdt， 控制：shmctl）
6).socket
11.线程通信：
1).互斥锁
2).自旋锁
3).读写锁
4).信号量
5).条件变量
6).volatile关键字
12.线程joinable状态和unjoinable状态
joinable状态下，当线程函数自己返回退出时或pthread_exit时都不会释放线程所占用堆栈和线程描述符。只有当你调用了pthread_join之后这些资源才会被释放；
unjoinable状态的线程，这些资源在线程函数退出时或pthread_exit时自动会被释放。
unjoinable状态设置有两种办法 一是可以在pthread_create时指定，二是线程创建后在线程中pthread_detach自己 pthread_detach(pthread_self())，状态改为unjoinable状态，确保资源的释放。
13.七层模型：
1).应用层：HTTP，FTP等
2).表示层：应用层产生的消息，并不会直接发送出去，会在表示层进行加密，压缩，并且制定加密的方式，压缩的方式等等。
3).会话层：总结就是会话交谈，是负责管理进程之间的会话。
4).传输层：TCP/UDP
5).网络层：简单的说主要就是加上一个源地址，目的地址;接着将数据放到链路层，注意这里的数据部分就是我们传输层上来的数据
6).链路层：我们需要包装物理地址，而物理地址我们怎么知道，这里就要用到ARP协议，根据ip地址查找物理地址
7).物理层：传输数据的媒介，这一层数据叫比特。数据通过光纤等介质，传输到了网络道路中，交换机会扒开数据。
14.4层模型：
1).应用层
2).传输层
3).网络层
4).数据链路层
15.程序编译过程:
预编译->编译->汇编->链接
16.死锁产生：
1).互斥条件（独占资源）
2).不可剥夺条件（资源不能被抢占）
3).请求和保持条件（申请新资源）
4).循环等待条件
17.避免死锁方法：
1).减少嵌套锁
2).正确的顺序获得锁，把获取锁的代码放在一个公共的方法里面，让这两个线程获取锁都是从我的公共的方法里面获取。
3).超时放弃
18.TCP/UDP UDP场景
游戏，视频，嵌入式设备
19.内存管理：静态存储区，栈区，堆区，代码区，常量字符区
20.虚拟内存
虚拟内存可以让程序拥有超过系统实际物理内存大小的可用内存空间
虚拟内存会为每个进程提供一个一致的，私有的地址空间，它让每个进程都拥有一片连续完整的内存空间，这样能更加有效管理内存并减少出错
虚拟内存的一个重要意义：定义了一个连续的虚拟地址空间，并将内存扩展到了硬盘空间
21.什么是虚拟内存？
第一层理解：
1、每个进程都有自己独立的4G内存空间，各个进程的内存空间具有类似的结构
2、 一个新进程建立的时候，将会建立起自己的内存空间，此进程的数据，代码等从磁盘拷贝到自己的进程空间，哪些数据在哪里，都由进程控制表中的task_struct记录，task_struct中记录中一条链表，记录中内存空间的分配情况，哪些地址有数据，哪些地址无数据，哪些可读，哪些可写，都可以通过这个链表记录。
3、每个进程已经分配的内存空间，都与对应的磁盘空间映射
第二层理解：
1、每个进程的4G内存空间只是虚拟内存空间，每次访问内存空间的某个地址，都需要把地址翻译为实际物理内存地址。
2、所有进程共享同一物理内存，每个进程只把自己目前需要的虚拟内存空间映射并存储到物理内存上。
3、进程要知道哪些内存地址上的数据在物理内存上，哪些不在，还有在物理内存上的哪里，需要用页表来记录。
4、页表的每一个表项分两部分，第一部分记录此页是否在物理内存上，第二部分记录物理内存页的地址（如果在的话）。
5、当进程访问某个虚拟地址，去看页表，如果发现对应的数据不在物理内存中，则缺页异常。
6、缺页异常的处理过程，就是把进程需要的数据从磁盘上拷贝到物理内存中，如果内存已经满了，没有空地方了，那就找一个页覆盖（页面置换），当然如果被覆盖的页曾经被修改过，需要将此页写回磁盘。
22.虚拟内存的优点
1、能在逻辑上扩大内存容量
2、既然每个进程的内存空间都是一致而且固定的，所以链接器在链接可执行文件时，可以设定内存地址，而不用去管这些数据最终实际的内存地址，这是有独立内存空间的好处
3、当不同的进程使用同样的代码时，比如库文件中的代码，物理内存中可以只存储一份这样的代码，不同的进程只需要把自己的虚拟内存映射过去就可以了，节省内存
4、在程序需要分配连续的内存空间的时候，只需要在虚拟内存空间分配连续空间，而不需要实际物理内存的连续空间，可以有效利用内存碎片。
事实上，在每个进程创建加载时，内核只是为进程“创建”了虚拟内存的布局，具体就是初始化进程控制表中内存相关的链表，实际上并不立即就把虚拟内存对应位置的程序数据和代码（比如.text .data段）拷贝到物理内存中，只是建立好虚拟内存和磁盘文件之间的映射就好（叫做存储器映射），等到运行到对应的程序时，才会通过缺页异常，来拷贝数据。还有进程运行过程中，要动态分配内存，比如malloc时，也只是分配了虚拟内存，即为这块虚拟内存对应的页表项做相应设置，当进程真正访问到此数据时，才引发缺页异常。
24.虚拟地址、线性地址、物理地址是如何转换的？
1、汇编代码编译成可执行文件后，每条指令的虚拟地址是该指令相对于所在段的偏移地址（关键词：分段）。
2、cpu寻址时，是按照（段寄存器：虚拟地址）这个格式计算的，这个加上段寄存器的值的地址就是所谓的线性地址。
3、这个线性地址仍然不是指令在内存中的实际地址，需要根据页表再次换算得到物理地址。页表里有一个字段记录这个页是否在内存中。（关键词：分页）
25.指针能不能访问0x0?
不能，属于保留区，禁止访问，用于处理一些指针错误或者空指针引起的异常情况。
26.什么时候会由用户态陷入内核态？
用户态切换到内核态的3种方式：a.系统调用 b.异常 c.外围设备的中断
27.分页大小的优缺点分析
CPU是通过寻址来访问内存的。32位CPU的寻址宽度是 0~0xFFFFFFFF ，计算后得到的大小是4G，也就是说可支持的物理内存最大是4G。
分页小相比分页大会更频繁发生缺页中断，浪费时间
TLB是有限的，这点毫无疑问。当超出TLB的存储极限时，就会发生 TLB miss，之后，OS就会命令CPU去访问内存上的页表。如果频繁的出现TLB miss，程序的性能会下降地很快。
为了让TLB可以存储更多的页地址映射关系，我们的做法是调大内存分页大小。
如果一个页4M，对比一个页4K，前者可以让TLB多存储1000个页地址映射关系，性能的提升是比较可观的。
也就是说如果分页大的话，TLB的命中率就会更高。
但是分页大，也是会有缺点的：
首先一个明显的缺点就是可能造成空间的浪费，因为你即便是仅仅存储两个字节大小的文件，也会占用一个页。
28.指针
1,int *p
2,int **p
3,int *p[10]
4,int (*p)[10]
5,int *p(int)
6,int (*p)(int)
7,int (*p[10])(int)
1.指向一个整数的指针。
2.指向一个整数指针的指针。
3.由10个指向整型数的指针构成的数组。
4.数组指针，可以理解为数组第一个元素的首地址。（数组在传参的时候会退化成指针）
5.一个简单的函数，有一个整型参数，返回一个整数类型指针。
6.一个指向函数的指针参数是整数，返回值是整数
7.一个有10个元素的指针数组，每个函数指针都有一个整数参数。
29.内存管理（C++）
C++内存管理分为三部分：内存分布，内存分配方式，内存回收处理。
对于分段式内存：c++程序设计的内存区从高到低分为：栈，堆，数据段，代码段；
堆栈是最难区分的问题：
(1). 管理方式不同
(2). 空间大小不同
(3). 能否产生碎片不同
(4). 生长方向不同
(5). 分配方式不同
(6). 分配效率不同
管理方式：对于栈来说大小和释放都有编译器管理，程序员可以管理的内存空间为堆区，但因为需要手动释放因此可能产生内存泄漏问题。
空间大小：一般来讲在32位系统下，堆内存可以达到4G的空间，从这个角度来看堆内存几乎是没有什么限制的。
碎片问题：对于堆来讲，频繁的new/delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序效率降低。对于栈来讲，则不会存在这个问题，因为栈是先进后出的队列，他们是如此的一一对应，以至于永远都不可能有一个内存块从栈中间弹出，在他弹出之前，在他上面的后进的栈内容已经被弹出。
生长方向：对于堆来讲，生长方向是向上的，也就是向着内存地址增加的方向；对于栈来讲，它的生长方向是向下的，是向着内存地址减小的方向增长。
分配方式：堆都是动态分配的，没有静态分配的堆。栈有2种分配方式：静态分配和动态分配。静态分配是编译器完成的，比如局部变量的分配。动态分配由alloca函数进行分配，但是栈的动态分配和堆是不同的，他的动态分配是由编译器进行释放，无需我们手工实现。
分配效率：栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是C/C++函数库提供的，它的机制是很复杂的，例如为了分配一块内存，库函数会按照一定的算法（具体的算法可以参考数据结构/操作系统）在堆内存中搜索可用的足够大小的空间，如果没有足够大小的空间（可能是由于内存碎片太多），就有可能调用系统功能去增加程序数据段的内存空间，这样就有机会分到足够大小的内存，然后进行返回。显然，堆的效率比栈要低得多。
30.野指针
“野指针”不是NULL指针，是指向“垃圾”内存的指针。人们一般不会错用NULL指针，因为用if语句很容易判断。但是“野指针”是很危险的，if语句对它不起作用
野指针产生原因：
1.声明之后未经初始化直接使用，初始化之后是个缺省的值，并不知道他的具体指向。
2.new/delete一个空间之后未对指向该空间的指针进行指空。
3.编程最常见的越界问题，超出了变量的作用域，容易覆盖其他程序的存储空间，很危险！！
31.new和malloc区别？
1.new/delete需要C++头文件支持，malloc/free是库函数支持。
2.new支持重载，malloc不支持重载。
3.malloc在内存分配需要声明内存大小，new根据申请对象的类的大小自行分配。
4.malloc返回值的类型为void*需要进行强制类型转换，new不需要。
5.new分配异常会抛出bac_alloc，malloc会返回NULL
6.new是在自由存储区申请内存，malloc是在堆上申请内存，自由存储区是个抽象概念，其实new的底层也是由malloc实现但是申请完我们就成为自由存储区，自由存储区为上层的概念不属于底层。
7.new 是为了opp编程引入的申请内存概念，因为在malloc申请内存时候都需要程序员去计算申请大小过于麻烦。
32.设计一个一个只在堆区分配内存的类？
class Onlyheap
{
public:
~Onlyheap();
static Onlyheap* getInit(){
//别忘了加*
return new Onlyheap; //new 一个出来
}
private://构造与拷贝构造私有化
Onlyheap(){
};
Onlyheap(const Onlyheap&);
};
33.设计一个只在栈区分配内存的类？
class Onlystack
{
public:
Onlystack(){
};
~Onlystack(){
};
private:
void* operator new(size_t); //加* 参数类型
void operator delete(void*);
};
34.可变长结构体
变长结构体的作用：
变长结构体的变长部分通常可以用来作为buffer，缓存数据。
变长结构体的空间释放是很方便的，只需要free(pv)， 而且不会造成内存泄露。
变长结构体使用起来更方便，不过，要小心越界。
35.为何不用指针代替变长结构体？
指针与变长结构体的区别：
1）位置方面：指针可以放在任何地方，但是变长结构体的变长部分一定要放在结构体的尾部；
2）内存占用方面：指针会占用一个指针大小的内存空间，但是变长数组不占内存，它只是一个占位符；
3）内存布局方面：指针指向的内存和结构体的内存可以是不连续的，但是变长部分和结构体的内存必须是连续的。
4）内存释放方面：使用指针，需要先释放指针所指向的内存，再释放整个结构体的内存，否则会造成内存泄漏；而使用变长结构体可以直接释放整个结构体的空间；
5）限制方面：指针可以用在C++的类中，而变长结构体不可以。因为有些编译器会将一些额外的信息放在类的最后，比如vptr或者虚基类的内容，使用了变长的类，就会把这部分的值改变，这种行为是未定义的。
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
struct v_struct {
int i;
int a[0];
};
struct msg {
char cmd; char len; int extraData[0]; };
int main(){
v_struct *pv = (v_struct *)malloc(sizeof(v_struct)+sizeof(int)* 100);
pv->a[50] = 100;
// 我故意访问越界了一个，但是没有报错是什么鬼_100改成101试试
// rep(i,0,101) pv->a[i]=i;
rep(i,0,100) pv->a[i]=i;
int cnt=0;
rep(i,0,100){
cnt++;
cout<<pv->a[i]<<" ";
if(cnt%10==0) puts("");
}
cout<<"\n可以访问pv->a[100],可能是原来的'/0'标识处,但是不能访问pv->a[101]"<<endl;
// 2020年6月5日16:43:53 第二次探究，发现又可以访问pv->a[101]
pv->a[101] = 101;
cout<<"error here: pv->a[101]: "<<pv->a[101]<<endl;
printf("sizeof int is equal to %u\n", (unsigned int)sizeof(int));
printf("sizeof v_struct is equal to %u\n", (unsigned int)sizeof(v_struct));
// 64bit电脑输出8
printf("%u\n", (unsigned int)sizeof(pv));
struct msg *clientMsg = (struct msg *)malloc(sizeof(struct msg));
clientMsg->cmd = 'l';
clientMsg->len = 12;
cout<< " sizeof(struct msg): " << sizeof(struct msg) << endl;
cout<< " sizeof(struct msg*): " << sizeof(struct msg*) << endl;
cout<< "before realloc , the sizeof(*clientMsg): " << sizeof(*clientMsg) << endl;
clientMsg = (struct msg *)realloc(clientMsg, sizeof(struct msg) + 12 );
cout<< "sizeof(char): " << sizeof(char) << endl;
cout<< "after realloc , the sizeof(*clientMsg): " << sizeof(*clientMsg) << endl;
*(clientMsg->extraData) =11;
cout<< "after realloc , add one , the sizeof(*clientMsg): " << sizeof(*clientMsg) << endl;
*(clientMsg->extraData + 1) = 22;
cout<< "after realloc , add two , the sizeof(*clientMsg): " << sizeof(*clientMsg) << endl;
*(clientMsg->extraData + 3) = 33;
cout<< "after realloc , add and exceed. the sizeof(*clientMsg): " << sizeof(*clientMsg) << endl;
return 0;
}
#include <iostream>
#include <string.h>
using namespace std;
struct s_one {
int s_one_cnt;
char* s_one_buf;
};
struct s_two {
int s_two_cnt;
char s_two_buf[0];
};
struct s_three {
int s_three_cnt;
char s_three_buf[1];
};
int main() {
//赋值用
const char* tmp_buf = "abcdefghijklmnopqrstuvwxyz";
int ntmp_buf_size = strlen(tmp_buf);
//<1>注意s_one 与s_two的大小的不同
cout << "sizeof(char *) = " << sizeof(char *) << endl; // 8
cout << "sizeof(s_one) = " << sizeof(s_one) << endl; // 8+8
cout << "sizeof(s_two) = " << sizeof(s_two) << endl; // 4
cout << "sizeof(s_three) = " << sizeof(s_three) << endl; // 5-->8结构体对齐
cout << endl;
//为buf分配 sizeof(tmp_buf) 个字节大小的空间
int ntotal_stwo_len = sizeof(s_two) + (1 + ntmp_buf_size) * sizeof(char);
int ntotal_sthree_len = sizeof(s_three) + ntmp_buf_size * sizeof(char);
//给s_one buf赋值
s_one* p_sone = (s_one*)malloc(sizeof(s_one));
memset(p_sone, 0, sizeof(s_one));
p_sone->s_one_buf = (char*)malloc(1 + ntmp_buf_size);
memset(p_sone->s_one_buf, 0, 1 + ntmp_buf_size);
memcpy(p_sone->s_one_buf, tmp_buf, ntmp_buf_size);
//给s_two buf赋值
s_two* p_stwo = (s_two*)malloc(ntotal_stwo_len);
memset(p_stwo, 0, ntotal_stwo_len);
memcpy((char*)(p_stwo->s_two_buf), tmp_buf,
ntmp_buf_size); //不用加偏移量，直接拷贝!
//给s_three_buf赋值
s_three* p_sthree = (s_three*)malloc(ntotal_sthree_len);
memset(p_sthree, 0, ntotal_sthree_len);
memcpy((char*)(p_sthree->s_three_buf), tmp_buf, ntmp_buf_size);
cout << "p_sone->s_one_buf = " << p_sone->s_one_buf << endl;
cout << "p_stwo->s_two_buf = " << p_stwo->s_two_buf << endl;
cout << "p_sthree->s_three_buf = " << p_sthree->s_three_buf
<< endl; //不用加偏移量，直接拷贝!
cout << endl;
//<2>注意s_one 与s_two释放的不同！
if (NULL != p_sone->s_one_buf) {
free(p_sone->s_one_buf);
p_sone->s_one_buf = NULL;
if (NULL != p_sone) {
free(p_sone);
p_sone = NULL;
}
cout << "free(p_sone) successed!" << endl;
}
if (NULL != p_stwo) {
free(p_stwo);
p_stwo = NULL;
cout << "free(p_stwo) successed!" << endl;
}
if (NULL != p_sthree) {
free(p_sthree);
p_sthree = NULL;
cout << "free(p_sthree) successed!" << endl;
}
return 0;
}
36.MTU和MSS的区别
MTU（Maximum Transmission Unit）最大传输单元，在TCP/IP协议族中，指的是IP数据报能经过一个物理网络的最大报文长度，其中包括了IP首部(从20个字节到60个字节不等)，一般以太网的MTU设为1500字节，加上以太帧首部的长度14字节，也就是一个以太帧不会超过1500+14 = 1514字节。
MSS
MSS（Maximum Segment Size，最大报文段大小，指的是TCP报文（一种IP协议的上层协议）的最大数据报长度，其中不包括TCP首部长度。MSS由TCP链接的过程中由双方协商得出，其中SYN字段中的选项部分包括了这个信息。如果MSS+TCP首部+IP首部大于MTU，那么IP报文就会存在分片，如果小于，那么就可以不需要分片正常发送。
一般来说，MSS = MTU - IP首部大小 - TCP首部大小
37.为什么要有mac地址，为什么要有arp协议？
MAC地址是物理地址，工作在数据链路层，一旦出厂时由厂商确定并烧制入网络设备的EPROM中就具有了固定的全球唯一的地址，任何时候任何条件都不会改变，虽说使用起来不太方便，且描述的是较低层的数据链路通信细节，但在任何时候都可用于数据通信寻址。
为啥要arp：
因为通信要mac,所以要解析ip，arp(Address Resolution Protocol)
问题：既然每个以太网设备在出厂时都有一个唯一的MAC地址了，那为什么还需要为每台主机再分配一个IP地址呢？或者说为什么每台主机都分配唯一的IP地址了，为什么还要在网络设备（如网卡，集线器，路由器等）生产时内嵌一个唯一的MAC地址呢？
解答：主要原因基于以下几点：
（1）IP地址的分配是根据网络的拓扑结构，而不是根据谁制造了网络设置。若将高效的路由选择方案建立在设备制造商的基础上而不是网络所处的拓扑位置基础上，这种方案是不可行的；
（2）当存在一个附加层的地址寻址时，设备更易于移动和维修。例如，如果一个以太网卡坏了，可以被更换，而无须取得一个新的IP地址。如果一个IP主机从一个网络移到另一个网络，可以给它一个新的IP地址，而无须换一个新的网卡；
（3）无论是局域网，还是广域网中的计算机之间的通信，最终都表现为将数据包从某种形式的链路上的初始节点出发，从一个节点传递到另一个节点，最终传送到目的节点。数据包在这些节点之间的移动都是由ARP协议负责将IP地址映射到MAC地址上来完成的。
mac是网卡的唯一标识，设备可以使用不同的ip，不过始终是一个mac
然后交换机通过转化表建立交换机端口和接入交换机的那些设备的mac之间的映射
arp是同一个网段内，把ip地址转化成mac地址的协议，arp表就是同一网段中ip地址到mac的映射，没有则进行一次arp请求，arp请求会找到同一网段中可以到达请求ip的地址的那个设备的mac(结合后面的路由表看)
然后路由表是基础网络拓扑生成的，主要是根据ip以及路由表中的内容确定下一跳是哪个设备，确定设备之后通过arp获取那个设备的mac，然后封装好就可以转发了
38.send函数可以直接发送结构体吗？
一般是可以的，但是可能会因为struct数据设置得不好，导致受到字节对齐的影响，可能会导致计算会出问题
39.大端和小端（Big endian and Little endian）
一、大端和小端的问题
对于整型、长整型等数据类型，Big endian 认为第一个字节是最高位字节（按照从低地址到高地址的顺序存放数据的高位字节到低位字节）；而 Little endian 则相反，它认为第一个字节是最低位字节（按照从低地址到高地址的顺序存放据的低位字节到高位字节）。
记忆：大端_低址高字节_像左到右
例如，假设从内存地址 0x0000 开始有以下数据：
0x0000 0x0001 0x0002 0x0003
0x12 0x34 0xab 0xcd
如果我们去读取一个地址为 0x0000 的四个字节变量，若字节序为big-endian，则读出结果为0x1234abcd；若字节序为little-endian，则读出结果为0xcdab3412。
如果我们将0x1234abcd 写入到以 0x0000 开始的内存中，则Little endian 和 Big endian 模式的存放结果如下：
地址 0x0000 0x0001 0x0002 0x0003
big-endian 0x12 0x34 0xab 0xcd
little-endian 0xcd 0xab 0x34 0x12
一般来说，x86 系列 CPU 都是 little-endian 的字节序，PowerPC 通常是 big-endian，网络字节顺序也是 big-endian还有的CPU 能通过跳线来设置 CPU 工作于 Little endian 还是 Big endian 模式。
对于0x12345678的存储：
小端模式：（从低字节到高字节）
地位地址 0x78 0x56 0x34 0x12 高位地址
大端模式：（从高字节到低字节）
地位地址 0x12 0x34 0x56 0x78 高位地址
40.大端小端转换方法
htonl() htons() 从主机字节顺序转换成网络字节顺序
ntohl() ntohs() 从网络字节顺序转换为主机字节顺序
Big-Endian转换成Little-Endian：
#define BigtoLittle16(A) ((((uint16)(A) & 0xff00) >> 8) | (((uint16)(A) & 0x00ff) << 8))
#define BigtoLittle32(A) ((((uint32)(A) & 0xff000000) >> 24) | (((uint32)(A) & 0x00ff0000) >> 8) | \
(((uint32)(A) & 0x0000ff00) << 8) | (((uint32)(A) & 0x000000ff) << 24))
41.大端小端检测方法
联合体union的存放顺序是所有成员都从低地址开始存放，利用该特性就可以轻松地获得了CPU对内存采用Little-endian还是Big-endian模式读写。
static union {
char c[4]; unsigned long mylong; } endian_test = {
{
'l', '?', '?', 'b' } };
#define ENDIANNESS ((char)endian_test.mylong)
42.复原IP地址
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
#define per(i, b, a) for(int i = int(b); i >= int(a); --i)
#define mem(x, y) memset(x, y, sizeof(x))
#define SZ(x) x.size()
#define mk make_pair
#define pb push_back
#define fi first
#define se second
const ll mod=1000000007;
const int inf = 0x3f3f3f3f;
inline int rd(){
char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){
x=x*10+c-'0';c=getchar();}return x*f;}
inline ll qpow(ll a,ll b){
ll ans=1%mod;for(;b;b>>=1){
if(b&1)ans=ans*a%mod;a=a*a%mod;}return ans;}
class Solution {
public:
void dfs(const string& s,string cur,int i){
// sz是用掉的尺寸
// left_sz是剩下的
int sz = i <= 1 ? cur.size() : cur.size()-(i-1);
int left_sz = s.size() - sz;
if(3 == i){
// cout<< "1 here i == 3 "<<endl;
if(left_sz<=0 || left_sz > 3) return;
string sub = s.substr(sz,left_sz);
// cout<< "2 here i == 3, sub :" <<sub<<endl;
int tp = atoi(sub.c_str());
if(tp!=0 && sub[0]=='0') return;
if(tp==0 && sub.size()>1) return;
if(tp > 255) return ;
// cout<< "3 here i == 3 "<<endl;
ans.push_back(string(cur+'.'+sub));
}
else if(2 == i){
if(left_sz<2 || left_sz>6) return;
for(int k=1;k<=3;k++){
string sub = s.substr(sz,k);
// cout<< "2 here i == 2, sub :" <<sub<<endl;
int tp = atoi(sub.c_str());
if(k==3 && tp>255) return;
if(tp!=0 && sub[0]=='0') return;
if(tp==0 && sub.size()>1) return;
dfs(s,cur+'.'+sub,3);
}
}
else if(1 == i){
if(left_sz<3 || left_sz>9) return;
for(int k=1;k<=3;k++){
string sub = s.substr(sz,k);
// cout<< "2 here i == 1, sub :" <<sub<<endl;
int tp = atoi(sub.c_str());
if(k==3 && tp>255) return;
if(tp!=0 && sub[0]=='0') return;
if(tp==0 && sub.size()>1) return;
dfs(s,cur+'.'+sub,2);
}
}
else if(0 == i){
if(left_sz<4 || left_sz>12) return;
for(int k=1;k<=3;k++){
string sub = s.substr(sz,k);
// cout<< "2 here i == 0, sub :" <<sub<<endl;
int tp = atoi(sub.c_str());
if(k==3 && tp>255) return;
if(tp!=0 && sub[0]=='0') return;
if(tp==0 && sub.size()>1) return;
dfs(s,sub,1);
}
}
}
vector<string> restoreIpAddresses(string s) {
ans.clear();
dfs(s,"",0);
return ans;
}
private:
vector<string> ans;
};
class Solution_for {
public:
bool substr_ok(string sub){
int tp = atoi(sub.c_str());
int k = sub.size();
if(k==3 && tp>255) return false;
if(tp!=0 && sub[0]=='0') return false;
if(tp==0 && k>1) return false;
return true;
}
vector<string> restoreIpAddresses(string s) {
vector<string> ans;
int sz = s.size();
for(int i=1;i<4;i++){
if(i > sz) continue;
string sub1 = s.substr(0,i);
if(!substr_ok(sub1)) continue;
for(int j=1;j<4;j++){
if(i+j > sz) continue;
string sub2 = s.substr(0+i,j);
if(!substr_ok(sub2)) continue;
for(int k=1;k<4;k++){
if(i+j+k > sz) continue;
string sub3 = s.substr(i+j,k);
if(!substr_ok(sub3)) continue;
int left_sz = sz - (i+j+k);
if(left_sz<=0 || left_sz>3) continue;
// for(int p=1;p<=left_sz;p++){
string sub4 = s.substr(i+j+k,left_sz);
if(!substr_ok(sub4)) continue;
ans.push_back(sub1+'.'+sub2+'.'+sub3+'.'+sub4);
// }
}
}
}
return ans;
}
};
int main(){
Solution test;
// string s = "25525511135";
string s = "010010";
vector<string> ans;
ans = test.restoreIpAddresses(s);
for(auto x:ans) cout<<x<<endl;
return 0;
}
43.希尔排序
O(nlog^2n) 不稳定
int shellSort(int arr[], int n){
for (int gap = n/2; gap > 0; gap /= 2){
for (int i = gap; i < n; i += 1){
int temp = arr[i];
int j;
// 注意这里的j>=gap的时候还是会重复比较
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
}
return 0;
}
43.堆排序O(nlog n)不稳定
void heapify(int arr[], int n, int i) {
// 这里对arr[]中序列化的值按照类似满二叉树的逐层读取的规则来的
int largest = i; // 将最大元素设置为堆顶元素
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// 如果 left 比 root 大的话
if (l < n && arr[l] > arr[largest]) largest = l;
// I如果 right 比 root 大的话
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
// 递归地定义子堆,当子堆的最大被上层取走之后,那么要更新子堆
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
// 建立堆
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
// 一个个从堆顶取出元素
for (int i = n - 1; i >= 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
44.手写string
#include <string.h>
#include <vector>
class String {
public:
String() : data_(new char[1]) {
*data_ = '\0'; }
String(const char* str) : data_(new char[strlen(str) + 1]) {
strcpy(data_, str);
}
String(const String& rhs) : data_(new char[rhs.size() + 1]) {
strcpy(data_, rhs.c_str());
}
/* Delegate constructor in C++11
String(const String& rhs)
: String(rhs.data_)
{
}
*/
~String() {
delete[] data_; }
/* Traditional:
String& operator=(const String& rhs)
{
String tmp(rhs);
swap(tmp);
return *this;
}
*/
String& operator=(String rhs) // yes, pass-by-value
{
swap(rhs);
return *this;
}
// C++ 11
// 如果是右值传递，那么就会调用这个函数
String(String&& rhs) : data_(rhs.data_) {
rhs.data_ = nullptr; }
String& operator=(String&& rhs) {
swap(rhs);
return *this;
}
// Accessors
size_t size() const {
return strlen(data_); }
const char* c_str() const {
return data_; }
void swap(String& rhs) {
std::swap(data_, rhs.data_); }
private:
char* data_;
};
void foo(String x) {
}
void bar(const String& x) {
}
String baz() {
String ret("world");
return ret;
}
int main() {
String s0;
String s1("hello");
String s2(s0);
String s3 = s1;
s2 = s1;
foo(s1);
bar(s1);
foo("temporary");
bar("temporary");
String s4 = baz();
std::vector<String> svec;
svec.push_back(s0);
svec.push_back(s1);
svec.push_back(baz());
svec.push_back("good job");
}
45.红黑树的题
https://www.cnblogs.com/wuchanming/p/4444961.html
46.排序算法是稳定的意思是关键字相同的记录排序前后的相对位置不发生改变，对于下列排序算法：
1)插入排序 2)基数排序 3)归并排序 4)冒泡排序 5)堆排序
包含所有稳定算法的选项为：
1)2)3)4)
转载：https://blog.csdn.net/qq_35927741/article/details/117449718