购物平台大全,宁波做网站seo,wordpress 文章采集插件,浙江政务服务网文章目录 #x1f37a; 非技术问题#x1f37b; 基本问题#x1f942; 请自我介绍#xff1f;#x1f942; 你有什么问题需要问我的#xff1f; #x1f37b; 加班薪资#x1f942; 你对加班有什么看法#xff1f;#x1f942; 你的薪资期望是多少#xff1f;【待回… 文章目录 非技术问题 基本问题 请自我介绍 你有什么问题需要问我的 加班薪资 你对加班有什么看法 你的薪资期望是多少【待回答】 规划前景 你对自己的职业有什么规划吗 你有对象没在哪个城市 项目经历 极简抖音服务器 用户密码是用明文存储的吗 C基础 新特性 C11 的新特性有哪些 你对 lambda 了解多少 move 的作用是什么 智能指针的原理是什么如何实现智能指针 实现智能指针需要哪些函数【待回答】 智能指针出现循环引用如何解决【待回答】 关键字 / 函数 volatile 关键字是干什么的 sort 函数是基于快速排序还是插入排序的 strcpy 和 strncpy 的区别 static 的作用【待回答】 继承 / 封装 / 多态 多态是如何实现的 析构函数为什么一般为虚函数 内存管理 程序的内存分区是怎么样的 堆和栈的区别 为什么要内存对齐对齐原则是什么 内存泄漏是什么如何避免 程序从开始编译到生成可执行文件的过程【待回答】 语言对比 C 和 Python 的区别【待回答】 STL unordered_set、set、unordered_map、map 的区别应用场景 设计模式 常见的设计模式有哪些【待回答】 单例模式是什么请实现一下单例模式 哲学家进餐问题【待回答】 计算机网络 HTTP / HTTPS 在浏览器地址栏输入 URL 会涉及的技术步骤 HTTP 和 HTTPS 的区别 HTTP 1.0 / 1.1 / 2 / 3 的区别 HTTP 的状态码有哪些 HTTP 的请求和响应报文有哪些字段 HTTP 长连接如何维持 TCP / UDP TCP 是如何保证可靠传输的 TCP 和 UDP 的区别 三次握手的过程是怎样的 四次挥手的过程是怎样的 四次挥手中 ACK 报文和 FIN 报文可以合并发送吗 封包、拆包是什么是基于 TCP 还是 UDP 的概念 DNS DNS 负载均衡是什么【待回答】 操作系统 进程 / 进程 进程与线程的区别 进程间通信方法有哪些 线程间通信方法有哪些 回收线程有哪些方法【待回答】 线程切换状态有哪些【待回答】 锁 在并发任务中不加锁可能会出现哪些问题 死锁是什么产生原因是什么如何避免 介绍下几种典型的锁 多路复用 IO 多路复用是什么 IO 模型有哪些 select、poll、epoll 的区别 Linux Linux 中异常和中断的区别 Linux 中常用的命令有哪些 Linux 如何查看用到的端口【待回答】 其他 内核态和用户态的区别【待回答】 MySQL 引擎 InnoDB、MylSAM 的区别 锁 MySQL 的行级锁有哪些 慢查询 如何排查一条慢 SQL如何优化 事务 事务的四大特性是什么 事务的隔离级别有哪些 脏读、幻读、丢弃更改、不可重复读是什么 索引 为什么 MySQL 索引使用 B 树为什么不用 B 树红黑树hash 表 MySQL 中有哪些索引 使用索引的好处有哪些【待回答】 使用索引的注意事项有哪些【待回答】 备份数据库的备份和灾备你有了解吗 Redis 概念 Redis 是什么 数据结构 Redis 的底层数据结构有哪些 锁 Redis 如何实现分布式锁 缓存 如何保证缓存与数据库的数据一致性 Redis 的数据优化方案有哪些【待回答】 热点数据和冷数据是什么【待回答】 持久化 Redis 有哪些持久化机制 面试算法 双指针 11. 盛最多水的容器 [数组] [面积] (双指针) 31. 下一个排列 [数组] [排列] (双指针) (推导) 42. 接雨水 [数组] [面积] (双指针) 160. 相交链表 [链表] [相交] (双指针) LCR 139. 训练计划 I [数组] [元素交换] (双指针) 三指针 215. 数组中的第K个最大元素 [数组] [第K大元素] (三指针) (快速排序) 滑动窗口 3. 无重复字符的最长子串 [字符串] [子串] (滑动窗口) 二分法 153. 寻找旋转排序数组中的最小值 [旋转数组] [最小值] (二分法) 162. 寻找峰值 [数组] [峰值] (二分法) DFS 200. 岛屿数量 [矩阵] [岛屿] (DFS) 贪心 452. 用最少数量的箭引爆气球 [数组] [区域重合] (贪心) (排序) 其他 8. 字符串转换整数 [字符串] [转换] (遍历) 【待做】【199】 非技术问题 基本问题 请自我介绍 面试官您好我是深圳大学信息与通信工程的研三在校生我叫XXX。下面我将从求职动机和过往经历介绍下我自己。 对于求职动机虽然我本科和研究生阶段都是通信类专业但是我在校期间接触的项目大多都是和软件相关的比如本科接触过智能车的赛道识别硕士期间接触的深度学习图像压缩还有自己参与过的小组项目也都是软件相关的自己对编程类的工作也更感兴趣。 对于过往经历我在研三期间有一段实习经历在深圳的中科鼎创公司作为一个后端实习生实习了四个月主要工作是基于 C 实现对VMWare 虚拟机的灾备工作后期对相关功能进行 go 的实现。我的在校项目有两个第一个是参加的字节青训营的活动官方会提供一个编写好的抖音前端界面我们的任务就是对软件的后端功能进行实现比如像用户登录注册发布视频点赞搜藏等。第二个项目是一个webserver 服务器当用户在浏览器上输入对应网址时可以获取远程数据库中的文字图片视频等信息。我们科研工作的化主要集中于深度学习图像压缩科研中使用语言大多是 python目前已经发表了专利和小论文。我的性格的话比较外向在工作和生活中也可以和别人很好的沟通交流希望自己能够胜任这份工作。 以上是我的介绍谢谢。 你有什么问题需要问我的 请问你们在部门的主要业是什么如果自己进入贵部门会负责什么 请问面试官觉得我还存在着哪些不足的地方 我如果能够应聘上这个岗位还需要具备哪些知识或能力呢 请问面试官对我的职业规划有什么建议 加班薪资 你对加班有什么看法 我觉得加班来赶工期或者赶进度是很正常的特别是在互联网这个行业。业务肯定有比较忙比较紧急的时候对于加班我觉得是挺必要的。而且多把自己的精力放在工作中自己能力提升的也更快些。 你的薪资期望是多少【待回答】 规划前景 你对自己的职业有什么规划吗 首先希望进到公司后能够对新人有一定的培养自己尽快的适应当前的工作。 在最初的两年脚踏实地的干好自己的本职工作熟练掌握开发中需要用到的技术为公司带来更多的价值。平时的工作生活中多向前辈请教学习新的知识提高自己的水平。 在自己成为具备一定能力的工程师后希望能熟悉部分项目的框架原理碰到问题可以快速定位解决。以后向着架构师或者别的方向发展更多的提供自己的价值。 你有对象没在哪个城市 有的我女朋友找到也是深圳的工作所以我首要考虑的也是在深圳发展。 项目经历 极简抖音服务器 用户密码是用明文存储的吗 不是存储的是加密后的数据比如我在项目中就用的是 md5 加密存储的是 128 位的哈希值。 如果直接明文存储密码就十分的不安全登录或者其他操作时验证密码也是验证的加密值。 C基础 新特性 C11 的新特性有哪些 在关键字上用 nullptr 代替了 NULL引入了 auto 和 decltype 实现类型推导引入了 final 和 override 继承关键字引入了基于范围的 for 循环等。 引入了匿名函数 lambda 表达式用来替代独立的函数或函数对象。 支持自定义类型的列表初始化初始化代码更加简洁。 引入了智能指针自动释放动态内存避免忘记释放内存导致的内存泄漏。 引入了右值引用和 move 语义减少了不必要的资源拷贝。 你对 lambda 了解多少 lambda 表达式可以编写内嵌的匿名函数用来替换独立的函数、匿名对象增加代码的可读性。 每当定义一个 lambda 表达式编辑器会自动生成一个匿名类也成为闭包。在运行时lambda 表达式会创建一个闭包实例它可以通过传值或引用的方式获取作用域内的变量也就是前面的 []也可以通过参数列表获取参数也就是后面的 ()。 lambda 表达式的语法定义为: [捕捉列表] (参数列表) mutable 是否可修改捕捉列表 - 返回类型 {函数体}。其中捕获列表和函数体是必须有的其他的可以省略。 move 的作用是什么 move 是一种高效的资源转移机制相当于转移了资源的所有权这样可以让待销毁对象的资源原地转移到其他变量避免不必要的内存拷贝操作提高程序的性能。 move 本身不能移动任何东西它的唯一作用是将一个左值引用强制转化为右值引用编辑器只能对右值引用的对象调用移动构造 / 拷贝函数实现移动语义。 智能指针的原理是什么如何实现智能指针 智能指针本质上是一个类它用来存储指向动态分配对象的指针并负责该动态分配对象的释放避免内存泄漏。当智能指针对象的生命周期结束后会自动调用析构函数来释放动态分配的资源。 shared_ptr多个该智能指针可以指向同一个对象。每当增加一个智能指针指向该对象时所有的智能指针内部的计数器都会加一每当减少一个智能指针指向该对象时所有的智能指针内部计数器都会减一。因此当智能指针内部的引用计数器为零时则会自动释放动态分配的内存资源。 unique_ptr该智能指针独享所指向对象的所有资源。当资源进行转移时原来的智能指针将被置空因此 unique_ptr 不支持普通的拷贝和赋值操作因为此时有两个智能智能指向同一个资源导致同一内存多次释放。 weak_ptr该智能指针主要是为了解决循环引用的问题此时两个指针指向的内存都无法释放。weak_ptr 是一个弱引用它指向 shared_ptr 管理的对象而不影响对象的计数。当访问对象时可以使用 lock 函数来获取指向该对象的 shared_ptr。 智能指针的实现
templatetypename T
class Shared_Ptr {
private:T* _ptr; // 指向资源的指针int* _pcount; // 指向引用计数的指针
public:// 构造函数初始化智能指针Shared_Ptr(T* ptr nullptr): _ptr(ptr), _pcount(new int(1)) {}// 拷贝构造函数共享同一块内存引用计数 1Shared_Ptr(const SharedPtr s): _ptr(s._ptr), _pcount(s._pcount) {(*_pcount);}// 赋值运算符重载SharedPtrT operator(const SharedPtr s) {if (this ! s) {// 复制前检查自己是否是最后一个指向先前某区域的指针是的话释放之前指向的资源if (--(*(this-_pcount)) 0) {delete this-_ptr;delete this-_pcount;}// 复制其他的智能指针现在指向一个新的对象_ptr s._ptr;_pcount s._count;(*_pcount);}return *this;}// 解引用操作符重载T operator*() {return *(this-_ptr);}// 成员访问操作符重载T* operator-() {return this-_ptr;}// 析构函数处理引用计数当为 0 时释放资源。~ SharedPtr() {--(*(this-_pcount));if (*(this-_pcount) 0) {delete _ptr;_ptr nullptr;delete _pcount;_pcount nullptr;}}
};实现智能指针需要哪些函数【待回答】 智能指针出现循环引用如何解决【待回答】 关键字 / 函数 volatile 关键字是干什么的 内存可见性CPU 内核有自己的缓存彼此之间不可见使用 volatile 会强制将缓存写入主内存中从主内存中加载数据。 禁止指令重排指令重排是编译器为了优化程序的执行性能而对指令重新排序的一种手段在多线程环境下可能会出现问题。当一个变量被 volatile 修饰时编译器会禁止对齐进行指令重排从而确保程序的正确性。 sort 函数是基于快速排序还是插入排序的 sort 中采用的是一种 IntroSort 内省式排序的混合排序算法。 首先判断排序的元素个数是否大于阈值通常这个阈值为 16如果元素个数小于阈值则直接使用插入排序。因为当序列中大多元素有序时采用插入排序会更快。 如果元素个数大于阈值时判断序列递归的深度会不会超过 2*log(n)如果递归深度没有超过阈值时就使用快速排序。 如果递归深度超过阈值时那么快排的复杂度就退化了这时候就采用堆排序因为堆排序的复杂度是 nlog(n)比较稳定。 strcpy 和 strncpy 的区别 这两个都是复制字符串的函数不过 strncpy 可以指定复制的长度。 如果指定长大于目标长则报错无法复制。 如果指定长大于源长那么可以正常拷贝自动加上结束符。 如果指定长小于源长那么只能拷贝部分字符串并且不会加上结束符。 static 的作用【待回答】 继承 / 封装 / 多态 多态是如何实现的 多态是指让不同的对象在使用相同的方法时可以表现出不同的响应。 编辑器在发现基类中有 virtual 修饰的虚函数时会为每个含有虚函数的类生成一份虚表其中存放着一系列的虚函数地址。 编辑器会在对象中保存一个虚表指针指向这个虚表从而在实际调用中找到对应的函数。 当派生类创建对象时会自动调用构造函数在构造函数中创建虚表初始化虚表指针。 当派生类的虚函数没有重写时派生类的虚表指针指向的是基类的虚表当派生类对基类的虚函数进行重写时派生类的虚表指针将指向自身重写的虚表。因此可以根据当前对象的虚表指针进行相应函数的调用实现多态。 析构函数为什么一般为虚函数 如果析构函数为虚函数当基类指针可以指向派生类的对象如果删除基类的指针就会调用所指派生类对象的析构函数而派生类的析构函数又会调用基类的析构函数整个派生类的对象被完全释放。 如果析构函数不为虚函数则编辑器实施静态绑定当删除基类指针时只会调用基类的析构函数而不会调用派生类的析构函数造成派生类析构不完全导致内存泄漏。 内存管理 程序的内存分区是怎么样的 程序的内存分区主要分为 5 个部分从高到低分别是栈区堆区全局数据区常量区和代码区。 栈区程序运行时函数中局部变量的存储空间在栈上创建函数执行结束时这些变量的存储空间会被自动释放。栈的内存分配由操作系统负责效率高但是分配的内存空间有限。 堆区由 new 操作符所分配的动态内存都存放于堆中但是这些内存的释放需要手动控制一个 new 对应一个 delete 释放。堆的内存分配效率低但是可分配的内存空间大。 全局数据区里面存放着全局变量和静态变量如果有些变量没有初始化那么在这里会进行自动的初始化。 常量区里面存放着常量不允许修改。 代码区里面存放的是二进制的代码。 堆和栈的区别 申请方式不同栈是由系统自动分配的堆是程序员手动分配的。 申请大小不同栈是一片连续的内存区域大小是操作系统预定义好的。堆是一片不连续的内存区域大小可以灵活调整。 申请效率不同栈由系统分配速度快且不会有碎片堆由程序员分配速度慢而且会产生内存碎片。 生长方向不同栈的内存分配是由高到低的堆的内存分配是由低到高的。 为什么要内存对齐对齐原则是什么 CPU 访问数据时并不是逐字节的访问而是以字长为单位进行访问比如在 32 位系统中字长为 4 字节。这样设计可以提高 CPU 访问内存的效率比如同样是访问 8 字节的数据以字长为单位读取仅需要两次即可而逐字节访问需要 8 次。 结构体中的成员会按照声明的顺序进行存储而且第一个成员的地址就是结构体的地址。 结构体中的成员一定会存放在整数倍自身大小的偏移量上比如 int 只会方在 4 的倍数上。 结构体的总大小为最大对齐数的整数倍而最大对齐数与最大的成员大小有关。 可以通过 alignof 查看当前对齐数alignas 指定对齐数或通过 pragma back 指定对齐数。 内存泄漏是什么如何避免 内存泄漏通常是指堆中内存的泄漏应用程序在使用如 mallocreallocnew 等函数分配到堆中内存时使用完毕后应该立即使用 freedelete 释放该内存否则这块内存就无法被再次使用造成内存泄漏。 可以采用记数法当使用 new 或 malloc 时让计数加一delete 或 free 时让计数减一程序执行完毕后打印计数如果计数不为 0 则存在内存泄漏。 虚构函数需要声明为虚函数防止父类指针指向子类对象时编辑器实施静态绑定只会调用父类的析构函数而造成子类的析构不完全造成内存泄漏。 养成 newdelete 和 mallocfree 配对的习惯。 通过 new 构造的对象数组需要使用 delete[] 删除。 程序从开始编译到生成可执行文件的过程【待回答】 语言对比 C 和 Python 的区别【待回答】 STL unordered_set、set、unordered_map、map 的区别应用场景 map 是一种键值对的数据结构支持自动排序底层基于红黑树实现查询复杂度为 OlogN但是占用空间比较大需要存放父子节点染色等信息。 set 和 map 类似支持自动排序底层基于红黑树实现它是一种只有键的数据结构。 unordered_map 不支持排序底层是通过哈希表来实现通过哈希函数计算元素的位置因此查询复杂度为 O(1)。 unordered_set 和 unordered_map 类似不支持排序基于哈希表实现是一种只有键的数据结构。 map、set 主要用于元素有序的场景unordered_map、unordered_set 主要用于需要高效查询的场景。 设计模式 常见的设计模式有哪些【待回答】 单例模式是什么请实现一下单例模式 单例模式是一种创建型设计模式能够保证一个类只有一个实例并提供一个访问该实例的全局节点。它可以解决一个全局使用的类被频繁的创建与销毁的问题比如首页页面刷新使用单例模式可以有效减少内存开销。
class Single {
private:// 防止外界构造和删除对象Single() default; // 构造函数~Single() default; // 析构函数Single(const Single) default; // 拷贝构造函数Single operator(const Single) default; // 运算符重载// 静态析构函数用于在程序结束时销毁实例static void Destructor*() {if (instance ! nullptr) {delete instance;instance nullptr;}}// 静态指针指向Single的唯一实例static Single *instance;// 静态互斥锁用于同步多线程访问static mutex mutex_;
public:// 公共静态方法提供全局访问点static Single* GetInstance() {// 第一次检查查看实例是否已经被创建如果没有则进入同步块if (instance nullptr) {// 使用互斥锁确保同时只有一个线程可以执行实例创建的代码lock_guardmutex lock(mutex_);// 第二次检查确保实例在当前线程等待锁期间未被创建if (instance nullptr) {// 创建Single的新实例instance new Single();// 注册析构函数以便在程序退出时销毁实例atexit(Destuctor);}}return instance;}
};
// 新建实例
Single single::instance nullptr;哲学家进餐问题【待回答】 计算机网络 HTTP / HTTPS 在浏览器地址栏输入 URL 会涉及的技术步骤 浏览器首先会对 URL 进行解析生成发送给服务器的请求报文。 查询服务器域名对应的 IP 地址浏览器会先查询本地缓存本地没有的话就从通过 DNS 服务器进行查询。 查询到服务器的 IP 地址后向服务器三次握手建立 TCP 连接并保持通信。 期间浏览器可以向服务器发送 GETPOST 等请求比如获取数据库资源修改数据信息等。 服务器会对请求进行处理并发送响应报文给浏览器。 浏览器根据返回的响应解析内容并渲染网页呈现在屏幕上。 HTTP 和 HTTPS 的区别 HTTP 是超文本传输协议信息是明文传输的因此存在安全风险HTTPS 在 TCP 和 HTTP 之间加入了 SSL/TLS 协议使得报文可以加密传输更加的安全。 HTTP 建立连接比较简单仅需要 TCP 三次握手HTTPS 不仅需要 TCP 三次握手还需要经历 SSL/TLS 的握手过程。 HTTP 的默认端口是 80HTTPS 的默认端口为 443。 HTTP 不需要数字证书HTTPS 需要申请数字证书来确保服务端的身份是可信的。 HTTP 1.0 / 1.1 / 2 / 3 的区别 HTTP 1.0 是一种无状态无连接的应用层协议浏览器每次请求都需要与服务器建立一个 TCP 连接处理完请求之后立即断开连接不记录过去的状态。 HTTP 1.1 支持长连接在一个 TCP 连接上可以同时传输多个 HTTP 请求和响应减少了网络延迟。 HTTP 2 是基于二进制流的可以分解为独立的帧交错发送提高网络的传输效率。 HTTP3 是最新的版本它使用了 QUIC 协议来提高网络的传输效率。 HTTP 的状态码有哪些 1xx信息状态码表示接收的请求正在处理比如 100 代表一切正常。 2xx成功状态码表示请求被正常处理比如 200 代表成功。 3xx重定向状态码表示需要附加的操作来完成请求比如 301 代表永久重定向访问的资源已经被转移到其他位置。 4xx客户端错误码代表客户端发送的请求中存在错误比如 404 代表访问资源不存在。 5xx服务端错误码代表服务端处理请求时出现错误比如 503 代表服务器繁忙无法处理请求。 HTTP 的请求和响应报文有哪些字段 请求报文的第一行包含了请求方法URL协议类型。 接下来的多行的请求头信息主要包含 Accept 接收类型Connection 连接类型Host 等信息。 请求头和请求体之间用空格区分开最后是请求体的具体内容。 响应报文的第一行包含了协议版本状态码状态描述。 接下来是多行的响应头信息主要包含 Content-length 响应长度Content-type 响应格式 等信息。 响应头和响应体之间同样用空格区分开最后是响应体的具体内容。 HTTP 长连接如何维持 可以在服务端设置一个保活定时器当定时器开始工作的时候就向客户端发送探测报文如果对方收到探测报文并返回 ACK则代表连接还维持否则就已经断开。 可以在服务端设置 keep-alive 参数来保持长连接它可以指定长连接超时时间超时后如何没有数据传输就会自动连接如果有数据传输则超时时间重制。 TCP / UDP TCP 是如何保证可靠传输的 超时重传接收到收到消息后会发送一个响应报文如果发送方一段时间内没有收到响应报文就会触发超时重传机制。 数据校验TCP 头部有校验和用来校验报文是否损坏。 分片排序TCP 会按照最大传输单元 MTU 合理分片发送数据接受方会缓存未按序到达的数据重新排序后发送给应用层。 流量控制当接收方来不及处理发送的数据时会使用滑动窗口提醒发送方降低发送速率。 拥塞控制当网络拥塞时通过拥塞窗口减少发送方的发送速率避免丢包。 TCP 和 UDP 的区别 连接TCP 是面向连接的协议传输前需要先建立连接UDP 可以不建立连接直接传输。 可靠性TCP 是可靠的数据可以无差错有序完整的传输UDP 是尽最大可能的交付并不可靠。 服务对象TCP 是一对一的点到点服务UDP 支持一对一一对多多对一的服务。 拥塞控制TCP 有拥塞控制UDP 没有。 首部开销TCP 首部长开销较大UDP 首部开销固定只有 8 字节较小。 传输方式TCP 是基于字节流的传输无边界但是有序UDP 是基于包的传输有边界但是无序。 应用场景TCP 是面向连接且可靠的因此主要用于类似文件传输这样的场景UDP 是无连接不可靠的但因为其传输较快可以用于类似音视频通话这样的场景。 三次握手的过程是怎样的 最开始客户端和服务端都处于 CLOSE 状态服务端主动监听端口处于 LISTEN 状态。 此时客户端请求连接发送 SYN 报文进入 SYN_SEND 状态。 服务端收到 SYN 报文后发送 SYNACK 报文表示已已经收到消息同意连接随后进入 SYN_RECV 状态。 最后当客户端收到 SYNACK 报文后发送最后的 ACK 报文并进入 ESTABLISH 状态服务端收到 ACK 报文后也进入 ESTABLISH 状态。 四次挥手的过程是怎样的 最开始客户端和服务端处于 ESTABLISH 状态当客户端想要断开时会发送 FIN 报文给服务端并进入 FIN_WAIT_1 状态。 服务端收到 FIN 报文后发送 ACK 报文给客户端表示收到信息随后进入 CLOSE_WAIT 状态。 客户端收到 ACK 报文后进入 FIN_WAIT_2 状态。 服务端将待处理数据处理完毕后向客户端发送 FIN 报文表示同意断开随后进入 LAST_ACK 状态。 客户端收到 FIN 报文后回应 ACK 给服务端进入 TIME_WAIT 阶段。 服务端收到 ACK 报文后直接进入 CLOSE 状态此时服务端已经关闭连接。 而客户端需要等待 2MSL 时间等待完后自动进入 CLOSE_WAIT 状态关闭连接。 四次挥手中 ACK 报文和 FIN 报文可以合并发送吗 在四次挥手中服务端收到了来自于客户端的 FIN 报文会先发送 ACK 报文告知已经收到消息之后在处理完自己的数据之后才会发送 FIN 报文。 如果在收到客户端的 FIN 时没有数据需要处理并且开启了 TCP 延迟确认机制那么二三次握手是可以合并的也就是 ACK 包和 FIN 包合并发送。 封包、拆包是什么是基于 TCP 还是 UDP 的概念 封包和拆包都是基于 TCP 的概念因为 TCP 是无边界的二进制的流传输所以需要对 TCP 进行封包和拆包确保发送和接收数据的不粘连。 封包在发送数据包的时候为每个 TCP 数据包加上一个包头将数据报文分为包头和包体两个部分其中包头中包含数据包的长度信息。 拆包接收方在收到报文后根据包头中数据的长度信息来截取包体。 DNS DNS 负载均衡是什么【待回答】 操作系统 进程 / 进程 进程与线程的区别 调度进程是资源分配的基本单位线程是 CPU 调度的基本单位。 拥有资源进程拥有内存资源、CPU 资源、文件资源等线程只拥有自己的寄存器和栈资源其他资源彼此共享。 切换效率进程的切换内容包含虚拟空间地址、页表、硬件上下文等切换内容保存在内核中会涉及用户态到内核态的切换因此切换效率低线程的切换内容也保存在内核中但因为其切换内容仅包含部分寄存器资源因此切换效率更好些。 并发性多个进程之间可以并发运行一个进程中的多个线程之间也可以并发运行。 进程间通信方法有哪些 管道管道允许一个进程和拥有共同祖先的另一个进程间进行通信。但是管道通信的效率较低不适合频繁的数据交换。 命名管道命名管道允许任意两个进程之间进行通信通过 mkdifo 来创建命名管道。 消息队列消息队列是一种存储在内核中的消息链表有写权限的进程可以向队列中添加消息有读权限的进程可以从队列中取出消息。消息队列中消息体的大小有长度限制不能传输过大的数据在通信过程中存在用户态和内核态之间的数据拷贝开销。 共享内存共享内存把多个进程中的虚拟地址空间映射到相同的物理地址空间中去。这样一个进程写入数据其他进程立马可以看到不需要数据拷贝的过程大大提高了通信效率。但如果多个进程同时修改共享内存那么可以会发生冲突。 信号量信号量是一个整形的计数器主要用于实现进程间的互斥和同步。信号量的值代表资源的数量控制信号量的方式有 P 操作和 V 操作分别发生在进入共享资源离开共享资源时。 信号信号是进程间的一种异步通信机制可以在任何时候发送信号给某一进程。信号的来源有硬件来源ctrlc 终止进程和软件来源kill 命令等。 socketsocket 可以实现跨网络不同主机间进程的通信也可以实现同主机间不同进程间的通信。 线程间通信方法有哪些 线程间的通信目的主要是用于线程同步所以线程没有像进程通信中的数据交换相关的机制。 锁机制锁机制包含互斥锁读写锁条件变量等。互斥锁以排他的方式防止同共享数据同一时间被多个线程修改。读写锁允许多个线程同时读数据但是同一时间只能有一个线程写数据。条件变量可以阻塞线程直到某个特定的条件为真则让线程继续执行通常和互斥锁配合使用。 wait / notify 等待当一个线程调用锁对象的 wait 方式时线程会放弃同步锁进入等待队列直到其他线程进入同步锁调用 notify 唤醒该线程。 volatile 共享内存volatile 具有可见性和有序性其中可见性就是确保线程间可以进行通信。实现可见性需要两个原则保证当 volatile 修饰的变量被线程修改时必须立即刷新到主内存当线程读取 volatile 修饰的数据时需要从主内存中读取新值。 信号量信号量是一个整形的计数器主要用于实现进程间的互斥和同步。信号量的值代表资源的数量控制信号量的方式有 P 操作和 V 操作分别发生在进入共享资源离开共享资源时。 信号信号是进程间的一种异步通信机制可以在任何时候发送信号给某一进程。信号的来源有硬件来源ctrlc 终止进程和软件来源kill 命令等。 回收线程有哪些方法【待回答】 线程切换状态有哪些【待回答】 锁 在并发任务中不加锁可能会出现哪些问题 当两个线程使用同一个全局变量时可能会导致数据不一致的问题。 比如 A 线程修改了数据但是 B 线程还是从缓存中读取未更新的数据导致数据不一致。 死锁是什么产生原因是什么如何避免 死锁在并发编程中线程访问共享资源前会加上互斥锁只有成功持有锁时才能操作共享资源。当两个线程为了访问两个不同的共享资源时会使用两个互斥锁如果这两个互斥锁之间存在着循环依赖则会同时等待对方释放锁导致死锁。 死锁的产生需要同时满足四个条件 互斥条件线程 A 已持有的资源不能被线程 B 持有。 持有并等待条件线程 A 已持有资源 1想要资源 2则需要等待其他线程释放资源 2在此期间资源 1 不会被释放。 不可剥夺条件线程 A 已持有资源 1在使用完毕之前不可以被其他线程剥夺。 环路等待条件线程间获取资源的顺序构成了环路比如线程 A 持有资源 1想要资源 2线程 B 持有资源 2想要资源 1。 避免方法采用资源有序分配法来破坏环路等待条件。当多个线程都需要部分相同资源时应该保证获取资源的顺序是一致的比如线程 A 和线程 B 都是先获取资源 1再获取资源 2。 介绍下几种典型的锁 在多线程环境中为了避免多个线程同时修改同一资源造成资源混乱因此需要在访问共享资源前加锁。 互斥锁互斥锁是为了在任意时间内仅有一个线程可以访问共享资源。当线程A加锁成功时只要线程A没有释放锁那么线程B就会加锁失败并释放CPU让给其他线程。随后线程B进入阻塞睡眠状态等待锁被释放后被内核唤醒继续执行业务。 自旋锁自旋锁也是为了在任意时间内仅有一个线程可以访问共享资源。但是当自旋锁被持有而导致锁获取失败时线程不会立即释放CPU而是一直循环尝试获取锁直到获取锁成功。因此自旋锁一般用于加锁时间很短的场景较少了线程上下文切换的开销效率更高。 读写锁读写锁由读锁和写锁两部分构成如果只读取共享资源用读锁加锁如果需要修改共享资源则需要用写锁加锁它主要用于可以明确区分读操作和写操作的场景在读多写少的场景下可以发挥出优势。 条件变量条件变量是一种同步机制可能使线程在阻塞等待到某个条件发生后继续执行业务。比如在生产者消费者模型中希望在生产 N 个产品后进行庆祝。假设线程 A 是生产线程线程 B 是查询线程。如果使用互斥锁线程 B 需要不断地轮询查看是否满足条件每次查询都需要加锁解锁非常浪费资源。而使用条件变量可以高效解决当线程 B 发现不满足条件时直接进入阻塞等待状态。接着在线程 A 中判断是否满足条件当满足条件时由线程 A 发送信号唤醒线程 B 继续查询避免了无效的加锁解锁操作。 多路复用 IO 多路复用是什么 IO 多路复用是一种处理多个 IO 流的技术。它允许单个进程同时监听多个文件描述符当一个或多个文件描述符准备读写时可以立即响应。这种技术可以提高系统的并发能力和响应能力减少系统资源的浪费。 在 linux 中select、poll、epoll 都是 IO 多路复用的实现方式它们都可以同时监听多个文件描述符一旦某个文件描述符就绪就能通知程序进行对应的读写操作。 IO 模型有哪些 阻塞 IO当进程 A 发起数据请求时如果内核数据没有准备好A 会一直处于等待状态直到内核数据准备才会通知 A。优点是阻塞期间不会占用 CPU 的资源。缺点是如果长时间处于阻塞状态比较占用连接资源。 非阻塞 IO当进程 A 发起数据请求时如果内核没有准备好数据会立即告诉应用 A不会让 A 等待。之后 A 会进行多次的询问直到内核准备好数据告知 A。优点是用户线程不用阻塞实时性好。缺点是用户线程轮询比较占用 CPU 的资源。 IO 多路复用提供一种工具如 select、poll、epoll 来同时监听多个 fd 的操作比如 select 函数可以让内核检查是否有 fd 可读或可写。如果没有准备就绪则进入阻塞状态只要有一个 fd 准备就绪select 会调用进程进行相应的处理。优点是只需要少量的线程就可以监听大量的连接大大减少系统开销。 信号驱动 IO当进程发起一个 IO 操作时会向内核注册一个信号处理函数进程返回不阻塞。当内核准备就绪时会发送信号给进程进程在信号处理函数中调用 IO 读取数据。 异步 IO当进程发起一个 IO 操作时进程返回不阻塞。当内核把整个 IO 处理完毕后才会告知进程如果 IO 操作成功则进程可以直接获取数据。 select、poll、epoll 的区别 连接数不同select 的最大连接数有限制通过 FD_SETSIZE 宏定义大小是 32 的整数倍poll 和 select 本质上没有区别只是最大连接数没有限制因为它通过链表来存储连接信息epoll 虽然有连接数限制但这个数很大1G 内存可以打开近 10 万的连接。 IO 效率不同select 和 poll 都采用轮询的机制会对 socket 进行线性遍历在 socket 过多时效率会很低epoll 是事件驱动的只有活跃的 socket 才会主动调用 callback 函数因此 epoll 的效率与 socket 的数量无关而仅与活跃的 socket 数量有关。 消息传递方式select 和 poll 中的消息传递需要将内核态中的消息传递到用户态涉及内核拷贝动作epoll 中的消息传递是通过内核用户空间共享同一块内存来实现的。 Linux Linux 中异常和中断的区别 发送源不同中断是由硬件设备产生的异常是由 CPU 产生的但都是发送到内核内核调用不同的程序进行处理。 当处理中断时处于中断上下文中当处理异常时处于进程上下文中。 中断不是时钟同步的因此随时可能到来但异常是 CPU 产生的具有时钟同步的特点。 Linux 中常用的命令有哪些 文件mv 移动文件cp 拷贝文件mkdir 创建目录cd 切换目录ls 显示目录中的文件。 权限chmod 修改权限chown 修改所有者useradd 添加新用户。 资源netstat 显示网络状况ping 测试网络连通性ps -ef 查看进程信息top 查看系统资源占用。 压缩tar -zxvf 压缩文件。 Linux 如何查看用到的端口【待回答】 其他 内核态和用户态的区别【待回答】 MySQL 引擎 InnoDB、MylSAM 的区别 事务支持InnoDB 支持事务具有 ACID 属性MyISAM 不支持事务适用于读多写少的场景。 锁支持InnoDB 支持行级锁仅锁定实际需要的数据MyISAM 只支持表级锁。 外键支持InnoDB 支持外键保证了数据的完整性MyISAM 不支持外键。 崩溃恢复InnoDB 在崩溃后可以自动恢复MyISAM 崩溃后需要手动恢复或使用备份恢复。 备份InnoDB 支持热备份即在数据库运行的时候进行备份MyISAM 不支持热备份需要保证备份期间没有写操作。 锁 MySQL 的行级锁有哪些 记录锁仅仅锁定一条记录。 间隙锁锁定一个范围但是不包括记录本身。 临键锁锁定一个范围同时也锁定记录本身。 在读提交隔离级别下行级锁的种类只有记录锁。 在可重复读隔离级别下行级锁的种类有记录锁间隙锁临键锁。 慢查询 如何排查一条慢 SQL如何优化 慢查询是记录在 MySQL 中响应时间超过阈值的语句这些语句被记录在慢查询日志中。慢查询日志可以通过设置 slow_query_log 属性来开启。 可以通过 explain 指令去查询 SQL 语句的执行计划看 SQL 语句是否使用索引全表扫描等。 如果是因为没有使用索引那么就使用合适的索引。 如果是因为数据表过大即使使用索引也慢那么需要考虑分表。 事务 事务的四大特性是什么 原子性一个事务中的操作要么全部完成要么全部不满成不存在只完成部分的情况。如果中间发生错误会进行回滚操作。 一致性事务开始前和结束后数据库的完整性没有遭到破坏。 隔离性当多个事务访问数据库时多个事务之间相互隔离互不干扰。 持久性事务结束后对数据库的修改应该是永久的即使遇到故障也不会丢失。 事务的隔离级别有哪些 读未提交一个事务还没有提交时它做出的修改可以被其他事务读到。可能会出现脏读、不可重复读、幻读等情况。 读提交一个事务在提交后它做出的修改才能被其他事务读到。可能会出现不可重复读幻读等情况。 可重复读当前执行的事务对数据的修改对外是不可见的因此其他事务多次执行相同查询操作时结果应该是相同的。可能会出现幻读情况。 可串行化读当多个事务对同一个记录进行读写时会加上读写锁一个事务处理完毕后才会轮到下一个事务。 脏读、幻读、丢弃更改、不可重复读是什么 脏读事务 A 读取到了事务 B 未提交并修改过的数据那么当事务 B 发生错误并回滚时事务 A 读取的数据和实际的数据不一致发生脏读现象。 幻读事务 A 多次查询符合某个条件的记录数量但同时事务 B 进行一些插入删除操作使得事务 A 多次查询的结果不一致发生幻读现象。 丢弃修改事务 A 和事务 B 同时对一个数据进行操作但最终事务 B 的结果把事务 A 的结果覆盖发生丢弃修改现象。 不可重复读事务 A 读取了一个数据但随后事务 B 对数据进行了修改事务 B 再次读取发现数据不一样发生了不可重复读现象。 索引 为什么 MySQL 索引使用 B 树为什么不用 B 树红黑树hash 表 Mysql 中的数据是放在磁盘的读取数据会有访问磁盘的操作而访问磁盘的 IO 操作效率很低。 二分查找树可以快速地查找到数据但是极端情况下比如依次插入递增的元素那么查询数据的复杂度会从 O(logn) 退化为 O(n)。 自平衡二叉树是高度平衡的确保复杂度为 O(log n)但是当数据量过大时树的高度依然很高磁盘 IO 次数也更多。 B 树和 B 树中一个节点有多个子节点因此树的高度会变低磁盘 IO 次数也会降低查询效率更高。 B 树中的叶子节点存放数据非叶子节点仅存放索引在相同数据量下B 数的非叶子节点可以存放更多的索引因此高度比 B 树更低查询效率也更高。 B 树中有着大量的冗余索引这些冗余索引可以让 B 树在插入删除时的效率更高树的结构也不会发生太复杂的变化 B 树的叶子节点之间用链表连接了起来有利于范围查询而 B 树只能通过前序遍历来范围查询。 红黑树属于一种平衡二叉树它没有实现绝对平衡而是选择实现局部平衡使得查找删除插入的复杂度都为 O(log2 n)。但它本质上还是二叉树当数据量过大时高度还是会很高磁盘 IO 次数会增加导致效率变低。 当进行连续数据查询时红黑树也需要通过前序遍历来范围查询效率不如 B 树。 采用哈希表的查询复杂度为 O(1)速度确实更快但数据库中可能查询多条连续数据由于 B 树的有序性进行范围查询时会比 hash 表更快。 hash 表需要把数据全部加载到内存中非常消耗内存而采用 B 树可以按节点分段加载内存消耗更少。 MySQL 中有哪些索引 普通索引仅可以加速查询。 唯一索引可以加速查询并且列值唯一可以为空。 主键索引可以加速查询并且列值唯一不可以为空表中只能有一个主键。 组合索引多列组成的一个索引专门用于组合搜索效率高于索引合并。 全文索引对文本的内容进行分词搜索。 索引合并使用多个单列索引组合搜索。 覆盖索引使用多字段的联合索引使得从非主键中就能查询到的记录而不需要查询主键避免了回表可以减少树的搜索次数。 聚簇索引它的表数据和索引是放在一起存储的存放在叶子节点中找到索引就相当于找到了数据。 非聚簇索引它的表数据和索引分为两部分存储它的叶子节点只存放对应的主键值根据主键值二次查找数据。 使用索引的好处有哪些【待回答】 使用索引的注意事项有哪些【待回答】 备份
数据库的备份和灾备你有了解吗 数据库的备份和灾备主要是为了保护数据库中的数据不因为意外情况而丢失。 数据库的备份是指定期为数据库创建副本到另一个位置当发生数据丢失或数据库崩溃时进行恢复。 数据库的容灾是指当数据库主服务器发生故障或不可用时确保备用服务器可以接管数据库系统并提供相应服务。 数据库的备份可以分为完全备份和增量备份其中完全备份是指备份数据中的所有数据因此比较耗时和占用内存。增量备份是指仅备份距离上次备份后修改过的数据因此这种备份方式速度更快占用内存更少。 数据库的备份还可以分为冷备份和热备份其中冷备份是指只有当数据库停止运行没有发生数据修改时才可以进行备份而热备份可以在数据库运行的过程中进行备份。 数据库的容灾可以分为数据库复制和数据库镜像其中数据库复制把数据库的副本移动到另一个服务器使其可以独立运行数据库镜像是创建数据库的实时副本可以提供几乎无中断的故障转移但更耗费网络资源。 Redis 概念 Redis 是什么 Redis 是一种非关系型的数据库与传统的数据库不同Redis 中的数据是存储在内存中的所以读写速度非常的快因此 Redis 被广泛应用于缓存方向。 Redis 提供了多种数据类型来支持不同的业务场景比如字符串、哈希表、列表、集合、bitmap、geo、hyperloglog 等。 数据结构 Redis 的底层数据结构有哪些 简单动态字符串 SDSSDS 的结构中包含参数 len用来记录字符串的长度因此查询字符串长度的复杂度仅为 O(1)速度快。SDS 还是二进制安全的它不像 C 字符串一样用 ‘\0’ 标识字符串末尾而是使用 len 来记录因此可以存放任意的二进制数据。SDS 中参数 alloc 用于计算字符串的剩余空间在拼接字符串时如果空间不够会自动扩容避免缓存区溢出更加的安全。 链表链表的每个节点中都有一个前向和后向指针因此是双向链表。链表结构中的 head 和 tail 可以获取头尾元素节点dupfree 和 match 函数可以复制释放和比较元素节点。参数 len 可以用来获取链表长度查询链表长度的复杂度仅为 0(1)。链表节点由于使用的是 void* 指针因此可以存放不同类型的数据。它的缺点是内存不连续数据查找效率不高以及创建节点内存开销大。 压缩列表压缩列表类似于数组使用连续的内存块来存放数据。当前元素节点会记录前一节点的长度因此可以实现双向遍历。压缩列表在存储数据时会根据数据的大小分配合适的内存可以很好的节省了内存空间。但是当插入一个较大元素时可能出现记录前一节点长度所需空间不够的情况导致连锁更新使压缩列表的性能下降。 哈希表哈希表是一种 key-value 的数据结构可以使用 O(1) 的复杂度进行快速查询。然而随着数据的不断增加可能会发生哈希冲突。redis 采用链式哈希结构来解决哈希冲突就是将拥有相同哈希值的数据用链表串起确保数据仍可以被查询到。另一种解决方法就是 rehash当发生哈希冲突时新建一个哈希表并扩增哈希桶的大小为两倍迁移旧哈希表中的数据到新哈希表中。 整数集合整数集合是一块连续的内存空间类似于数组。其中元素的存放类型取决于参数 encoding 的属性比如 81632 位的 int。此外当插入的新数据类型超过当前最大类型时会进行类型的升级操作。 跳表跳表在链表的基础上进行改进的实现了一种多层的有序链表可以快速定位数据。它的查询步骤是从头节点的顶层开始查找第一个大于指定元素的节点再退回上一节点在下一层节点继续查找使得查找的复杂度为 O(log n)。 锁 Redis 如何实现分布式锁 使用 setnx expire 实现。首先利用 setnx 将 key 设为 value当 key 不存在时加锁成功而当 key 存在时什么也不做。因为分布式锁需要超时机制因此使用 expire 来设置过期时间。但存在问题因为 setnx 和 expire 是两步操作不具有原子性如果执行第一条语句后发生异常锁将无法过期。 可以采用 lua 脚本将 setnx 和 expire 写在脚本中由于 lua 脚本在 redis 中的实现是原子性的因此加锁和设置过期具有原子性。 使用 set 及 nx 可选参数实现。例如 EX 代表设置过期时间NX 代表 key 不存在时设置过期时间。其中设置的 value 必须具有唯一性以便区分来自不同客户端的加锁操作。释放锁时需要根据 value 值判断是不是自己的锁再进行释放锁操作。 缓存 如何保证缓存与数据库的数据一致性 使用缓存就会涉及到数据库和缓存的存储双写会导致数据不一致的问题。数据一致性分为强一致性即用户写入什么读取的立刻就是什么用户体验好但是对系统性能影响大。弱一致性写入数据后不保证数据立即一致而是某个时间级别后能够一致。 旁路缓存模式适用于请求比较多的场景服务端会以数据库的结果为准。读请求时先读取缓存如果命中的话直接返回数据未命中的话从数据库中获取数据并添加到缓存中。写请求时先更新数据库再删除缓存。 读写穿透模式服务端会以缓存的结果为准。读请求时先读取缓存如果命中的话直接返回数据未命中的话从数据库中获取数据并添加到缓存中。当进行写请求时先检查缓存缓存未存在则直接更新数据库如果缓存存在则先更新缓存再更新数据库。读写穿透在旁路缓存的基础上提供了 cache-provider 层并进行了封装在旁路缓存中缓存未命中客户端自己负责写入数据到缓存而读写穿透中是由 cache 服务自动将数据写入缓存的。 异步缓存写入模式该模式和缓存穿透类似都是通过 cache 服务负责缓存和数据库的读写。不同的是读写穿透同时更新数据库和缓存而该模式是先更新缓存数据之后通过异步的方式批量更新数据库。这种同步方式的缺点是缓存还没有来得及更新到数据库就已经失效。适合用在对写入数据需要高但对一致性需求不高的情况比如网页的浏览量点赞量等场景。 Redis 的数据优化方案有哪些【待回答】 热点数据和冷数据是什么【待回答】 持久化 Redis 有哪些持久化机制 Redis 有两种持久化方式分别为 RDB 持久化和 AOF 持久化技术。 通过持久化机制将内存中的数据同步到硬盘中当 Redis 重启后将持久化数据从硬盘数据加载到内存达到恢复数据的目的。Redis 默认使用 RDB 持久化。 RDBRedis 可以通过创建快照来获取某个时刻的内存数据副本创建的快照是二进制文件。创建快照完成后对快照进行备份发送给其他服务器创建数据副本也可以在重启时用快照恢复自身的服务器数据。 Redis 有两个命令来生成快照分别是 save 和 bgsave。其中 save 会在主线程中生成文件而 bgsave 会创建子线程来生成文件避免主线程的阻塞。RDB 的备份是全量备份如果备份频繁的话会影响 Redis 的性能但不频繁可能会丢失较长时间的数据。 AOFRedis 在执行一条写操作命令时会把命令以追加到形式写入到磁盘中的日志里。当 Redis 重启的时候读取并执行日志中的命令就可以恢复内存数据。AOF 有三种策略 写回策略Redis 在执行完写操作后会将命令写入缓冲区系统调用 write() 函数将缓冲区命令写入 AOF 日志由内核决定何时将日志写入到磁盘。其中参数为 always可以让内核在每次执行写操作后将日志写入到磁盘everysec可以让内核每秒将日志写入到磁盘参数为 no意味着将日志写入磁盘的时机由内核决定。 重写机制随着写操作的越来越多AOF 日志文件的大小也会越来越大这会导致性能的问题。于是 redis 给 AOF 文件大小设置阈值当超过后会启用 AOF 重写机制。当出现了多条命令修改同一个 key 时只会记录最后一条更新 key 的命令。然后将重写后的 AOF 文件覆盖掉现有的 AOF 文件AOF 文件的大小也得到了压缩。 后台重写当触发 AOF 重写机制时如果 AOF 文件太大的话主线程的重写是很耗时的因此 AOF 重写可以由后台的子进程完成在此期间主进程一直是非阻塞的。 Redis 也支持 RDB 和 AOF 的混合持久化。使用混合持久化时AOF 重写会将内存数据以快照的形式全量写入 AOF 文件之后将新增命令以 AOF 的形式增量写入到 AOF 文件实现混合持久化。 面试算法 双指针 11. 盛最多水的容器 [数组] [面积] (双指针)
class Solution {
public:int maxArea(vectorint height) {// 双指针int left 0, right height.size() - 1;// 最大面积, 当前面积int res 0, cur 0;// 缩小区域while (left right) {cur min(height[left], height[right]) * (right - left);res max(res, cur);// 哪一边比较短, 移动哪一边if (height[left] height[right]) {left;} else {right--;}}return res;}
};31. 下一个排列 [数组] [排列] (双指针) (推导)
class Solution {
private:int flag 0; // 设置一个标志位, 代表找到当前排列了
public:void nextPermutation(vectorint nums) {int n nums.size();// 从后往前找, 找到第一个 nums[i] nums[j] 的地方int i n - 2, j n - 1;while (i 0 nums[i] nums[i 1]) {i--;}// 此时不是最后一个排列if (i 0) {// 找到一个比 nums[i] 大的第一个元素while (j i nums[j] nums[i]) {j--;}// 交换两者swap(nums[i], nums[j]);// 再将剩余部分逆转, 把降序变为升序reverse(nums.begin() i 1, nums.end());} else {// 如果是最后一个排列reverse(nums.begin(), nums.end());}return;}
};42. 接雨水 [数组] [面积] (双指针)
class Solution {
public:int trap(vectorint height) {// 左边边界, 右边边界, 最边上存不了水int left 0, right height.size() - 1;// 左边最大值, 右边最大值int left_max height[left], right_max height[right];// 当前装水量, 总装水量int cur 0, res 0;while (left right) {left_max max(left_max, height[left]);right_max max(right_max, height[right]);if (left_max right_max) {// 左指针的leftMax比右指针的rightMax矮// 说明左指针的右边至少有一个板子 左指针左边所有板子// 那么可以计算左指针当前列的水量左边最大高度-当前列高度res left_max - height[left];left;} else {res right_max - height[right];right--;}}return res;}
};160. 相交链表 [链表] [相交] (双指针)
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 双指针ListNode *p1 headA, *p2 headB;// A 走到 nullptr 后接着走 B, B 走到 nullptr 后接着走 A// 当 p1 p2 的地方就是相交的地方while (p1 ! p2) {if (p1 nullptr) p1 headB;else p1 p1-next;if (p2 nullptr) p2 headA;else p2 p2-next;}return p1;}
};LCR 139. 训练计划 I [数组] [元素交换] (双指针)
class Solution {
public:vectorint trainingPlan(vectorint actions) {int n actions.size();if (n 1) return actions;// 定义双指针一个指向头一个指向尾int left 0, right n - 1; while (left right) {// 依次移动找到数时暂停while (left right actions[left] % 2 1) {left;}while (left right actions[right] % 2 0) {right--;}std::swap(actions[left], actions[right]);}return actions;}
};三指针 215. 数组中的第K个最大元素 [数组] [第K大元素] (三指针) (快速排序)
class Solution {
private:int target; // 目标索引, 第 n-k 小int res; // 目标值
public:int findKthLargest(vectorint nums, int k) {// 快速排序, 每次可以确定好一个元素的位置, 当索引为 k 时, 代表找到int n nums.size();// 第 k 大就是第 n - k 小target n - k;// 开始快排quickSort(nums, 0, n - 1);return res;}// 快排 [left, right]void quickSort(vectorint nums, int left, int right) {if (left right) return;// 只剩一个元素if (left right left target) {res nums[target];return;}// 先获取一个哨兵, 将数组分为小于它的部分和大于它的部分vectorint edge part(nums, left, right);// 如果 target 在左右边界之间, 则找到if (edge[0] target target edge[1]) {res nums[target];return;}// 继续递归quickSort(nums, left, edge[0] - 1);quickSort(nums, edge[1] 1, right);}// 分隔, 三指针, 这里返回相同元素的左右边界是为了去重vectorint part(vectorint nums, int left, int right) {int pivot_idx rand() % (right - left 1) left;int pivot nums[pivot_idx];// [pivot] [1] [2] [3] [4]// L/LP CP RP swap(nums[pivot_idx], nums[left]);// 设置三个指针, 分别指向小于 pivot 的元素, 当前元素, 大于 pivot 的元素int curp left 1, leftp left, rightp right 1;// 还没走到尽头, rightp 始终是指向大于 pivot 元素的while (curp rightp) {if (nums[curp] pivot) { // 小于哨兵leftp;swap(nums[curp], nums[leftp]);curp;} else if (nums[curp] pivot) { // 大于哨兵rightp--;swap(nums[curp], nums[rightp]);} else { // 相等, 什么也不做curp;}}// 最后 leftp 指向的内容肯定是最后一个小于 pivot 的, 它与 pivot 交换swap(nums[left], nums[leftp]);// 返回等于 pivot 的左边界和右边界 [小于] [pivot] [大于]return {leftp, rightp - 1};}
};滑动窗口 3. 无重复字符的最长子串 [字符串] [子串] (滑动窗口)
class Solution {
private:unordered_mapchar, int window; // 窗口内的字符
public:int lengthOfLongestSubstring(string s) {int left 0, right 0;int res 0;// 开始滑动while (right s.size()) {char cur_r s[right];right;window[cur_r];// 如果出现次数为第二次, 则缩小窗口, 直到出现次数为一次while (window[cur_r] 1) {char cur_l s[left];left;window[cur_l]--;}// 此时更新下符合条件的当前字符长度 [left, right-1]res max(res, right - left);}return res;}
};二分法 153. 寻找旋转排序数组中的最小值 [旋转数组] [最小值] (二分法)
class Solution {
public:int findMin(vectorint nums) {int left 0, right nums.size() - 1;// 二分法 [0, n-1]while (left right) {int mid left (right - left) / 2;if (nums[mid] nums[right]) {right mid;} else if (nums[mid] nums[right]) {left mid 1;} else {right--;}}return nums[left];}
};162. 寻找峰值 [数组] [峰值] (二分法)
class Solution {
public:int findPeakElement(vectorint nums) {int left 0, right nums.size() - 1;// [0, n-1]while (left right) {// [left, mid] [mid1 right]int mid left (right - left) / 2;if (nums[mid] nums[mid 1]) {// [left, mid]right mid;} else {// [mid1, right], 相等的时候左右移动都一样left mid 1;}}return left;}
};DFS 200. 岛屿数量 [矩阵] [岛屿] (DFS)
class Solution {
private:int m, n; // 地图的宽高int res 0; // 岛屿数量vectorvectorint dirts {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 方向
public:int numIslands(vectorvectorchar grid) {m grid.size(), n grid[0].size();// 从每个点都出发找一遍for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {DFS(grid, i, j);res;}}}return res;}// DFS 算法void DFS(vectorvectorchar grid, int i, int j) {// 终止条件if (i 0 || i m || j 0 || j n) return;if (grid[i][j] 0) return;// 将已遍历岛屿沉默grid[i][j] 0;// 遍历四周的元素for (auto dirt : dirts) {DFS(grid, i dirt[0], j dirt[1]);}}
};贪心 452. 用最少数量的箭引爆气球 [数组] [区域重合] (贪心) (排序)
// 找非重叠区域最多有几个, 就是需要射多少箭
class Solution {
private:int res 0; // 需要射的最少的箭数long cur_end LONG_MIN; // 上一个区间的 end [-wq, INT_MIN]
public:int findMinArrowShots(vectorvectorint points) {// 按 end 排序sort (points.begin(), points.end(), [](vectorint a, vectorint b) {return a[1] b[1];});// 开始遍历一个个区间for (auto point : points) {int start point[0], end point[1];// 碰到重叠区域, 这题擦边也可以射气球if (start cur_end) continue;// 没碰到重叠区域res;cur_end end;}return res;}
};其他 8. 字符串转换整数 [字符串] [转换] (遍历)
class Solution {
public:int myAtoi(string s) {long res 0; // 最终的结果int flag 1; // 正负标志位int i 0; // 元素下标while (s[i] ) i; // 去掉前面的空格if (s[i] -) flag -1; // 标志为负数if (s[i] || s[i] -) i; // 移动到数字处// 开始转换while (i s.size()) {if (s[i] 0 || s[i] 9) break;int cur s[i] - 0;cout cur;// 如果是负数 -2147483648if (flag -1 (res INT_MAX / 10 || (res INT_MAX / 10 cur 8))) {return INT_MIN;}// 如果是正数 2147483647if (flag 1 (res INT_MAX / 10 || (res INT_MAX / 10 cur 7))) {return INT_MAX;}res res * 10 cur;i;}return flag * res;}
};【待做】【199】
