C/C++
数组的指针形式
a[i][j] 表示有i个数组，每个数组中又是一个j个数据的数组，即一维数组的数组
*(a+i) 代表了第i个数组的首地址
*(a+i) + j 表示了第i个数组中第j个元素的地址
*(*(a+i)+j) 表示a[i][j]这个元素
- 二维数组作为参数时，应当传递
func(int a[][10])这种形式，不指定列就会报错，因为从实参传递来的是数组的起始地址，如果在形参中不说明列数，编译器将无法定位元素的的位置。
static、new、delete
static 修饰的变量，其在编译阶段就分配了内存空间，一个局部静态变量，函数没有调用时，他就存在了
程序结束时。static变量才会自动释放
new 会触发一个对象的构造函数，malloc不会，malloc还需要手动指定申请的空间大小
delete 会触发析构函数,free则只是简单的释放空间，有可能会导致一些对象的指针没有释放，造成内存泄漏。
static char * p = new char[100];
delete p;
//delete[] p;
上述代码也不会出错，当用delete来释放用new int[]申请的内存空间时，由于其为基本数据类型没有析构函数，所以使用delete与delete []相同，两者都会释放申请的内存空间。若是自定义的数据类型，有析构函数时，用new []申请的空间，必须要用delete []来释放，因为要delete []时会逐一调用对象数组的析构函数，然后释放空间https://blog.csdn.net/m0_46613023/article/details/114867406
memcpy memmove
作用：拷贝一定长度的内存内容。
#include <string.h>
void *memmove(void *dest, const void *src, size_t n);
/*
DESCRIPTION
The memmove() function copies n bytes from memory area src to memory area dest. The memory areas may overlap: copying takes place as though the bytes in src are first copied into a temporary array that does not overlap src or dest, and the bytes are then copied from the temporary array to dest.
*/
//大意是先拷贝到一个不与原、目的重叠的临时区域，然后再拷贝到目的地。
//当然实际上能够发生重叠的只有一种情况，目的区域的起始位置在源区域之上，逐步复制的过程中，源区域后半段就会被改变，从而出现错误
//只要从后往前复制也能解决这个问题
void * mymemmove(void *dest, const void *src, size_t n){
char *s_dst = (char*)dst;
char *s_src = (char *)src;
if(s_dst > s_src && (s_src + n > s_dst)){//此时表示有内存发生重叠
s_dst = s_dst+n-1;
s_src = s_src+n-1;
while(n--){
*s_dst-- = *s_src--;
}
}else{
while(n--){
*s_dst++ = *s_src++;
}
}
}
#include <string.h>
void *memcpy(void *dest, const void *src, size_t n);
/*
DESCRIPTION
The memcpy() function copies n bytes from memory area src to memory area dest. The memory areas must not overlap. Use memmove(3) if the memory areas do overlap.
*/
void * mymemcpy(void *dest, const void *src, size_t n){
char * tmp = (char *)dst;
char * s_src = (char *)src;
while(n--){
*tmp++ = *s_src++;
}
return dest;
}
memcpy要求拷贝的内存不能重叠memmove对于源和目的有重叠部分的区域时，可以完成拷贝。
atoi实现
- 清除前置空格
- 解析符号
- 输出结果
int atoi(const char * str){
int neg = 1;
int result = 0;
const char* ptr = str;
while(*ptr == ' '){
ptr++;
}
if(*ptr == '-' || *ptr == '+'){
if(ptr == '-'){
neg = -1;
}
ptr++;
}
while(*ptr >= '0' && *ptr <= '9'){//循环，注意递增
result = result*10 + (*ptr - '0');
ptr++;
}
return result * neg;
}
strcpy和memcpy的区别
1.复制内容不同，strcpy只能复制字符串，还会复制字符串的结束符，而memcpy可以复制任意类型的内容。
2.复制方法不同，strcpy不需要指定长度，遇到` `就会截至，当然这也导致其容易溢出，而memcpy需要指定长度。
#include <string.h>
char *strcpy(char *dest, const char *src);
char *strncpy(char *dest, const char *src, size_t n);
/*
DESCRIPTION
The strcpy() function copies the string pointed to by src, including the terminating null byte (' '), to the buffer pointed to by dest. The strings may not overlap, and the destination string dest must be large enough to receive the copy. Beware of buffer overruns! (See BUGS.)
The strncpy() function is similar, except that at most n bytes of src are copied. Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.
If the length of src is less than n, strncpy() writes additional null bytes to dest to ensure that a total of n bytes are written.
A simple implementation of strncpy() might be:
char *
strncpy(char *dest, const char *src, size_t n)
{
size_t i;
for (i = 0; i < n && src[i] != ' '; i++)
dest[i] = src[i];
for ( ; i < n; i++)
dest[i] = ' ';
return dest;
}
RETURN VALUE
The strcpy() and strncpy() functions return a pointer to the destination string dest.
*/
//自我实现
char * strcpy(char * dest,const char * src){
if(NULL == dest && NULL == src){
return NULL;
}
char * ret = dest;
const char * _src = src;
while((*dest++ = *_src++) != ' ');
return ret;
}
char* strncpy(char * dest,const char * src,size_t n){
if(NULL == dest && NULL == src){
return NULL;
}
size_t i;
for (i = 0; i < n && src[i] != ' '; i++)
dest[i] = src[i];
for ( ; i < n; i++)//剩余部分全部填充
dest[i] = ' ';
return dest;
}
数字转二进制
vector<int> transform(int &num){
//int 范围 0-256 即8位
vector<int> result;
for(int i=7;i<=0;i--){
result.push_back((num >> i) & 1);//右移一位除以2
}
return result;
}
sizeof 与 strlen
const char * str = "123";
cout << "sizeof : " << sizeof(str) << endl;//4 取的是指针的大小
cout << "strlen : " << strlen(str) << endl;//3 不包含
char str2[] = "12345";
cout << "sizeof: " << sizeof(str2) << endl;//6 传递数组名时，计算数组的大小,包含
cout << "sizeof: " << sizeof(str2[0]) << endl;//1 一个字符的大小
cout << "strlen：" << strlen(str2) << endl;//5 不包含
cout << "sizeof: " << sizeof("123456") << endl;//7
cout << "strlen : " << strlen("123456") << endl;//6
C++面向对象
C++类和结构体
结构体和类都可以定义成员函数
类中成员默认是private，结构体中的成员默认是public
两者都可以使用malloc和new来创建，但推荐使用new
两者都可以定义虚函数，都可以继承
C实现C++类的面向对象特性
- 封装：使用结构体，属性就是结构体的属性，方法使用函数指针
- 继承：结构体嵌套！
- 多态：父类与子类方法的函数指针不同
虚函数、虚表、虚函数指针
成员初始化列表
优点：少了一次调用默认构造函数地过程。
必须使用初始化列表地场合：
- 常量成员，常量成员只能初始化，不能赋值，必须放在初始化列表中
- 引用类型，引用必须在定义地时候初始化，并且不能够重新赋值。
- 没有默认构造函数的类类型，因为使用初始化列表可以不必调用默认构造函数来初始化。
不能使用初始化列表地场合：
- 数组，数组必须在函数体内进行初始化
const修饰指针不同位置
const int * a; //可以修改指针的指向，但是指针指向的值不能够修改
int * const a; //this指针形式，指针式常量，不能改变，但其指向的数据却可以改变
C++类中
void myfunc() const{
这样this指针就是 const class * const this;类型 不能修改其指向，且指针指向的值也不能修改
}
const修饰引用
STL
insert
习惯插入于指定位置之前。
vector
-
vector push_back emplace_back都是向尾部添加数据
-
emplace_back() 和 push_back() 的区别，就在于底层实现的机制不同。push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）； 而 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。
vector push_back()的过程
若容量已经满了，首先申请一个更大的存储空间，一般是增加当前容量的50%或者100%，然后将旧内存空间的内容，按照原来的顺序放到新的空间。
最后将旧内存空间的内容释放掉，本质上其存储空间不会释放，只是删除了里面的内容。
- vector扩容的过程可以发现，扩容后，相关指针，引用，迭代器都会失效。
vector push_back()扩容时怎么把元素拷贝到新地址
- 按照一定的规则计算新的空间大小，然后分配一段内存。
- 将原vector拷贝到新的vector
- 然后释放并且析构原来的vector
- 调整迭代器，指向新的vector。
- vector一旦引起空间的重新配置，原来的迭代器就失效了。
vector的erase(iter) 与 algorihtm的remove的差别
vector<int> nums = { 1,2,3,4,5,6,7,8,9 };
vector<int> num2 = { 1,2,3,4,5,6,7,8,9 };
cout << "delete before:" << endl;//1 2 3 4 5 6 7 8 9
for (auto i : nums) {
cout << i << " ";
}
cout << endl;
auto iter = nums.begin();
iter += 3;
nums.erase(iter);
cout << "delete end:" << endl;//1 2 3 5 6 7 8 9
for (auto i : nums) {
cout << i << " ";
}
cout << endl;
///////////////////////
cout << "delete before:" << endl;//1 2 3 4 5 6 7 8 9
for (auto i : num2) {
cout << i << " ";
}
cout << endl;
remove(num2.begin(), num2.end(), 3);
cout << "delete end:" << endl;//1 2 4 5 6 7 8 9 9
for (auto i : num2) {
cout << i << " ";
}
cout << endl;
/////////////////////////
cout << "delete before:" << endl;//0 1 0 2 0 3 0 4
for (auto i : num3) {
cout << i << " ";
}
cout << endl;
remove(num3.begin(), num3.end(), 0);
cout << "delete end:" << endl;//1 2 3 4 0 3 0 4
for (auto i : num3) {
cout << i << " ";
}
cout << endl;
- erase是彻底删除那个元素，迭代器再也不能够访问。
- 而remove将对应的值删除之后，容器元素个数没有减少，只是将每一个不和对应值相等的元素拷贝到前面的位置！！！
reserve和resize
- reserve是改变容器的容量，也就是capacity，如果n大于当前的容量，就会分配空间扩增容量，否则不做任何处理。
- resize是直接改变当前容器的元素个数
list
-
每次插入或者删除一个元素，就配置或者释放一个元素空间。
-
list对空间的运用有绝对的精准。
-
list对于任何位置的元素的插入和删除，永远是常数时间。
-
插入删除都不会造成原有的迭代器失效。
list是双向链表，环状双向链表，只需要一个指针
- 尾端刻意置于一个空白节点，让哪个指针指向那里，就符合了STL前闭后开的区间要求。
list unique()
原理：移除数值相同的连续元素！比较相邻的两个元素，然后移除后面那个。
所以去重之前要先用自己的sort函数。
STL算法的sort只接受 随机访问迭代器
list splice() 接合函数
list merge() 合并函数
- 将参数合并到自己本身，两个链表都要预先进行递增排序！
deque
- vector是单向开口容器的连续线性空间，vector头部插入删除效率很差
- deque是双向开口的连续线性空间
- 允许常数时间内对头部元素进行插入删除
- 没有容量的概念：动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。
- 也提供了随机访问迭代器
- deque排序最高效率：复制到vector，然后再复制回去
deque中控器
采用一小段连续地空间作为中控器，然后每个元素都是指针，指向一段较大地连续线性空间，这些空间才是其主体。
map与unordered_map
区别：
- 头文件不同：
<map>与<unordered_map> - 内部实现不同：
- map红黑树，一种非严格的平衡二叉树，map内部元素会自动排序
- unordered_map内部哈希表，查找O(1)，但是建立哈希表比较费时间，无序排列
map插入方式
maps[key] = value;//这种方式可以覆盖掉对应的原值，算法题常用maps.insert(make_pair(key,value));maps.insert(map<>::value_type(key,value));maps.insert(pair(key,value));
map遍历删除数据
map<Key, int, cmp>::iterator it = keymap.begin();
for (; it != keymap.end();) {//这里不再有it++！！！
if (shuolddel(it)) {
keymap.erase(it++);//erase会返回下一个元素的迭代器
//或者 it = keymap.erase(it);
}
else {
it++;
}
}
//解释：it++ 拷贝旧的it，自增，返回旧的it
/*
if (it->second % 2 == 1) {
keymap.erase(it);
}
it++; //错误！迭代器已经失效
*/
C++11特性
自动类型推导auto
隐式类型推导发生于编译阶段，像python这种语言的类型推导发生在运行的时候。
auto x = 5;//int
auto pi = new auto(5);//int * auto可以用于new操作符
const auto u = 6;//int
const r;//错误
auto声明的变量必须马上初始化，以便让编译器推断出它的实际类型。
int x = 0;
const auto e = x;//auto = int
auto f = e;//f --> int而非const int
const auto & g = x; //g --> const int &
auto& h = g; //h --> const int &
- 当不声明为指针和引用时，auto的推导结果和初始化表达式抛弃引用和
const volatile一致。 - 当声明为指针或者引用时，将保持
const volatile。 - auto不能用于函数参数，不能用于类的非静态成员，可用于类的静态成员。auto不能推导出模板类型。
自动类型推导 decltype
用来在编译时推导出一个表达式的类型，decltype(exp)，exp是表达式。decltype(a+b)
- 一般都会保留
const volatile类型。
const int & i= x;
decltype(i) j = y;//j ->const int &
- 若exp是标识符或者类访问表达式
Class::static_member，则推导类型和exp一致，会保留const volatile类型。 - 若exp是函数调用，则推导类型与函数返回值相同。
- 对于函数返回纯右值，
const int func()，会消去const volatile类型
- 对于函数返回纯右值，
- 其他情况下，若exp是一个左值，则推导出exp类型的左值引用，否则就是exp类型。
struct Foo{int x;};
const Foo foo = Foo();
decltype(foo.x) a = 0;//a->int
decltype( (foo.x) ) b = a;//b -> const int & ,foo.x是左值，()表达式也是左值，则是一个左值引用。 foo 是const Foo ,则 foo.x是const int类型
int n = 0,m = 0;
decltype(n+m) c = 0;//c -> int n+m返回一个右值
decltype(n+=m) d = c;//d -> int & n+=m返回一个左值
返回类型后置语法
来解决函数返回值类型依赖于参数而导致难以确定返回值类型的问题。
template <typename T,typename U>
auto add(T t,U u) -> decltype(t+u)
{
return t+u;
}
///////////
int &foo(int & i);
float foo(float& f);
template <typename T>
auto func(T& val) -> decltype(foo(val))
{
return foo(val);
}
using别名取代typedef
typedef unsigned iny uint_t;
using uint_t = unsigned int;
using常用于模板之中。
列表初始化
class Foo{
public:
Foo(int){}
private:
Foo(const Foo &);
};
Foo a1(123);
Foo a2 =123;//错误
Foo a3 = {123};//虽然使用等号仍然是列表初始化，私有的拷贝构造不会影响
Foo a4{123};//写不写 =无影响
int a5 = {3};
int a6{3};
- stl中的容器是
std::initializer_list类模板来支持的。 - 自定义类可以通过重载构造函数使用上述类模板作为参数来完成。
基于范围的for循环
vector<int> arr = {1,2,3};
for(auto n : arr){//n表示arr中的一个元素，auto则是自动类型推导
cout<<n<<endl;
}
for(auto& n : arr){//想要修改，需要使用引用
cout<<n++<<endl;
}
- auto类型自动推导出的是容器的
value_type，而不是迭代器。 :之后的表达式，可以是函数，返回一个容器，但是只会执行一次。- 迭代器类 --》 p61往前
可调用对象包装器 std::function
std::bind绑定器
lambda表达式
函数式编程
- 声明式编程风格，就地匿名定义目标函数或函数对象，不需要额外写一个命名函数或者函数对象，有更好的可读性和可维护性。
- 简洁，高效，可实现功能闭包，使程序更加灵活。
语法：
[ capture ] (params) opt -> ret { body; };
- capture 捕获列表
- [] 不捕获任何变量
- [&] 捕获外部作用域所有变量，并作为引用在函数体中使用。按引用捕获
- [=] 捕获外部作用域所有变量，并作为副本在函数体中使用。按值捕获
- [=, &foo] 按值捕获外部作用域所有变量，并按引用捕获foo。
- [bar] 按值捕获bar变量，同时不捕获其他变量。
- [this] 捕获当前类中的this指针，让lambda表达式拥有和当前类成员函数同样的访问权限。如果使用了&或者=，就默认添加此选项，捕获this的目的是可以在lambda中使用当前类的成员函数和成员变量。
- params 参数表，无参数时可以省略
- opt 函数选项
- ret 返回值类型，可以省略
- body 函数体
- C++允许省略lambda表达式的返回值定义。编译器会根据返回值自动推导
auto f = [](int a) -> int {return a+1;};
cout<<f(1)<<endl;
按值捕获，得到的变量是lambda定义时的值，如果想要去修改按值捕获的外部变量，需要显示指明表达式为mutable。
- 此时必须写明参数列表，即使没有参数
int a = 10;
//auto f = [=]() {return a++; };//不可以，不能修改
//auto f = [&]() {return a++; };//可以
auto f = [=]()mutable {return a++; };//可以
cout << a << endl;//10
a++;
cout << a << endl;//11
cout << f() << endl;//10
cout << a << endl;//11
元组 tuple
相当于一个灵活的轻量级小结构体。
左值和右值
- 左值，指表达式结束后依然存在的持久对象。
- 右值，表达式结束之后不再存在的临时对象。
- c++11中的右值：将亡值 xvalue，纯右值 prvalue。
- 纯右值：非引用返回的临时变量，运算表达式产生的临时变量，原始字面量，lambda表达式
- 将亡值：将要被移动的对象，T&& 函数返回值，
std::move返回值和转换为T&& 的类型的转换函数返回值。
int i = 0;
//i 左值
//0 字面量 右值
无论声明左值还是右值引用，都必须立即初始化，引用本身不拥有绑定对象的内存，只是该对象的一个别名。
- 左值引用：常规引用方式，一般表示对象的身份！
- 右值引用：即绑定到一个右值（一个临时对象、将要销毁的对象）的引用，一般表示对象的值。
T &&- 右值不具名，只能通过引用的方式找到它。
- 通过右值引用的声明，该右值重获新生，其声明周期与右值类型引用类型变量的生命周期相同，只要引用变量还活着，临时值就将活着。
- 右值引用可实现转移语义和精确传递
- 消除两个对象交互时不必要的对象拷贝，节省运算存储资源、提高效率
- 能够更简洁明确地定义泛型函数
常量左值引用，是一个万能的引用类型，可接受左值、右值、常量左值和常量右值。
const A& a = ...
auto &&或者函数模板T&&可将其视作一种未定的引用类型，可以用左值或者右值初始化，但是其必须要初始化！！
编译器会将已经命名的右值引用视作左值，而将未命名的右值引用视为右值。
右值引用作用
在某些操作中，会返回一个临时对象，若是直接赋值给一个外部对象，就会触发拷贝构造或者重载=赋值函数，然后临时对象再析构掉，这样会带来性能的损耗。
使用右值引用，避免临时对象的拷贝。
移动语义，可以将资源，堆、系统对象等通过浅拷贝方式从一个对象转移到另一个对象！这样能够减少不必呀的临时对象的创建、拷贝和销毁，可以大幅提高C++应用程序的性能，能够消除临时对象的维护对性能的影响。
一般右值引用的构造函数参数不加const，因为要对其修改
而左值常量引用要加const，
一般这两个引用都要提供，防止右值引用不成，还有拷贝来提供。
std::move
可以将一个左值转换成一个右值引用。
拷贝构造时为了避免浅拷贝，可能会需要深拷贝，有些代码返回一个临时变量，然后再通过临时变量构造一个新的对象，而临时变量在拷贝构造完成之后就销毁了。
- 这样会带来额外的损耗，使用移动构造，其参数是
A&&。 - p89
move将对象的状态或者所有权从一个对象转移到另一个对象，只是转移，没有拷贝！！
- 其唯一的功能是将一个左值强制转换成一个右值引用！方便我们使用移动语义。
std::list <std::string> token;//临时容器
std::list<std::stirng> t = token;//代价很大
std::list<std::stirng> t = std::move(token);
forward完美转发
一个右值引用作为函数形参，在函数内部转发该参数时，它又变成了左值！
std::forward可以将参数完全按照模板的参数类型，保持参数的左值、右值特性来转发。
emplace
emplace函数可以通过直接构造对象的方式避免内存的拷贝和移动。
is_base_of 判断两种类型是不是继承关系
智能指针
自动删除分配内存，不需要手动释放。
智能指针是存储指向动态分配内存对象指针的类，用于生存期控制，能够确保在离开指针所在作用域时，自动正确地销毁动态分配地对象，防止内存泄漏。
通用实现方式：引用计数，每使用它一次，内部计数+1，每析构一次，内部引用计数减1.减为0，删除所指向地内存。
向 linux地打开文件表、共享内存地关联个数
shared_ptr
每一个shared_ptr的拷贝都指向相同的内存，在最后一个shared_ptr 析构时，才会被释放！
陷阱
- 不要用一个原始指针初始化多个shared_ptr。
shared_from_this()这种方式返回this指针！
unique_ptr
独占的智能指针，不允许其他智能指针共享内部的指针，也不能两者unique指针赋值！
- 可以使用移动语义完成赋值！
weak_ptr
主要用来监视shared_ptr，不是使引用计数加1，它不管理shared_ptr内部的指针，主要是监视shared_ptr的生命周期。
use_count()计数
expired()判断观测资源是否被释放！
int main() {
//初始化
shared_ptr<int> p(new int(1));
shared_ptr<int> p2 = p;
weak_ptr<int> wp(p);
if (wp.expired())
cout << "指针无效，已经被释放" << endl;
else
cout << "指针有效" << endl;
cout << wp.use_count() << endl;//2 打印引用计数
/////////////////////
auto sp = make_shared<int>(42);//另一种初始化方式
weak_ptr<int> gw = sp;
auto apt = gw.lock();
cout << *apt.get() << endl;//42
////////////////////
shared_ptr<int> p3;
p3.reset(new int(1));//未初始化的指针可以用reset初始化
//已经初始化的指针调用reset会使得引用计数减1
if (p3) {
cout << "p3 in not null" << endl;
}
//不能用原始指针来赋值智能指针
//shared_ptr<int> p4 = new int(1);
///////////////////////////
//获取原始指针
int *ip = p3.get();
//delete ip;//之后运行会出错！！
//指定释放空间的函数，可以是lambda
//shared_ptr<int> p5(new int(5), [](int *p) {delete p; });
//管理数组时要指定删除器，默认删除方式不支持数组
/////////////////////////////
//int *a1 = new int(10);
//shared_ptr<int> p6(a1);
//shared_ptr<int> p7(a1);//错误
return 0;
}
游戏
帧同步 状态同步
同步：多个客户端表现效果要相同！王者：英雄位置、技能释放时间、角度
帧同步：客户端和服务器同步方式，为了实现高实时性、高同步性而产生的
实时性：由于网络延迟，客户端发出指令到服务器需要时间，服务器发送指令到其他客户端也需要时间。为了感觉不到延迟，发送消息的周期一定要短。但是对服务器的成本更大。
为了减小服务器的压力，也为了能够更快地转发消息，游戏地逻辑一般都会放到客户端去执行。
同步性：客户端需要将指令同步后然后在固定地帧间隔内进行逻辑计算，而不是将逻辑计算好后再发送到其他客户端，防止不知道其他用户地操作而进行计算，会导致计算结果地不一致。
- 同步指令再计算：需要保证每个客户端收到相同指令都会运行出唯一的结果。若需要随机，则随机结果也应该相同
- 指令不能够丢失，采用tcp可靠传输。
- 为了应对玩家掉线，服务器应当保存一场游戏中的指令，在玩家断线之后重连发送给客户端。
战斗逻辑在客户端，服务器主要做转发。，回放、观战比较好做。
断线重连：断线重连之后，服务器会把短缺的消息都发给客户端，客户端加速运行，直到追到现有进度。
状态同步：同步的是游戏中的各种状态！！！
一般的流程是，客户端上传操作到服务器，服务器收到后计算游戏行为的结果。然后再以广播的方式 下发游戏中各种状态，客户端收到状态后再根据状态显示内容。
- 多应用于回合制游戏。
- 对网络延迟要求不高，
- 例如：一些回合制游戏，放大招，都有动画效果、前摇，然后将请求提交给服务器，服务器结果返回时，特效结束，然后统一伤害效果以及计算。
状态同步安全性比较高，逻辑和数值都在服务端，
断线重连：数值加到人物身上即可。
速度、加速度计算
三维立体空间计算
算法题
第一个题是求一个整数的平方根，要用搜索的方法，大概是二分查找
对于正整数来说：其开平方之后一定小于原来的数。
注意：正负5的平方都是25.
-
第一步，设置左端点为0，右端点为a。a开平方一定是小于a的。left = 0,right = a;
-
第二步，求初始值的中间值，mid = left + (right - left)/2;
-
第三步，求新的左端点以及右端点：
- if(mid * mid > a): 值有点大，right = mid
- else 值有点小，left = mid
- 继续循环 mid = left + (right - left)/2;
int main() {
//二分法：
int num;
cout << "请输入要开方的值：";
cin >> num;
if (num > 0) {
float left = 0;
float right = num;
float mid = left + (right - left) / 2;
while (abs(num-mid*mid) > 0.00001) {
if (mid * mid > num) {
right = mid;
}
else {
left = mid;
}
mid = left + (right - left) / 2;
}
cout << num << "开方之后得到 +/-" << mid<<endl;
}
else if (num = 0) {
cout << "0开方之后得0" << endl;
}
else {
cout << "负数不可能开平方" << endl;
}
}
这种做法只能处理正整数。
但是对于那种0.04这种就无法开放求解了。因为(<1小数部分)是越平方越小
int main()
{
float num;
float x; //x为所求结果
int i = 100; //控制循环的次数
cout<<"请输入要开方的数:";
cin >> num;
x = num / 2;
while (i--)
{
x = (x + num / x) / 2;//貌似是牛顿迭代法
}
printf("开方的结果为:%f
", x);
}
Linux
名词查询与概念理解
同步：发出一个功能调用，在没有得到结果之前，该调用就不返回或这继续执行后续才做，必须一件一件事情去做。调用者主动等待调用结果
异步：当一个异步过程调用发出以后，调用者在没有得到结果之前，就可以继续执行后续操作，且当调用完成以后，一般会通过状态、通知和回调来通知调用者，对于异步调用，调用的返回并不受调用者的控制。
同步/异步关心的时消息通知机制。
在同步的情况下，由调用者自己去处理去等待消息被触发
而异步情况下，则是由某些触发机制来通知处理消息者。
阻塞/非阻塞关心的是程序等待调用结果时的状态。
阻塞：是指调用结果返回之前，当前线程会被挂起，只有在得到结果之后才会返回。
非阻塞：是指不能立刻得到结果之前，该调用不会阻塞当前进程，通过轮询的凡是查询调用是否完成。
并行和并发表示CPU执行多个任务的方式。
并行：多个CPU时会出现并行，两个进程占用两个不同的CPU，可以同时进行，指多个任务同一时间点发生，不会相互抢占资源。
并发：在操作系统之中，某个时间段内多个进程都已经启动运行，它们共同占用一个处理机。指同一时间段内发生，多个任务之间会互相抢占资源。
消息队列
好比存放消息的容器。
消息队列是分布式系统中重要的组件，使用消息队列主要是为了通过异步处理提高系统性能、降低系统耦合。
常见的：RabbitMQ、Kafka。
在不使用消息队列服务器的时候，用户的请求数据直接写入数据库，在高并发的情况下数据库压力剧增，使得响应速度变慢。
但是在使用消息队列之后，用户的请求数据发送给消息队列之后立即返回，再由消息队列的消费者进程从消息队列中获取数据，异步写入数据库。由于消息队列服务器处理速度快于数据库（消息队列也比数据库有更好的伸缩性），因此响应速度得到大幅改善。
windows中系统为每个执行的程序维护一个消息队列。
数据库 Mysql
事务
特性：ACID
原子性
一致性
隔离性，防止一些错误
持久性：改变是持久的，通过日志等方式记录。
并发控制
锁：对数据库中的一条数据进行修改的时候，为了避免同时被其他人修改，最好的办法就是直接对数据加锁防止并发。
悲观锁：在修改数据之前先锁定，再修改的是方式称为悲观并发控制。因为我们认为数据会被并发修改的概率很大，需要在修改前加上锁。
修改前 先加排他锁。
效率方面：处理加锁机制会让数据库产生额外的开销，还有可能增加产生死锁的机会。还会降低并行性。
乐观锁：假设数据一般情况下不会造成冲突，所以在数据进行提交更新的时候，才会对数据的冲突与否进行检测，如果发生冲突，就返回用户错误信息，让用户决定如何去做。
一般乐观锁实现不采用锁，而是记录数据版本。直到提交的时候才去锁定，所以不会产生任何锁和死锁 ？？？
使用数据版本记录机制，当我们提交更新的时候，判断数据库表对应记录的当前版本信息与第一次取出来的version值进行比对，如果数据库表当前版本号与第一次取出来的version值相等，则予以更新，否则认为是过期数据。或者使用时间戳在更新提交的时候检查当前数据库中数据的时间戳和自己更新前取到的时间戳进行对比，如果一致则OK，否则就是版本冲突。
索引
索引是一个单独的、存储在磁盘上的数据库结构，它们包含着对数据表里所有记录的引用指针。
使用索引用于快速找出在某个或者多个列中有以特定值的行。
例如：查字典时候的拼音、笔画、部首等检索方式。
实际上，索引也是一张“表”，保存了主键和索引字段，并指向实体表的记录。
缺点：
- 索引会降低表的更新速度，更新表的同时，也会更新索引文件。
- 建立索引会占用磁盘空间的索引方式，维护索引会造成资源浪费！
InnoDB存储引擎
- 支持事务
- 灾难恢复性好，重启Mysql后都会将数据恢复到发生崩溃前的状态。
- 使用了行级锁，
- 提供了专门的缓冲池、实现了缓冲管理，可缓冲索引和数据，直接从内存中处理
InnoDB索引种类
- Primary Key（聚集索引）：InnoDB存储引擎的表会存在主键（唯一非null），如果建表的时候没有指定主键，则会使用第一非空的唯一索引作为聚集索引，否则InnoDB会自动帮你创建一个不可见的、长度为6字节的row_id用来作为聚集索引。
- 单列索引：单列索引即一个索引只包含单个列
- 组合索引：组合索引指在表的多个字段组合上创建的索引，只有在查询条件中使用了这些字段的左边字段时，索引才会被使用。使用组合索引时遵循最左前缀集合
- Unique（唯一索引）：索引列的值必须唯一，但允许有空值。若是组合索引，则列值的组合必须唯一。主键索引是一种特殊的唯一索引，不允许有空值
- Key（普通索引）：是MySQL中的基本索引类型，允许在定义索引的列中插入重复值和空值
- FULLTEXT（全文索引）：全文索引类型为FULLTEXT，在定义索引的列上支持值的全文查找，允许在这些索引列中插入重复值和空值。全文索引可以在CHAR、VARCHAR或者TEXT类型的列上创建
- SPATIAL（空间索引）：空间索引是对空间数据类型的字段建立的索引，MySQL中的空间数据类型有4种，分别是GEOMETRY、POINT、LINESTRING和POLYGON。MySQL使用SPATIAL关键字进行扩展，使得能够用于创建正规索引类似的语法创建空间索引。创建空间索引的列必须声明为NOT NULL
最左前缀原则：
索引创建原则
- 索引并非越多越好，一个表中如果有大量的索引，不仅占用磁盘空间，而且会影响INSERT、DELETE、UPDATE等语句的性能，因为在表中的数据更改的同时，索引也会进行调整和更新
- 避免对经常更新的表进行过多的索引，并且索引中的列尽可能少。而对经常用于查询的字段应该创建索引，但要避免添加不必要的字段。
- 数据量小的表最好不要使用索引，由于数据较少，查询花费的时间可能比遍历索引的时间还要短，索引可能不会产生优化效果。
- 在条件表达式中经常用到的不同值较多的列上建立索引，在不同值很少的列上不要建立索引。比如在学生表的“性别”字段上只有“男”与“女”两个不同值，因此就无须建立索引。如果建立索引，不但不会提高查询效率，反而会严重降低数据更新速度。
- 当唯一性是某种数据本身的特征时，指定唯一索引。使用唯一索引需能确保定义的列的数据完整性，以提高查询速度。
- 在频繁进行排序或分组（即进行group by或order by操作）的列上建立索引，如果待排序的列有多个，可以在这些列上建立组合索引。
- 搜索的索引列，不一定是所要选择的列。换句话说，最适合索引的列是出现在WHERE子句中的列，或连接子句中指定的列，而不是出现在SELECT关键字后的选择列表中的列。
- 使用短索引。如果对字符串列进行索引，应该指定一个前缀长度，只要有可能就应该这样做。例如，有一个CHAR(200)列，如果在前10个或20个字符内，多数值是唯一的，那么就不要对整个列进行索引。对前10个或20个字符进行索引能够节省大量索引空间，也可能会使查询更快。较小的索引涉及的磁盘 IO 较少，较短的值比较起来更快。更为重要的是，对于较短的键值，索引高速缓存中的块能容纳更多的键值，因此，MySQL 也可以在内存中容纳更多的值。这样就增加了找到行而不用读取索引中较多块的可能性。
- 利用最左前缀。在创建一个n列的索引时，实际是创建了MySQL可利用的n个索引。多列索引可起几个索引的作用，因为可利用索引中最左边的列集来匹配行。这样的列集称为最左前缀。
- 对于InnoDB存储引擎的表，记录默认会按照一定的顺序保存，如果有明确定义的主键，则按照主键顺序保存。如果没有主键，但是有唯一索引，那么就是按照唯一索引的顺序保存。如果既没有主键又没有唯一索引，那么表中会自动生成一个内部列，按照这个列的顺序保存。按照主键或者内部列进行的访问是最快的，所以InnoDB表尽量自己指定主键，当表中同时有几个列都是唯一的，都可以作为主键的时候，要选择最常作为访问条件的列作为主键，提高查询的效率。另外，还需要注意，InnoDB 表的普通索引都会保存主键的键值，所以主键要尽可能选择较短的数据类型，可以有效地减少索引的磁盘占用，提高索引的缓存效果
计算机网路
在浏览器输入url之后的流程
tcp基本概念
- 面向字节流
- 面向连接
- 可靠的：会送确认机制、超时重传机制
tcp中的计时器
tcp三次握手
tcp四次挥手
tcp拥塞控制
tcp粘包
在socket网络编程中，都是端到端通信，由客户端端口+服务端端口+客户端IP+服务端IP+传输协议组成的五元组可以明确的标识一条连接。在TCP的socket编程中，发送端和接收端都有成对的socket。发送端为了将多个发往接收端的包，更加高效的的发给接收端，于是采用了优化算法（Nagle算法），将多次间隔较小、数据量较小的数据，合并成一个数据量大的数据块，然后进行封包。那么这样一来，接收端就必须使用高效科学的拆包机制来分辨这些数据。
1.Q：什么是TCP粘包问题？
TCP粘包就是指发送方发送的若干包数据到达接收方时粘成了一包，从接收缓冲区来看，后一包数据的头紧接着前一包数据的尾，出现粘包的原因是多方面的，可能是来自发送方，也可能是来自接收方。
2.Q：造成TCP粘包的原因
（1）发送方原因
TCP默认使用Nagle算法（主要作用：减少网络中报文段的数量），而Nagle算法主要做两件事：
只有上一个分组得到确认，才会发送下一个分组
收集多个小分组，在一个确认到来时一起发送
Nagle算法造成了发送方可能会出现粘包问题
（2）接收方原因
TCP接收到数据包时，并不会马上交到应用层进行处理，或者说应用层并不会立即处理。实际上，TCP将接收到的数据包保存在接收缓存里，然后应用程序主动从缓存读取收到的分组。这样一来，如果TCP接收数据包到缓存的速度大于应用程序从缓存中读取数据包的速度，多个包就会被缓存，应用程序就有可能读取到多个首尾相接粘到一起的包。
3.Q：什么时候需要处理粘包现象？
如果发送方发送的多组数据本来就是同一块数据的不同部分，比如说一个文件被分成多个部分发送，这时当然不需要处理粘包现象
如果多个分组毫不相干，甚至是并列关系，那么这个时候就一定要处理粘包现象了
4.Q：如何处理粘包现象？
（1）发送方
对于发送方造成的粘包问题，可以通过关闭Nagle算法来解决，使用TCP_NODELAY选项来关闭算法。
（2）接收方
接收方没有办法来处理粘包现象，只能将问题交给应用层来处理。
（2）应用层
应用层的解决办法简单可行，不仅能解决接收方的粘包问题，还可以解决发送方的粘包问题。
解决办法：循环处理，应用程序从接收缓存中读取分组时，读完一条数据，就应该循环读取下一条数据，直到所有数据都被处理完成，但是如何判断每条数据的长度呢？
格式化数据：每条数据有固定的格式（开始符，结束符），这种方法简单易行，但是选择开始符和结束符时一定要确保每条数据的内部不包含开始符和结束符。
发送长度：发送每条数据时，将数据的长度一并发送，例如规定数据的前4位是数据的长度，应用层在处理时可以根据长度来判断每个分组的开始和结束位置。
5.Q：UDP会不会产生粘包问题呢？
TCP为了保证可靠传输并减少额外的开销（每次发包都要验证），采用了基于流的传输，基于流的传输不认为消息是一条一条的，是无保护消息边界的（保护消息边界：指传输协议把数据当做一条独立的消息在网上传输，接收端一次只能接受一条独立的消息）。
UDP则是面向消息传输的，是有保护消息边界的，接收方一次只接受一条独立的信息，所以不存在粘包问题。
举个例子：有三个数据包，大小分别为2k、4k、6k，如果采用UDP发送的话，不管接受方的接收缓存有多大，我们必须要进行至少三次以上的发送才能把数据包发送完，但是使用TCP协议发送的话，我们只需要接受方的接收缓存有12k的大小，就可以一次把这3个数据包全部发送完毕。
————————————————
原文链接：https://blog.csdn.net/weixin_41047704/article/details/85340311
tcp心跳包
http
https
长连接 短连接
- 长连接意味着进行一次数据传输之后，不关闭连接，长期保持联通状态，如果双方之间有了新的数据需要传送，就复用这个连接，无需再建立一个新的连接。
- 优点：再多次通信中可以省去连接建立和关闭连接的开销，并且总体上看，进行多次数据传输的总耗时更少。
- 缺点：需要花费额外的经历来保持这个连接一直可用，需要使用保活机制，方式一：定期发送探测报文，方式二：上层应用主动的定时发送一个“心跳包”，探测能否成功。保活：一般常用于服务器端探测客户端，一旦识别成功，则断开连接，缓解服务器压力。
- 场景：频次高的，实时刷新的，两个进程之间需要高频通信并且具备服务端主动推送或者有状态（需串行）两者之一的场景，否则并不是必选项。
- 短连接：意味着每次数据传输都需要建立一个新的连接，用完马上关闭，下次用的时候重新建立连接。
- 优点：每次使用的连接都是新建立的，本次传输异常都不影响下次新的数据传输
- 缺点：建立连接与释放连接，耗时增加。同时能够使用的端口是不够用。
- 场景：低频、阅读类，两个进程之间通信频率较低，或者属于无状态（可并行）的场景，否则并不是必选项。
数据结构
排序
各大排序算法、思想
二分查找
- 一定要会！！！
链表
二叉树的多种基本操作
红黑树
dfs bfs
astar
海量数据处理
操作系统
一面
1. tcp客户端断开和服务端断开有啥区别
2. http请求头部都有哪些 ： GET POST HEAD
3. malloc有几种实现方法 |
4. 长连接短连接怎么解析的
5. 项目中主线程怎么向从线程发送数据
6. 函数实例和函数有什么区别
7. string 变化的空间是怎么实现的
8. 四次挥手的标志
9. 四次挥手的过程
10. 读写锁之间的关系
11. select底层使用什么存储的，poll是用什么存储的，epoll是用什么存储的？
12. 继承后的虚函数表示在一块的吗？
二面
1. 大端小端如何识别
2. 字符串大端小端以及为什么
3. 如果有一个连接请求处理时间特别长怎么办，有了解过其他的模型吗？
4. 1G数据如何取出中位数（自己实现一下）
5. stl库 map拷贝过程中如果插入数据 怎么构造map
6. map底层实现，如果超过一定数量怎么办？
7. map和unordered_map区别
8. TCP三次握手的标志，以及为什么，TCP头部都有哪些变化
9. 网络层总共有几层，每层协议是什么（数据链路层没答上来）
10. int型1G数据有多少个？
11. 空的类有多大（说到内存对齐）
12. 虚函数表里有啥（提到了虚继承的offset）
13. 服务器连接失败了如何定位
14. ping命令如何执行
15. select poll epoll底层实现
16. 实现智能指针
17. 网络序是什么，本地序
18. 自己写一个htonl
数据库acid mysql的引擎 索引
tcp连接的过程 服务器如何处理多个连接 select和epoll
进程间通信的几种方式 进程和线程的差别 线程间的同步 linux进程调度算法
如何查看一个程序的内存 知道什么linux命令 在linux环境下的调试
还想问C++ 完全不会 问了C的堆栈的区别
数组和链表的区别/适用场景
作者：奕心
链接：https://www.nowcoder.com/discuss/629212?source_id=discuss_experience_nctrack&channel=-1
来源：牛客网
主学什么语言（c，深度学习用python）
c的malloc的内存池是怎么管理的（没怎么了解，大概说了链表结构啥的）
二叉树找第k大怎么做，空间复杂度多少
用快排做topk怎么做，时间复杂度怎么算
二叉搜索树找第k大怎么做，空间复杂度多少
打算考研吗（打算）
多线程编程有了解过吗
路由器和交换机有什么区别，分别工作在哪一层
流量控制用的协议，拥塞控制用的协议（不知道啥协议，讲了下原理）
mysql的幻读，怎么解决幻读
mysql怎么提高效率（索引是有效的）（大概想问分库分表、读写分离这样的高并发处理操作，一时没想起来）
线程的上下文是什么、进程的上下文是什么
编程：k个一组反转链表