博客主页:@披星戴月的贾维斯
欢迎关注:点赞收藏留言
系列专栏: C/C++专栏
请不要相信胜利就像山坡上的蒲公英一样唾手可得,但是请相信,世界上总有一些美好值得我们全力以赴,哪怕粉身碎骨!
一起加油,去追寻、去成为更好的自己!
文章目录
- 前言
- 1、为什么C++没有实现垃圾回收?
- 2、浅析STL源码中hash表
- 解决哈希冲突的方式(常考常问)
- 拓展:STL vector迭代器失效的问题(常考常问)
- 3、网络:TCP/IP五层(或四层)模型
- 4、三次握手的过程
- 5、四次挥手的过程
- 6、 TCP和UDP的区别(常问常考)
- 7、洛谷P2390地标访问(二分算法)
- 总结
提示:以下是本篇文章正文内容,下面案例可供参考
前言
这次我们将把之前没有聊到C++面经的几个点继续和朋友们分享,以及我最近在写一些题目,对于二分算法的理解更深刻了,和大家一起分享一下!希望要参加面试和参加蓝桥杯的同学都有所收获!
1、为什么C++没有实现垃圾回收?
实现垃圾回收器会带来额外的时间和空间开销,因为需要一定的空间用来保存指针的引用计数和对他们进行标记,并且要单独开一个线程在空闲的时候进行free操作。不符合C++高效的特性,不适合做底层的工作。
C++是要兼容C语言的,这使得可以将一个类型转化为另一个类型,因此对于一个指针无法知道它真正指向的类型。这也就导致所有的指针没有共同的基类,并不知道要如何释放指针所指向的对象。
C++有析构、智能指针等方式来进行内存管理,对垃圾回收的需求不是很着急。
2、浅析STL源码中hash表
STL中的hash就是unordered_map,使用哈希桶进行实现,其对传入的key值进行hash操作得到哈希值,从而得到存储的位置,实现O(1)的插入和访问操作。由于使用哈希桶来进行实现,当一个桶对应的拉链超过8个时,则会将链表转化为红黑树,从而提高查找的效率。
map则是使用红黑树来实现,红黑树相比于哈希表的一个优势在于红黑树能够实现自动排序,但其插入和查找的效率则取决于树的高度也就是log(n)。
解决哈希冲突的方式(常考常问)
线性探测:当要插入的数据的哈希值对应的桶不能存放元素时,就继续往后面查找,直到找到了空桶。
二次探测:与线性探测类似,但每次并不是线性查找,而按照1,4,9的顺序进行探测。
双散列函数法:当第一个哈希函数得到的哈希值发生冲突时,就换另一个哈希函数。
拉链法:每一个哈希桶维护一个链表,哈希值找到对应的桶,并将元素头插到对应的链表中。如果链表过长,就将链表转化成红黑树。
建立公共溢出区:当发生冲突时,就将所有冲突的元素放到公共溢出区。
拓展:STL vector迭代器失效的问题(常考常问)
vector插入时,空间不够,重新申请空间并将原来的元素都移动到新的空间,此时指向原来内存的迭代器就都失效了。
插入时,end迭代器肯定失效。
vector删除时,被删除的元素以及后面元素的迭代器都会失效。
3、网络:TCP/IP五层(或四层)模型
TCP/IP是一组协议的代名词,它还包括许多协议,组成了TCP/IP协议簇.
TCP/IP通讯协议采用了5层的层级结构,每一层都呼叫它的下一层所提供的网络来完成自己的需求。
- 物理层: 负责光/电信号的传递方式. 比如现在以太网通用的网线(双绞 线)、早期以太网采用的的同轴电缆(现在主要用于有线电视)、光纤, 现在的wifi无线网使用电磁波等都属于物理层的概念。物理层的能力决定了最大传输速率、传输距离、抗干扰性等. 集线器(Hub)工作在物理层
- 数据链路层: 负责设备之间的数据帧的传送和识别. 例如网卡设备的驱动、帧同步(就是说从网线上检测到什么信号算作新帧的开始)、冲突检测(如果检测到冲突就自动重发)、数据差错校验等工作. 有以太网、令牌环网, 无线LAN等标准. 交换机(Switch)工作在数据链路层。
- 网络层: 负责地址管理和路由选择. 例如在IP协议中, 通过IP地址来标识一台主机, 并通过路由表的方式规划出两台主机之间的数据传输的线路(路由). 路由器(Router)工作在网路层.
- 传输层: 负责两台主机之间的数据传输. 如传输控制协议 (TCP), 能够确保数据可靠的从源主机发送到目标主机.
- 应用层: 负责应用程序间沟通,如简单电子邮件传输(SMTP)、文件传输协议(FTP)、网络远程访问协议(Telnet)等. 我们的网络编程主要就是针对应用层。
4、三次握手的过程
服务端调用socket(指定协议、套接字类型)创建套接字、分配文件描述符,bind(绑定套接字也就是文件信息和网络信息)绑定服务器的端口和ip地址,listen监听文件描述符,进入LISTEN状态,等待客户端的连接。
客户端调用connect(填写套接字、服务器的ip和端口号)向服务器发送连接请求(这个请求是一个带有SYN标志的报文),并且阻塞等待服务器的响应,客户端此时的状态为SYN_SENT。
服务器通过listen收到客户端发来的SYN报文并确认Seq字段,由LISTEN状态转变为SYN_RECVD状态,并向客户端发送SYN+ACK的报文,并且将连接放到半连接队列里。
客户端收到ACK+SYN报文后,发送ACK报文,并且变成ESTABLISHED状态,服务器收到客户端发送的ACK报文,进入ESTABLISHED状态,并且把连接从半连接队列取出放到全连接队列,等待accept取出。
后续客户端和服务器分别调用send和recv两个函数,进行通讯。
在三次握手的过程中,客户端和服务器还会将自己的序列号seq和窗口大小wind一起放到报文中进行沟通。
5、四次挥手的过程
客户端调用close函数后,向服务器发送FIN数据包,此时客户端进入FIN_WAIT_1状态。
服务器收到FIN数据包,向客户端发送ACK报文,进入CLOSE_WAIT状态。
客户端收到ACK报文,进入FIN_WAIT_2状态,等待接收服务器的FIN报文。
服务器处理完数据以后,调用close函数,向客户端发送FIN报文,并进入LAST_ACK状态。
客户端收到FIN报文,最后向服务器发送ACK报文,并进入TIME_WAIT状态,2MSL后,进入CLOSED状态。
服务器收到ACK,断开连接关闭套接字,进入CLOSED状态。
6、 TCP和UDP的区别(常问常考)
- TCP是面向连接的协议,从而提供可靠的传输,在收发数据之前需要先通过三次握手建立连接,期间沟通seq序列号和窗口大小。而UDP是无连接的,不管对方有没有收到或者收到的数据是否正确。
- TCP提供流量控制、拥塞控制和超时重传等一系列方式来保证可靠性。
- TCP对系统资源的要求高于UDP,速度比UDP慢。
- TCP是面向字节流,而UDP是数据报。TCP的数据包没有边界,会出现粘包问题,UDP的包是独立的,不会出现粘包问题,但UDP的包要么不读要么就要一次性全读完。通常要解决TCP粘包问题,可以采用包和包之间增加分隔符、指定包的长度、每次发送定长的包来解决。
- 在应用方面,如果强调数据的完整性和正确性,可以采用TCP,如果对性能要求比较高比如直播等允许一定丢包的情况,可以采用UDP。
7、洛谷P2390地标访问(二分算法)
题目链接 :地标访问
题目背景
改编自 USACO2007Nov 铜组 Exploration
题目描述
贝西在一条道路上旅行,道路上有许多地标,贝西想要在日落之前访问尽可能多的路标。将道路视为一条数轴,贝西从原点出发,道路上有n(1≤n≤5×10)个地标,每个地标有一个坐标xi(|xi| <= 10^5), 且地标的坐标各不相同,(1≤T≤10^9) 分钟之后将会日落。
输入格式
第一行:两个整数 t,n
第二行至第 n+1 行:地标的坐标
输出格式
一个整数,贝西能访问的最多的地标数.
输入输出样例
输入 #1
25 14168-7310-15-176-1214-1329-5
输出 #1
8
对样例分析
我们要在日落之前访问尽量多的坐标,样例给的T是25,就是我们要在25分钟内,总共有14块路标,每一个路标都有对应的位置,我们比如说是有3块路标,分别在1,2,3这些位置,那我们在访问 1 – 3时可以顺便把 2这块路标访问到,这样的时间也算3,对负数的处理在时间上也是要转为正数来算的,我们先sort每块路标的位置,得到
-17 -15 -13 -12 -7 -5 2 3 6 8 9 10 14 16
答案8 就是左端点是-7开始到右端点是10,加起来8个数,而且贝西是先去最短的地方-7再去最远的10,这样子加起来的时间就是7 + 7 + 10 = 24 < 25成立。
二分的再次理解:二分算法使用于具有二段性的题目,比如求最大值,最小值,最大值中的最小值等等,二分中的L 和 R的取值一定要在合理的区间内,R的值也最好是区间右端点,如果是求最小值,mid = (l + r) / 2, 不用 + 1.
while(l > 1;if(check(mid)) r = mid;else l = mid;}
求最大值(枚举区间右端点)
while(l < r){int mid = l + r + 1;if(check(mid)) l = mid;else r = mid - 1;}
本题题解
#includeusing namespace std;const int N = 5e4 + 10;int a[N];int n, t;bool cheak(int x)//能访问到x个坐标{ for(int r=x;r<=n;r++){//枚举右端点int l=r-x+1;if(a[r]<=0)//如果右端点在原点左边,就要一直向左走 if(-a[l]=0)//如果左端点在原点右边,就要一直向右走 if(a[r]<=t)return true;//同上if(a[l]=0)//如果这段区间横跨了原点 if(min(a[r],-a[l])+a[r]-a[l]> t >> n; for(int i = 1; i > a[i]; sort(a + 1, a + n + 1); int l = -1, r = n + 1;//因为可能一个点也访问不了 //我们想找尽量大一点的值 while(l + 1 > 1; if(cheak(mid)) l = mid; else r = mid; } cout << l << endl; return 0;}
总结
本文向大家介绍了几个C/C++面试中可能会被问到的问题,还和大家一起继续深入理解二分算法,解决了地标访问这一题,希望对读者能有所帮助!