CPP八股总结

备份一下遇到的CPP知识

CPP

（1）数据结构

data structure引入：在电脑中，变量存储在RAM（Random Access Memory，随机存取存储器）中。（随机存储，容易丢失，高速访问）

插入、删除、遍历、查找、排序、访问是对各种数据结构的操作。

1、数组

lookup：O(1) ; push：O(1) ; insert：O(n) ; delete：O(n)

定义数组元素初始值时，数组可以不指定初始数组长度。

int arr3[] = { 100,90,80,70,60,50,40,30,20,10 };

数组长度：sizeof（arr）

二维数组的长度：行数：sizeof（arr） ；列数：sizeof（arr[0]）

、

、unordered_set

🐦特点

无序性：元素不按照特定顺序存储。与 set 不同，unordered_set 不保证元素的排列顺序，元素的顺序与插入顺序无关。

唯一性：unordered_set 中的每个元素都是唯一的，即不能有重复元素。如果尝试插入重复元素，插入操作会被忽略。

底层实现：unordered_set 使用哈希表（hash table）作为底层数据结构，因此它在插入、查找和删除元素时平均时间复杂度为 O(1)，但在最坏情况下可能降到 O(N)。

需要哈希函数：unordered_set 需要一个哈希函数来计算元素的哈希值。对于内置类型（如整数、字符串等），STL 提供了默认的哈希函数。

🐦操作

插入：insert（value）

查找：find（value）

删除：erase（value）

清空：clear（）

返回元素数量：size（）

、哈希表

• 声明：unordered_map<int,int> hashtable;
• 查找：auto it=hashtable.find(target-nums[i]);

it->second：值 ；it->first：键

、大根堆

特点：父节点比任意子节点都大。

构建过程：

• 将无序数组依次插入完全二叉树中。
• 从最后一个非叶子的子节点开始，找到它子节点的最大值，如果大于它就和它交换，就这样一直交换到根节点。
• 再从根节点下的节点开始这样交换。

、双向队列

、map

（2）算法

1、Dijkstra（迪杰斯特拉）算法

用于求解带权有向图的最短路径问题

🎃在构造算法的时候需要两个辅助数组：

• dist[]：记录从源点V0到其他各顶点的当前最短路径长度。初始值：若V0到Vi有直接路径，则dist[i]为这两个顶点边上的权值，否则置为∞。
• path[]：记录从原点到各顶点之间最短路径的前驱节点。（在算法结束时，可以根据其值追溯V0到Vi的最短路径）。初始值：-1。

在计算的时候维护一个集合S，初始值为V0。

每一次从V-S的顶点中选出最小的dist[i]，并把相应Vi放入S中。根据Vi可以直达的顶点j（也需在V-S中），计算相应路径长度，如果小于当前的dist[j]，就更新其值，并设其前驱节点为i。

当V中的顶点已全部在S中，就结束算法。

2、散列表的平均查找成功/失败长度

解决哈希冲突的常见方法：链地址法；开放地址法。

🐦链地址法

查找成功平均长度：

• 设查找到每个位置的概率为p0。
• 查找到第n层就成功的概率为p0*第n层元素个数（Pn）。
• 平均长度=P1*1+P2*2+P3*3...+Pn*n

查找失败平均长度：

• 不知道零层到底算不算……存疑

🐦开放地址法

装填/负载因子：散列表中已经装填的元素数/散列表总长度

（对于函数为H(Key)=(Key*3)%7，哈希地址只能是0-6）

查找成功平均长度：

• 对于每个数，从开始的地址一直查到它的距离相加。最后除以7。

查找失败平均长度：

• 从0-6的地址开始依次向后，直到找到空位置的距离相加。最后除以7。

3、排序

＜蓝桥杯软件赛＞零基础备赛20周–第8周第1讲–十大排序-CSDN博客

4、二分

＜蓝桥杯软件赛＞零基础备赛20周–第10周–二分_蓝桥杯20周csdn-CSDN博客

（3）其他知识点

1、i++和++i的区别

i++先赋值再自增，++i先自增再赋值。

int i = 1;
i = i++;
int j = i++;
int k = i + ++i * i++;
System.out.println("i = " + i);    //4
System.out.println("j = " + j);    //1
System.out.println("k = " + k);    //11(2+3*3)

2、std::vector<int>()

ans=cnt==numCourses?ans:std::vector<int>();

如果要返回空数组，不能直接写[]或者{}，而是要按照上面的语法写

3、设计模式

23 种设计模式详解（全23种）_23种设计模式-CSDN博客

4、stoi

用于将字符串转化为数字

stoi（str，pos，base）

• pos可以定义从某个位置开始转化
• base可以指定转化为多少进制，直接写数字就可以了

与此相对的是to_string，它用于把各种数值类型转化为字符串

5、replace

用于在指定范围内替换指定的元素，通常与vector，string配合使用。