C++开发基础
软件开发基础
2024-01-08 20:13 星期一
博客内容来自相关书籍和网站内容总结，仅供个人参考使用：笔者@东北大学 StuBoo
使用目录快速转到面试问题汇总、常见算法问题
1.C++语言基础
1.1 C++语言特性概览
面向对象编程（OOP）：C++ 支持面向对象编程，包括封装、继承和多态。通过类和对象，可以将数据和方法组织成单个单元，提高了代码的重用性和可维护性。
泛型编程：C++ 具有模板（Templates）特性，使得可以编写通用代码，使代码可以适用于不同的数据类型，实现了泛型编程。
内存管理：C++ 具有直接的内存管理能力，可以使用指针、引用和动态内存分配等机制来精确地控制内存的分配和释放。
多线程编程：通过标准库中的thread头文件可以创建和管理线程。这个头文件包含了用于操作线程的类和函数。C++11 引入了跨平台的线程库，允许开发者在不同的操作系统上使用相同的线程接口。
网络编程：C++ 通过各种库和框架（如Boost.Asio、Poco、CppNetLib等）提供了强大的网络编程支持。它允许开发者创建客户端和服务器应用程序，进行网络通信，支持各种网络协议（如TCP、UDP、HTTP等）
标准模板库（STL）：C++ 提供了 STL，它包含了一组模板类和函数，例如容器（如vector、list、map）、算法（如排序、搜索等）和迭代器等，提供了高效的数据结构和算法。
1.2面向对象特性
C++ 是一种支持面向对象编程（OOP）的语言，它的三大面向对象特性包括：封装、继承和多态。
封装（Encapsulation）：
封装是一种将数据和操作（方法或函数）捆绑在一起并限制外部访问的机制。通过使用类，C++ 允许将数据（成员变量）和方法（成员函数）组合成一个单一的单元，这样可以控制数据的访问权限。
类中的数据成员可以被标记为私有（private）或受保护（protected），从而限制对它们的直接访问，而对外提供公共接口（公有成员函数）来间接操作这些数据，这就是封装的体现。
继承（Inheritance）：
继承是一种允许一个类（派生类/子类）从另一个类（基类/父类）继承属性和行为的机制。派生类可以重用基类的成员变量和成员函数，并且可以添加自己的特定成员。
通过继承，可以构建出一个类层次结构，使得代码的重用性更强，同时也能更好地组织和管理类之间的关系。
多态（Polymorphism）：
多态性允许一个函数在不同的对象上表现出不同的行为。它可以通过函数重载（函数名相同，参数列表不同）、运算符重载、虚函数和抽象类（接口）实现。
最常见的多态性形式是运行时多态（动态多态），通过虚函数和继承实现。在运行时，根据实际对象的类型调用相应的函数，这种机制称为动态绑定。
1.2.1静态多态和动态多态
静态多态
静态多态是指在编译时就能确定要调用的函数，它主要通过函数重载和运算符重载来实现。编译器在编译阶段确定调用的函数，因此也称为早期绑定。
实现原理：
函数重载：函数名称相同，但参数类型或个数不同。
运算符重载：重载了类的成员函数或全局函数，使其具有不同的行为。
代码示例：
#include <iostream>
class StaticPolymorphism {
public:
// 函数重载实现静态多态
void print(int value) {
std::cout << "Integer value: " << value << std::endl;
}
void print(double value) {
std::cout << "Double value: " << value << std::endl;
}
};
int main() {
StaticPolymorphism obj;
obj.print(5); // 调用 print(int)
obj.print(3.14); // 调用 print(double)
return 0;
}
动态多态
动态多态是指在运行时根据对象的实际类型来确定调用的函数。主要通过虚函数和继承来实现。在运行时，根据对象的类型确定调用的函数，因此也称为晚期绑定。
实现原理：
虚函数：在基类中使用 virtual 关键字声明的函数，可以被派生类重写。
继承：派生类可以覆盖基类中的虚函数，根据实际对象的类型进行调用。
代码示例：
#include <iostream>
class Base {
public:
// 虚函数实现动态多态
virtual void print() {
std::cout << "Base class print() called" << std::endl;
}
};
class Derived : public Base {
public:
// 覆盖基类的虚函数
void print() override {
std::cout << "Derived class print() called" << std::endl;
}
};
int main() {
Base* basePtr;
Base baseObj;
Derived derivedObj;
basePtr = &baseObj;
basePtr->print(); // 调用 Base::print()
basePtr = &derivedObj;
basePtr->print(); // 调用 Derived::print()
return 0;
}
静态多态和动态多态的区别：
| 绑定时间 | 实现方式 | 适用性 | 效率 | |
|---|---|---|---|---|
| 静态多态 | 在编译时确定调用的函数，早期绑定 | 通过函数重载和运算符重载实现 | 适用于函数重载和运算符重载，但不适用于类的层次结构 | 效率更高，因为函数调用在编译时确定 |
| 动态多态 | 在运行时确定调用的函数，晚期绑定 | 通过虚函数和继承实现 | 适用于类的层次结构，通过派生类重写基类的虚函数来实现多态 | 运行时需要额外的虚函数查找，可能会有些许性能损失 |
1.2.2 C++中动态多态的实现
在 C++ 中，多态性的主要实现依赖于虚函数（Virtual Functions）和虚函数（vtable）。
虚函数：
虚函数是在基类中声明并使用 virtual 关键字标记的成员函数。它允许在派生类中进行覆盖（重写），并在运行时根据对象的实际类型调用相应的函数。
在基类中声明为虚函数的函数可以在派生类中被重写。如果在派生类中使用 override 关键字重新定义了基类的虚函数，编译器会检查其覆盖关系，从而提高代码的可读性和安全性。
虚函数允许基类指针或引用指向派生类对象，并且在运行时根据实际对象的类型来决定调用的函数，这就是多态性的体现。
虚函数表（vtable）：
虚函数表是用来实现动态多态性的关键机制之一。对于每个含有虚函数的类，编译器会生成一个对应的虚函数表。
虚函数表是一个存储虚函数地址的表格，每个对象都有一个指向其类的虚函数表的指针。该指针通常称为虚指针（vptr），它指向对象所属类的虚函数表。
在运行时，当调用虚函数时，实际上是通过对象的虚指针找到对应的虚函数表，然后根据函数在虚函数表中的索引调用正确的函数。
如果派生类重写了基类的虚函数，那么虚函数表中的对应位置会被新的函数地址所覆盖，确保调用时能够执行派生类的函数。
在 C++ 中，虚函数指针（vptr）是实现动态多态性的关键。在继承体系中，子类继承了基类的虚函数并且可以覆盖（重写）这些虚函数。
虚函数指针（vptr）：
存储虚函数表地址：每个类（含有虚函数的类）的对象都包含一个指向其类的虚函数表（vtable）的指针，称为虚函数指针（vptr）。
动态绑定：在运行时，通过虚函数指针可以动态定位到对象的虚函数表，并根据实际对象的类型来确定调用的函数。
多态实现：通过虚函数指针实现运行时多态性，当基类指针指向派生类对象时，调用虚函数会根据对象的实际类型在虚函数表中找到正确的函数进行调用，这就是多态性的体现。
子类继承虚函数：
覆盖基类的虚函数：派生类可以重新定义（覆盖）基类中的虚函数，如果派生类中重新定义了基类的虚函数，那么派生类的虚函数表会覆盖基类相应位置的函数地址。
动态绑定：子类继承了基类的虚函数，如果子类重新定义了基类的虚函数，那么在使用派生类对象调用该虚函数时，根据派生类对象的实际类型确定调用的是派生类的虚函数还是基类的虚函数。
代码示例：
#include <iostream>
class Base {
public:
virtual void show() {
std::cout << "Base::show()" << std::endl;
}
};
class Derived : public Base {
public:
void show() override {
std::cout << "Derived::show()" << std::endl;
}
};
int main() {
Base* ptr;
Base baseObj;
Derived derivedObj;
ptr = &derivedObj; // 基类指针指向派生类对象
ptr->show(); // 调用派生类的虚函数
return 0;
}
基类指针 ptr 指向派生类对象 derivedObj 时，调用 ptr->show() 时，根据 ptr 所指向的实际对象类型（派生类对象），会动态地调用派生类 Derived 中的 show() 函数，进行动态绑定，从而实现多态。
1.3C++泛型编程
C++ 中的泛型编程主要依赖于模板（Templates）和泛型算法，模板是实现泛型编程的关键组成部分。
组成部分：
模板（Templates）：
函数模板（Function Templates）：允许定义通用的函数，可以用于多种数据类型，通过模板参数来实现参数化的数据类型。
类模板（Class Templates）：类似于函数模板，允许定义通用的类，通过模板参数化的数据类型。
模板允许编写通用的代码，通过在编译时进行模板实例化来生成特定类型的代码。编译器在编译阶段根据实际使用的数据类型生成模板函数或模板类的实例。
泛型算法：
泛型算法是针对不同数据类型的通用算法。C++ 标准模板库（STL）提供了大量的泛型算法，如排序、查找、操作容器等，它们使用模板来实现对不同数据类型的通用处理。
泛型算法使用模板来实现通用性。例如，对于排序算法，通过使用模板参数传递比较函数，可以针对不同的数据类型和排序要求实现通用的排序算法。
示例：
-
函数模板：
#include <iostream> template <typename T> T maximum(T x, T y) { return (x > y) ? x : y; } int main() { std::cout << "Max of 3 and 5 is: " << maximum(3, 5) << std::endl; // 调用模板函数 std::cout << "Max of 3.14 and 6.28 is: " << maximum(3.14, 6.28) << std::endl; // 调用模板函数 return 0; } -
类模板：
#include <iostream> template <typename T> class Pair { private: T first; T second; public: Pair(T a, T b) : first(a), second(b) {} T getFirst() { return first; } T getSecond() { return second; } }; int main() { Pair<int> intPair(10, 20); // 使用模板类实例化出一个具体类型的类 std::cout << "First value: " << intPair.getFirst() << std::endl; std::cout << "Second value: " << intPair.getSecond() << std::endl; Pair<double> doublePair(3.14, 6.28); std::cout << "First value: " << doublePair.getFirst() << std::endl; std::cout << "Second value: " << doublePair.getSecond() << std::endl; return 0; }
1.3.1STL六大组件
STL大体分为六大组件，分别是:容器、算法、迭代器、仿函数、适配器(配接器)、空间配置器
1.容器:各种数据结构，如vector、list, deque,set、map等,用来存放数据。
2.算法:各种常用的算法，如sort、find、copy、for_each等
3.迭代器:扮演了容器与算法之间的胶合剂。
4.仿函数:行为类似函数，可作为算法的某种策略。
5.适配器:一种用来修饰容器或者仿函数或迭代器接口的东西。
6.空间配置器:负责空间的配置与管理。
容器
STL容器就是将运用最广泛的一些数据结构实现出来。
常用的数据结构:数组,链表,树,栈,队列,集合，映射表等这些容器分为序列式容器和关联式容器两种:
关联式容器:二叉树结构，各元素之间没有严格的物理上的顺序关系。
序列式容器:强调值的排序，序列式容器中的每个元素均有固定的位置。
算法
有限的步骤，解决逻辑或数学上的问题，这一门学科我们叫做算法(Algorithms)
算法分为:质变算法和非质变算法。
质变算法:是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等。
非质变算法:是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等。
迭代器
提供一种方法，便之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。
每个容器都有自己专属的迭代器。
迭代器使用非常类似于指针，初学阶段我们可以先理解迭代器为指针。
迭代器种类:
种类 功能 支持运算
输入迭代器 对数据的只读访问 只读，支持++、==、! =
输出迭代器 对数据的只写访问 只写，支持++
前向迭代器 读写操作，并能向前推进迭代器 读写，支持++、==、!=
双向迭代器 读写操作，并能向前和向后操作 读写，支持++、-,
随机访问迭代器 读写操作，可以以跳跃的方式访问任意数据，功能最强的迭代器 读写，支持++、-、[n]、-n、<、<=、>、>=
常用的容器中迭代器种类为双向迭代器，和随机访问迭代器。
容器迭代器示例
最常见容器Vector，可以理解为数组。
vector存放内置数据类型
容器：vector
算法：for_each
迭代器： vector<int>::iterator
1.3.2STL-常用容器
1.3.2.1string容器
1.string基本概念
本质:string是C++风格的字符串，而string本质上是一个类。
string和char * 区别: char*是一个指针，string是一个类，类内部封装了char*，管理这个字符串，是一个char*型的容器。
特点:
string类内部封装了很多成员方法，例如:查找find，拷贝copy，删除delete，替换replace，插入insert。
string管理char*所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责。
2.string构造函数
构造函数原型:
string(); //创建一个空的字符串例如:string str;
string(const char* s); //使用字符串s初始化
string(const string& str); //使用一个string对象初始化另一个string对象
string(int n, char c); //使用n个字符c初始化
3.string赋值操作
功能描述:
·给string字符串进行赋值
赋值的函数原型:
string& operator=(const char* s); //char*类型字符串赋值给当前的字符串
string& operator=(const string &s); //把字符串s赋给当前的字符串
string& operator=(char c); //字符赋值给当前的字符串
string& assign(const char *s); //把字符串s赋给当前的字符串
string& assign(const char *s,int n); //把字符串s的前n个字符赋给当前的字符串
string& assign(const string &s); //把字符串s赋给当前字符串
string& assign(int n,char c); //用n个字符c赋给当前字符串
4.string字符串拼接
功能描述:实现在字符串末尾拼接字符串
函数原型:
string& operator+=(const char* str); //重载+=操作符
string& operator+=(const char c); //重载+=操作符
string& operator+=(const string& str); //重载+=操作符
string& append(const char *s); //把字符串s连接到当前字符串结尾
string& append(const char *s, int n); //把字符串s的前n个字符连接到当前字符串结尾
string& append(const string &s); //同operator+=(const string& str)
string& append(const string &s, int pos, int n); //字符串s中从pos开始的n个字符连接到字符串结尾
5.string查找和替换
功能描述:
查找:查找指定字符串是否存在
替换:在指定的位置替换字符串 I
函数原型:
int find(const string& str, int pos =0) const; //查找str第一次出现位置,从pos开始查找
int find(const char* s, int pos =0) const; //查找s第一次出现位置,从pos开始查找
int find(const char* s, int pos, int n) const; //从pos位置查找s的前n个字符第一次位置
int find(const char c, int pos =0) const; //查找字符C第一次出现位置
int rfind(const string& str, int pos = npos) const; //查找str最后一次位置,从pos开始查找
int rfind(const char* s, int pos = npos) const; //查找s最后一次出现位置,从pos开始查找
int rfind(const char* s, int pos, int n) const; //从pos查找s的前n个字符最后一次位置
int rfind(const char c, int pos=0)const; //查找字符C最后一次出现位置
string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str
string& replace(int pos, int n,const char* s); //替换从pos开始的n个字符为字符串s
6.string字符串比较
功能描述:
·字符串之间的比较
比较方式:
·字符串比较是按字符的ASCII码进行对比
=返回 0
>返回 1
<返回-1
函数原型:
int compare(const string &s) const; //与字符串s比较
int compare(const char *s) const; //与字符串s比较
7.string字符串存取
函数：
char& operator[](int n); //通过[]方式取字符
char& at(int n); //通过at()方式取字符
8.string插入和删除
功能描述:
·对string字符串进行插入和删除字符操作
函数原型:
string& insert(int pos, const char*s); //插入字符串
string& insert(int pos, const string& str); //插入字符串
string& insert(int pos, int n,char c); //在指定位置插入n个字符C
string& erase(int pos, int n= npos); //删除从Pos开始的n个字符
9.string子串
函数：
string substr(int pos = 0, int n= npos) const; //返回由pos开始的n个字符组成的字符串
1.3.2.2vector容器
1 vector基本概念
功能:
·vector数据结构和数组非常相似，也称为单端数组
vector与普通数组区别:
·不同之处在于数组是静态空间，而vector可以动态扩展
动态扩展:
·并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间
2 vector构造函数
功能描述：
• 创建vector容器
函数原型：
vector<T> v; //采用模板实现类实现，默认构造函数
vector(v.begin(), v.end()); //将v[begin(),end())区间中的元素拷贝给本身。
vector(n, elem); //构造函数将n个elem拷贝给本身。
vector(const vector &vec); //拷贝构造函数。
3 vector赋值操作
功能描述：
•给vector容器进行赋值
函数原型：
vector& operator=(const vector &vec)； //重载等号操作符
assign(beg,end); //将[beg,end)区间中的数据拷贝赋值给本身。
assign(n, elem); //将n个elem拷贝赋值给本身。
4 vector容量和大小
功能描述：
•对vector容器的容量和大小操作
函数原型： I
empty(); //判断容器是否为空
capacity(); //容器的容量
size(); //返回容器中元素的个数
resize(int num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
resize(int num,elem)； //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除
5 vector插入和删除
功能描述：
•对vector容器进行插入、删除操作
函数原型：
push_back(ele); //尾部插入元素ele
pop_back(); //删除最后一个元素
insert(const_iterator pos, ele); //迭代器指向位置pos插入元素ele
insert(const_iterator pos,int count,ele)； //迭代器指向位置pos插入count个元素eleerase(const_iterator pos); //删除迭代器指向的元素
erase(const_iterator start,const_iterator end)； //删除迭代器从start到end之间的元素clear(); //删除容器中所有元素
6 vector数据存取
功能描述：
•对vector中的数据的存取操作
函数原型：
at(iht idx); //返回索引idx所指的数据
operator[]; //返回索引idx所指的数据
front(); //返回容器中第一个数据元素
back(); //返回容器中最后一个数据元素
7 vector互换容器
功能描述：
•实现两个容器内元素进行互换
函数原型：
swap(vec)； //将vec与本身的元素互换
8 vector预留空间
功能描述：
·减少vector在动态扩展容量时的扩展次数
函数原型：
reserve(int len)；//容器预留len个元素长度，预留位置不初始化，元素不可访问。
1.3.2.3deque容器（daike）
1 deque容器基本概念
功能：
•双端数组，可以对头端进行插入删除操作
deque与vector区别：
•vector对于头部的插入删除效率低，数据量越大，效率越低
•deque相对而言，对头部的插入删除速度回比vector快
•vector访问元素时的速度会比deque快,这和两者内部实现有关
deque内部工作原理：
deque内部有个中控器维护每段缓冲区中的内容，缓冲区中存放真实数据中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间。
deque容器的迭代器也是支持随机访问的
函数原型: .
deque<T> deqT; //默认构造形式
deque(beg, nd); //构造函数将[beg, end)区间中的元素拷贝给本身。
deque(n, elem); //构造函数将n个elem拷贝给本身。
deque(const deque &deq); //拷贝构造函数
2 deque赋值操作
功能描述：
•给deque容器进行赋值
函数原型：
deque&roperator=(const deque&deq); //重载等号操作符
assign(beg,end); //将[beg，end)区间中的数据拷贝赋值给本身。
assign(n,elem); //将n个elem拷贝赋值给本身。
3 deque大小操作
功能描述：
•对deque容器的大小进行操作
函数原型：
deque.empty(); //判断容器是否为空
deque.size(); //返回容器中元素的个数
deque.resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。
//如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。
//如果容器变短，则末尾超出容器长度的元素被删除。
4 deque插入和删除
功能描述：
•向deque容器中插入和删除数据
函数原型：
两端插入操作：
push_back(elem); //在容器尾部添加一个数据
push_front(elem); //在容器头部插入一个数据
pop_back(); //删除容器最后一个数据
pop_front(); //删除容器第一个数据
指定位置操作：
insert(pos,elem); //在pos位置插入一个elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end)； //在pos位置插入[beg，end)区间的数据，无返回值。
clear(); //清空容器的所有数据erase(beg,end);//删除[beg，end)区间的数据，返回下一个数据的位置。
erase(pos); //删除pos位置的数据，返回下一个数据的位置。
5 deque数据存取
功能描述：
•对deque中的数据的存取操作
函数原型：
at(int idx); //返回索引idx所指的数据
operator[]; //返回索引idx所指的数据
front(); //返回容器中第一个数据元素
back(); //返回容器中最后一个数据元素
6 deque排序
功能描述：
•利用算法实现对deque容器进行
排序算法：
sort(iterator beg,iterator end) //对beg和end区间内元素进行排序
1.3.2.4stack 常用接口
功能描述：栈容器常用的对外接口
构造函数：
stack<T> stk; //stack采用模板类实现，stack对象的默认构造形式
stack(const stack &stk); //拷贝构造函数
赋值操作：
stack& operator=(const stack &stk); //重载等号操作符
数据存取：
push(elem); //向栈顶添加元素
pop(); /1从栈顶移除第一个元素
top(); //返回栈顶元素
大小操作：
empty(); //判断堆栈是否为空
size(); //返回栈的大小
1.3.2.5queue 常用接口
功能描述：栈容器常用的对外接口
构造函数：
queue<T> que; //queue采用模板类实现，queue对象的默认构造形式
queue(const queue &que); //拷贝构造函数
赋值操作： I
queue& operator=(const queue &que); //重载等号操作符
数据存取：
push(elem); //往队尾添加元素
pop()； /1从队头移除第一个元素
back(); //返回最后一个元素
front(); //返回第一个元素
大小操作：
empty(); //判断堆栈是否为空
size(); //返回栈的大小
1.3.2.6list容器
1 list基本概念
功能：将数据进行链式存储
链表(list)：是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的。
链表的组成：链表由一系列结点组成。
结点的组成：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
SLT中的链表是一个双向循环链表。
由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器。
list的优点:
采用动态存储分配，不会造成内存浪费和溢出
链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
list的缺点:
链表灵活，但是空间(指针域)和时间(遍历)额外耗费较大。
list有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。
总结：
STL中List和vector是两个最常用的容器，各有优缺点。
2 list构造函数
功能描述：
创建list容器
函数原型：
list<T> lst; //list采用采用模板类实现,对象的默认构造形式：
list(beg,end); //构造函数将[beg，end)区间中的元素拷贝给本身。//构造函数将n个elem拷贝给本身。
list(n,elem);
list(const list &lst); //拷贝构造函数。
总结：
list构造方式同其他几个STL常用容器，熟练掌握即可。
3 list赋值和交换
功能描述：
给list容器进行赋值，以及交换list容器。
函数原型：
assign(beg, end); //将[beg，end)区间中的数据拷贝赋值给本身。
assign(n, elem); //将n个elem拷贝赋值给本身。
list& operator=(const list &lst); //重载等号操作符
swap(lst); //将lst与本身的元素互换。
总结：
list赋值和交换能够灵活运用即可。
4 list大小操作
功能描述：
对list容器的大小进行操作。
函数原型：
size(); //返回容器中元素的个数
empty(); //判断容器是否为空
resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。//如果容器变短，则末尾超出容器长度的元素被删除。
resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。//如果容器变短，则末尾超出容器长度的元素被删除。
总结:
判断是否为空——empty
返回元素个数——size
重新指定个数——resize
5 list插入和删除
功能描述：
对list容器进行数据的插入和删除
函数原型：
push_back(elem)；//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除第一个元素
insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg，end)区间的数据，无返回值。
clear();//移除容器的所有数据
erase(beg,end);//删除[beg，end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
remove(elem);//删除容器中所有与elem值匹配的元素。
总结：
尾插——push_back
尾删——pop_back
头插——push_front
头删——pop_front
插入——insert
删除——erase
移除——remove
清空——clear
6 list数据存取
功能描述：
对list容器中数据进行存储。
函数原型：
front(); /返回第一个元素。
back(); //返回最后一个元素。
总结：
list容器中不可以通过[]或者at方式访问数据
返回第一个元素——front
返回最后一个元素——back
7 list反转和排序
功能描述：
将容器中的元素反转，以及将容器中的数据进行排序。
函数原型：
reverse();//反转链表
sort(); //链表排序
总结：
反转——reverse
排序——sort(成员函数)
1.3.2.7set/multiset容器
1 set基本概念
简介：
所有元素都会在插入时被自动排序。
本质：
set/multiset属于关联式容器，底层结构是用二叉树实现。
set和multiset区别：
set不允许容器中有重复的元素。
multiset允许容器中有重复的元素
2 set构建和赋值
功能描述：
创建set容器以及赋值。
构造：
set<T> st; //默认构造函数：
set(const set &st); //拷贝构造函数
赋值：
set& operator=(const set &st); //重载等号操作符
总结：
set容器插入数据时用insert
set容器插入的数据会自动排序
3 set大小和交换
功能描述：
统计set容器大小以及交换set容器。
函数原型：
sized； //返回容器中元素的数目
empty(); //判断容器是否为空
swap(st); //交换两个集合容器
总结：
统计大小——size
判断是否为空——empty
交换容器——swap
4 set插入和删除
功能描述：
set容器进行插入数据和删除数据
函数原型：
insert(elem); //在容器中插入元素。
clear(); //清除所有元素
erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。erase(beg, end); //删除区间[beg，end)的所有元素，返回下一个元素的迭代器。erase(elem); //删除容器中值为elem的元素。
总结：
插入——insert
删除——erase
清空——clear
5 set查找和统计
功能描述：
对set容器进行查找数据以及统计数据
函数原型：
find(key); //查找key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回set.end(;
count(key); 11统计key的元素个数
总结：
查找——find(返回的是迭代器)
统计——count(对于set,结果为0或者1)
6 set和multiset区别
学习目标：
掌握set和multiset的区别
区别：
set不可以插入重复数据，而multiset可以
set插入数据的同时会返回插入结果，表示插入是否成功
multiset不会检测数据，因此可以插入重复数据
总结：
如果不允许插入重复数据可以利用set
如果需要插入重复数据利用multiset
1.3.2.7.5pair
C++ STL 标准库提供了 pair 类模板，其专门用来将 2 个普通元素 first 和 second（可以是 C++ 基本数据类型、结构体、类自定的类型）创建成一个新元素 <first, second>。
pair将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一个结构体，主要的两个成员变量是first，second 因为是使用struct不是class，所以可以直接使用pair的成员变量。
pair以类模板的形式定义在 utility 头文件，并位于命名空间 std 中，在 C++ 11 标准之前，pair 类模板中提供了以下 3 种构造函数：
// 默认构造函数，即创建空的 pair 对象
pair();
// 直接使用 2 个元素初始化成 pair 对象
pair (const first_type& a, const second_type& b);
// 拷贝（复制）构造函数，即借助另一个 pair 对象，创建新的 pair 对象
template<class U, class V> pair (const pair<U,V>& pr);
在 C++ 11 标准中，在引入右值引用的基础上，pair 类模板中又增添了如下 2 个构造函数：
// 移动构造函数
template<class U, class V> pair (pair<U,V>&& pr);
// 使用右值引用参数，创建 pair 对象
template<class U, class V> pair (U&& a, V&& b);
成员变量：
first: 用于访问 pair 中的第一个元素。
second: 用于访问 pair 中的第二个元素。
比较运算符：
==, !=, <, <=, >, >=: 比较两个 pair 对象。按照字典序，先比 first ，然后比 second 。
交换函数：
swap(pair<T1, T2>& x, pair<T1, T2>& y): 用于交换两个 pair 对象的值。
make_pair 函数：
make_pair(T1&& x, T2&& y): 创建并返回一个 pair 对象，使用给定的参数初始化。
示例：
#include <iostream>
#include <utility>
int main() {
// 构造函数
std::pair<int, double> myPair(10, 3.14);
// 访问成员变量
std::cout << "第一个元素: " << myPair.first << std::endl;
std::cout << "第二个元素: " << myPair.second << std::endl;
// 比较运算符
std::pair<int, double> anotherPair(20, 6.28);
if (myPair == anotherPair) {
std::cout << "Pairs 相等。" << std::endl;
} else {
std::cout << "Pairs 不相等。" << std::endl;
}
// 交换函数
std::swap(myPair, anotherPair);
// make_pair 函数
auto newPair = std::make_pair(42, 7.0);
return 0;
}
通过tie获取pair元素值
在某些清况函数会以pair对象作为返回值时，可以直接通过std::tie进行接收。
std::pair<std::string, int> getPreson() {
return std::make_pair("Sven", 25);
}
int main(int argc, char **argv) {
std::string name;
int ages;
std::tie(name, ages) = getPreson();
std::cout << "name: " << name << ", ages: " << ages << std::endl;
return 0;
}
1.3.2.8map/multimap容器
1 map基本概念
简介：
map中所有元素都是pair
pair中第一个元素为key(键值)，起到索引作用，第二个元素为value(实值)
所有元素都会根据元素的键值自动排序
本质：
map/multimap属于关联式容器，底层结构是用二叉树实现。
优点：
可以根据key值快速找到value值
区别：
map和multimap区别
map不允许容器中有重复key值元素
multimap允许容器中有重复key值元素
3 map构造和赋值
功能描述：
对map容器进行构造和赋值操作。
函数原型：
构造：
map<T1,T2> mp; //map默认构造函数：
map(const map &mp); //拷贝构造函数
赋值：
map&operator=(const map &mp); //重载等号操作符
总结：
map中所有元素都是成对出现，插入数据时要使用对组。
4 map大小和交换
功能描述：
统计map容器大小以及交换map容器
函数原型：
size(); //返回容器中元素的数目
empty(); //判断容器是否为空
swap(st); //交换两个集合容器
总结：
统计大小——size
判断是否为空——empty
交换容器——swap
5 map插入和删除
功能描述:
map容器进行插入数据和删除数据
函数原型：
insert(elem); //在容器中插入元素。
clear(); //清除所有元素
erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end); //删除区间[beg，end)的所有元素，返回下一个元素的迭代器。
erase(key); //删除容器中值为key的元素。
总结：
map插入方式很多，记住其一即可
插入——insert
删除——erase
清空——clear
6 map查找和统计
功能描述：
对map容器进行查找和数据以及统计数据
函数原型：
find(key); //查找key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回set.end(;
count(key); //统计key的元素个数
总结：
查找——find(返回的是迭代器)
统计——cout(对于map,结果为0或1)
7 map容器排序
学习目标：
map容器默认排序规则为按照key值进行从小到大排序，掌握如何改变排序规则。
主要技术点：
利用仿函数，可以改变排序规则。
总结：
利用仿函数可以指定map容器的排序规则
对于自定义数据类型，map必须要指定排序规则，同set容器
1.3.2.9 优先队列Priority_queue
1.简介
优先队列是一种极其特殊的队列，他与标准的队列使用线性结构进行计算不同，优先队列的底层是以散列的状态（非线性）表现的，
它与标准的队列有如下的区别，标准的队列遵从严格的先进先出，优先队列并不遵从标准的先进先出，而是对每一个数据赋予一个权值，
根据当前队列权值的状态进行排序，使得权值最大（或最小）的永远排在队列的最前面。
2.头文件
属于队列的一种，直接使用队列的头文件 #include<queue>
3.优先队列的初始化
priority_queue<T, Container, Compare>
priority_queue<T> //直接输入元素则使用默认容器和比较函数
与往常的初始化不同，优先队列的初始化涉及到一组而外的变量，这里解释一下初始化：
a) T就是Type为数据类型
b) Container是容器类型（Container必须是用数组实现的容器，比如vector,deque，不能用 list，默认vector）
c) Compare是比较方法，类似于sort第三个参数那样的比较方式，对于自定义类型，需要我们手动进行比较运算符的重载。
与sort直接Bool一个函数来进行比较的简单方法不同，Compare需要使用结构体的运算符重载完成，直接
bool cmp(int a,int b){ return a>b; } 这么写是无法通过编译的。
举例：
struct cmp
{ //这个比较要用结构体表示
bool operator()(int &a, int &b) const
{
return a > b;
}
};
priority_queue<int,vector<int>,cmp> q; //使用自定义比较方法
priority_queue<int> pq;
4.常用接口
我们预先通过priority_queue <int> q创建了一个队列，命名为q，方便举例。
a)大小size()
返回队列元素的个数
函数原型：size_type size() const;
cout<<q.size()<<endl; //直接返回队列中元素的个数
b) 入队push()
进行入队操作，在队尾处进行插入
函数原型：void push (const value_type& val);
q.push(100);
c) 出队pop()
进行出队操作，在对头出进行弹出
函数原型：void pop();
q.pop();
d) 访问队头元素top()
与标准队列不同，优先队列只允许访问队头元素，不允许访问其余的数据，由于堆的特殊性质，堆顶元素的优先权最高（或者最低），
访问其余元素没有意义，因此，优先队列只允许访问队头元素，这和栈的访问类型类似所以使用栈访问栈顶的命名top
函数原型是：
reference& top();
const_reference& top() const;
cout<<q.top()<<endl;
e) 判空empty()
返回一个bool类型的值，只存在真和假，当队列为空时为真，不为空时为假
函数原型
bool empty() const;
可以利用empty()进行队列的遍历操作，这里建议先使用初始化函数将队列进行复制，否则遍历之后队列就为空了。
while(q.empty()){
cout<<q.pop()<<endl;
q.pop();
}
1.3.3STL函数对象（仿函数）
1 函数对象
1 函数对象概念
概念：
重载函数调用操作符的类，其对象也称为函数对象
函数对象使用重载()时，行为类似函数调用，也叫仿函数
本质：
函数对象(仿函数)是一个类，不是一个函数。
函数对象使用
特点：
函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值
函数对象超出普通函数的概念，函数对象可以有自己的状态
函数对象可以作为参数传递
2 谓词
2.1谓词概念
概念:
返回bool类型的仿函数称为谓词
如果operator()接受一个参数，那么叫做一元谓词
如果operator()接收两个参数，那么叫做二元谓词
2.2一元谓词
参数中只有一个的谓词，叫做一元谓词
2.3二元谓词
参数只有两个的谓词，称为二元谓词。
3内建函数对象
3.1内建函数对象意义
概念：
STL内建了一些函数对象
分类：
算数仿函数
关系仿函数
逻辑仿函数
用法：
这些仿函数所产生的对象，用法和一般函数完全相同
使用内建函数对象，需要引入头文件#include< functional>
3.2算数仿函数
功能描述：
实现四则运算
其中negate是一元运算，其它都是二元运算
仿函数原型：
使用内建函数对象时，需要引入头文件#include< functional>
3.3关系仿函数
功能描述：
实现关系对比
仿函数原型：
3.4逻辑仿函数
功能描述：
实现逻辑运算
函数原型:
2.数据结构与算法
线段树
线段树（Segment Tree）是一种用于高效处理区间查询的数据结构，特别适用于动态数组的问题。它允许在对数时间内进行区间查询、更新操作。
结构和构建
线段树是一棵平衡二叉树，其中每个叶子节点表示原始数组的一个元素，而每个非叶子节点表示一个区间。
节点结构：
每个节点包含一个区间 [start, end]，以及一些与该区间相关的信息（例如，区间和、最小值、最大值等）。
构建过程：
从树的根节点开始，递归地将每个区间分成两半，直到叶子节点表示单个元素。
在构建的过程中，为每个节点计算并存储相关的信息，例如区间和、最小值、最大值等。
查询操作通常涉及到一个给定的查询区间 [qlow, qhigh]，并需要找到该区间内的相关信息。
完全包含：
如果一个节点的区间完全包含在查询区间内，那么可以直接使用该节点存储的信息。
部分交叉：
如果一个节点的区间部分与查询区间相交，那么需要递归地查询该节点的左右子节点。
完全不交叉：
如果一个节点的区间完全不与查询区间相交，则无需进一步查询。
更新操作
更新操作通常涉及到修改数组中的某个元素，并相应地更新线段树中的节点信息。
找到叶子节点：
定位包含要更新元素的叶子节点。
更新路径上的节点：
从叶子节点向上更新，逐步更新路径上的节点的信息。
线段树常被用于解决需要频繁进行区间查询和更新的问题，例如：
区间和、最小值、最大值查询： 维护数组中的元素，支持区间和、最小值、最大值等查询。
区间更新： 对数组中的区间进行更新操作，如将一个区间内的元素全部加上一个值。
线段树的C++实现区间和查询和更新：
#include <iostream>
#include <vector>
using namespace std;
class SegmentTree {
private:
vector<int> tree;
int n;
void buildTree(const vector<int>& arr, int start, int end, int index) {
if (start == end) {
tree[index] = arr[start];
return;
}
int mid = (start + end) / 2;
buildTree(arr, start, mid, 2 * index + 1);
buildTree(arr, mid + 1, end, 2 * index + 2);
tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
}
int queryHelper(int qs, int qe, int start, int end, int index) {
if (qs <= start && qe >= end) {
return tree[index];
}
if (qe < start || qs > end) {
return 0;
}
int mid = (start + end) / 2;
return queryHelper(qs, qe, start, mid, 2 * index + 1) +
queryHelper(qs, qe, mid + 1, end, 2 * index + 2);
}
void updateHelper(int i, int diff, int start, int end, int index) {
if (i < start || i > end) {
return;
}
tree[index] += diff;
if (start != end) {
int mid = (start + end) / 2;
updateHelper(i, diff, start, mid, 2 * index + 1);
updateHelper(i, diff, mid + 1, end, 2 * index + 2);
}
}
public:
SegmentTree(const vector<int>& arr) {
n = arr.size();
int height = ceil(log2(n));
int treeSize = 2 * pow(2, height) - 1;
tree.resize(treeSize, 0);
buildTree(arr, 0, n - 1, 0);
}
int query(int qs, int qe) {
return queryHelper(qs, qe, 0, n - 1, 0);
}
void update(int i, int newVal) {
int diff = newVal - tree[i];
tree[i] = newVal;
updateHelper(i, diff, 0, n - 1, 0);
}
};
int main() {
vector<int> arr = {1, 3, 5, 7, 9, 11};
SegmentTree st(arr);
// 查询区间和
cout << "Sum of elements in range [1, 4]: " << st.query(1, 4) << endl;
// 更新元素
st.update(2, 6);
// 再次查询更新后的区间和
cout << "Sum of elements in range [1, 4]: " << st.query(1, 4) << endl;
return 0;
}
稀疏表
稀疏表（Sparse Table）是一种用于高效处理区间查询的数据结构。它主要用于解决静态数组的区间查询问题，其中数组的元素在查询过程中不会发生变化。
稀疏表的核心思想是通过预处理构建一个二维表，使得表中的每个元素保存一定范围内的原数组元素的信息。通常，稀疏表会选择保存每个范围内的最小值、最大值、和等信息，以便在查询区间时能够快速获取答案。
使用ST表（Sparse Table）解决可重复贡献问题：
可重复贡献问题指的是，对于一种运算opt，满足opt(x,x)=x，并且opt可以参与区间运算，满足 ∀l≤k≤r,opt [l,r]=opt(opt [l,k],opt [k,r])。之后给定任意区间[l,r]，求解opt [l,r]的问题。
我们特化一下这个定义，例如，最大值有max(x,x)=x ，gcd 有 gcd(x,x)=x ，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次，这是我们所不愿意看到的。另外，opt还必须满足结合律才能使用 ST 表求解。
构建稀疏表：
- 初始化： 将原数组的每个元素作为长度为1的区间的最小值和最大值，填充稀疏表的第一行（或第一列）。
- 逐步填表： 从第二行（或第二列）开始，对于每个区间长度为2的区域，使用上一行（或上一列）对应位置的信息填充当前位置，以此类推，直到填充整个表。
查询操作：对于一个给定的区间查询 [L, R]，稀疏表可以通过将该区间拆分成若干个不相交的区间来快速计算结果。例如，如果查询区间长度为8，可以将其拆分为两个长度为4的区间，然后通过查找稀疏表中相应位置的信息来得到最终结果。
应用场景：稀疏表广泛应用于解决静态数组的区间查询问题：
最小值查询： 查询一个区间内的最小值。
最大值查询： 查询一个区间内的最大值。
区间和查询： 查询一个区间内的元素和。
构建了一个保存最小值信息的稀疏表，并进行了一次最小值查询：
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1000; // 数组大小
const int LOGMAXN = 10; // log2(MAXN)的上限
int sparseTable[MAXN][LOGMAXN];
void buildSparseTable(const vector<int>& arr) {
int n = arr.size();
// 初始化第一行
for (int i = 0; i < n; i++) {
sparseTable[i][0] = arr[i];
}
// 逐步填表
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; i + (1 << j) - 1 < n; i++) {
sparseTable[i][j] = min(sparseTable[i][j - 1], sparseTable[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int l, int r) {
int len = r - l + 1;
int k = 0;
while ((1 << (k + 1)) <= len) {
k++;
}
return min(sparseTable[l][k], sparseTable[r - (1 << k) + 1][k]);
}
int main() {
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
buildSparseTable(arr);
// 查询区间[2, 5]的最小值
int result = query(2, 5);
cout << "Minimum value in range [2, 5]: " << result << endl;
return 0;
}
优先队列
优先队列（Priority Queue）是一种特殊的队列，其中每个元素都有一个相关的优先级。在优先队列中，元素按照优先级顺序排列，而不是按照插入的顺序。具有最高优先级的元素先出队列。
在优先队列中，元素的插入操作是无序的，但是每次出队列的元素都是具有最高优先级的元素。这种数据结构通常用堆（Heap）来实现，堆是一种特殊的二叉树结构。
应用场景
任务调度： 优先队列可以用于任务调度，确保高优先级的任务先执行。
图算法： 在一些图算法中，如Dijkstra算法，优先队列可以用来选择下一个要探索的节点。
模拟系统： 在模拟系统中，可以使用优先队列来模拟事件的发生顺序，确保按照优先级进行处理。
贪心算法： 一些贪心算法中，优先队列可以用于选择当前最优的步骤。
C++中，优先队列是通过 queue 头文件中的priority_queue类实现的。以下是一些常见的接口：
构造函数：
priority_queue<Type, vector<Type>, Comparison> pq;
Type：队列中元素的数据类型。
vector<Type>：底层容器类型，存储元素的容器。
Comparison：比较函数，用于确定元素之间的优先级。
插入元素：
pq.push(element);
访问队首元素：
top_element = pq.top();
删除队首元素：
pq.pop();
使用C++中的优先队列：
#include <iostream>
#include <queue>
using namespace std;
int main() {
// 声明一个最大堆（默认）
priority_queue<int> maxHeap;
// 插入元素
maxHeap.push(10);
maxHeap.push(30);
maxHeap.push(20);
// 访问队首元素
cout << "Top element: " << maxHeap.top() << endl;
// 删除队首元素
maxHeap.pop();
// 输出剩余元素
cout << "Remaining elements: ";
while (!maxHeap.empty()) {
cout << maxHeap.top() << " ";
maxHeap.pop();
}
return 0;
}
如果需要最小堆，则使用
priority_queue<int, vector<int>, greater<int>> minHeap;
练习：力扣239，优先队列解决
单调队列
单调队列（Monotonic Queue）是一种数据结构，用于解决一些特定问题，例如滑动窗口中的最大值或最小值。它的主要特点是队列中的元素保持特定的单调性（递增或递减），从而在队列中维护有用的信息。下面是关于单调队列的详细解释：
单调队列的基本思想：
- 维护队列的单调性： 在单调队列中，元素按照单调递增或单调递减的顺序排列。这有助于在队列中快速找到最大值或最小值。
- 保持有效信息： 队列中的每个元素都有其有效信息。在一些问题中，有效信息可能是元素的值，而在其他问题中，可能是与元素相关的其他属性。
单调队列的应用场景：
- 滑动窗口最值问题： 在一个大小为k的窗口中找到最大值或最小值。
- 优先级队列的替代： 单调队列可以在O(1)时间内找到队列中的最大值或最小值，而不需要维护一个完整的优先级队列。
- 一些动态规划问题： 在某些动态规划问题中，通过维护单调队列，可以以较低的时间复杂度解决问题。
单调队列的实现：
单调队列通常使用双端队列（Deque）实现。在每次push操作时，将队尾元素与当前元素比较，并删除队尾元素直到队列单调。在pop操作时，删除队头元素。
示例：
#include <iostream>
#include <deque>
#include <vector>
std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {
std::vector<int> result;
std::deque<int> dq;
for (int i = 0; i < nums.size(); ++i) {
// 维护单调递减队列
while (!dq.empty() && nums[i] > nums[dq.back()]) {
dq.pop_back();
}
dq.push_back(i);
// 移除超出窗口范围的元素
while (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
// 添加当前窗口的最大值到结果中
if (i >= k - 1) {
result.push_back(nums[dq.front()]);
}
}
return result;
}
int main() {
std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
std::vector<int> result = maxSlidingWindow(nums, k);
std::cout << "Max values in sliding window: ";
for (int val : result) {
std::cout << val << " ";
}
std::cout << std::endl;
return 0;
}
示例中的 maxSlidingWindow 函数使用了单调队列来找到滑动窗口中的最大值。通过维护单调递减队列，它在O(n)时间内解决了这个问题。
练习：力扣239，单调队列解决
回溯算法
回溯算法是一种通过逐步构建解决方案并在发现当前方案不可行时进行回溯的算法。在回溯过程中，算法尝试不同的选择，直到找到一个满足问题条件的解决方案或者遍历所有可能的选择。
原理：
选择： 在每一步，从候选的选择集合中选择一个元素。
路径： 将所选元素添加到当前路径中，构建部分解决方案。
条件： 检查路径是否满足问题的条件。
回溯： 如果当前路径不满足条件，撤销上一步的选择，回到之前的状态，尝试其他选择。
应用：
回溯算法通常用于解决组合问题、排列问题、子集问题、棋盘问题（如八皇后问题、数独问题）、图搜索等。
具体应用场景包括：
组合问题： 从给定的一组元素中找出所有可能的组合。
排列问题： 从给定的一组元素中找出所有可能的排列。
子集问题： 找出给定集合的所有子集。
棋盘问题： 在一个棋盘上放置一些元素，满足特定条件。
图搜索： 通过深度优先搜索实现图的遍历。
实现：
回溯算法的实现通常通过递归来完成，每一层递归对应问题的一个阶段。递归的基本结构如下：
void backtrack(参数) {
// 终止条件
if (满足问题条件) {
// 处理解决方案
return;
}
// 遍历选择集合
for (选择 in 选择集合) {
// 做选择
添加选择到路径中;
// 递归到下一层
backtrack(参数);
// 撤销选择
从路径中移除选择;
}
}
使用回溯算法生成一组数字的所有排列。在每一步，选择一个未使用的数字，添加到当前路径中，然后递归到下一层。当路径长度达到数组长度时，输出一个排列。这个过程不断重复，直到遍历所有可能的排列。回溯算法实现：
#include <iostream>
#include <vector>
void backtrack(std::vector<int>& nums, std::vector<int>& path, std::vector<bool>& used) {
// 终止条件
if (path.size() == nums.size()) {
// 处理解决方案
for (int num : path) {
std::cout << num << " ";
}
std::cout << std::endl;
return;
}
// 遍历选择集合
for (int i = 0; i < nums.size(); ++i) {
if (!used[i]) {
// 做选择
path.push_back(nums[i]);
used[i] = true;
// 递归到下一层
backtrack(nums, path, used);
// 撤销选择
path.pop_back();
used[i] = false;
}
}
}
void generatePermutations(std::vector<int>& nums) {
std::vector<int> path;
std::vector<bool> used(nums.size(), false);
backtrack(nums, path, used);
}
int main() {
std::vector<int> nums = {1, 2, 3};
generatePermutations(nums);
return 0;
}
回溯算法与深度优先遍历
维基百科中「回溯算法」和「深度优先遍历」的定义。
回溯法 采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
找到一个可能存在的正确的答案；
在尝试了所有可能的分步方法后宣告该问题没有答案。
深度优先搜索 算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会 尽可能深 的搜索树的分支。当结点 v 的所在边都己被探寻过，搜索将 回溯 到发现结点 v 的那条边的起始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被访问为止。
我刚开始学习「回溯算法」的时候觉得很抽象，一直不能理解为什么递归之后需要做和递归之前相同的逆向操作，在做了很多相关的问题以后，我发现其实「回溯算法」与「 深度优先遍历 」有着千丝万缕的联系。
个人理解
「回溯算法」与「深度优先遍历」都有「不撞南墙不回头」的意思。我个人的理解是：「回溯算法」强调了「深度优先遍历」思想的用途，用一个 不断变化 的变量，在尝试各种可能的过程中，搜索需要的结果。强调了 回退 操作对于搜索的合理性。而「深度优先遍历」强调一种遍历的思想，与之对应的遍历思想是「广度优先遍历」。至于广度优先遍历为什么没有成为强大的搜索算法，我们在题解后面会提。
在「力扣」第 51 题的题解《回溯算法（第 46 题 + 剪枝）》 中，展示了如何使用回溯算法搜索 444 皇后问题的一个解，相信对大家直观地理解「回溯算法」是有帮助。
搜索与遍历
我们每天使用的搜索引擎帮助我们在庞大的互联网上搜索信息。搜索引擎的「搜索」和「回溯搜索」算法里「搜索」的意思是一样的。
搜索问题的解，可以通过 遍历 实现。所以很多教程把「回溯算法」称为爆搜（暴力解法）。因此回溯算法用于 搜索一个问题的所有的解 ，通过深度优先遍历的思想实现。
与动态规划的区别
共同点
用于求解多阶段决策问题。多阶段决策问题即：
求解一个问题分为很多步骤（阶段）；
每一个步骤（阶段）可以有多种选择。
不同点
动态规划只需要求我们评估最优解是多少，最优解对应的具体解是什么并不要求。因此很适合应用于评估一个方案的效果；
回溯算法可以搜索得到所有的方案（当然包括最优解），但是本质上它是一种遍历算法，时间复杂度很高。
从全排列问题开始理解回溯算法
我们尝试在纸上写 333 个数字、444 个数字、555 个数字的全排列，相信不难找到这样的方法。以数组 [1, 2, 3] 的全排列为例。
先写以 111 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列（注意：递归结构体现在这里）；
再写以 222 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列；
最后写以 333 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。
总结搜索的方法：按顺序枚举每一位可能出现的情况，已经选择的数字在 当前 要选择的数字中不能出现。按照这种策略搜索就能够做到 不重不漏。这样的思路，可以用一个树形结构表示。
看到这里的朋友，建议先尝试自己画出「全排列」问题的树形结构。
说明：
每一个结点表示了求解全排列问题的不同的阶段，这些阶段通过变量的「不同的值」体现，这些变量的不同的值，称之为「状态」；
使用深度优先遍历有「回头」的过程，在「回头」以后， 状态变量需要设置成为和先前一样 ，因此在回到上一层结点的过程中，需要撤销上一次的选择，这个操作称之为「状态重置」；
深度优先遍历，借助系统栈空间，保存所需要的状态变量，在编码中只需要注意遍历到相应的结点的时候，状态变量的值是正确的，具体的做法是：往下走一层的时候，path 变量在尾部追加，而往回走的时候，需要撤销上一次的选择，也是在尾部操作，因此 path 变量是一个栈；
深度优先遍历通过「回溯」操作，实现了全局使用一份状态变量的效果。
使用编程的方法得到全排列，就是在这样的一个树形结构中完成 遍历，从树的根结点到叶子结点形成的路径就是其中一个全排列。
设计状态变量
首先这棵树除了根结点和叶子结点以外，每一个结点做的事情其实是一样的，即：在已经选择了一些数的前提下，在剩下的还没有选择的数中，依次选择一个数，这显然是一个 递归 结构；
递归的终止条件是： 一个排列中的数字已经选够了 ，因此我们需要一个变量来表示当前程序递归到第几层，我们把这个变量叫做 depth，或者命名为 index ，表示当前要确定的是某个全排列中下标为 index 的那个数是多少；
布尔数组 used，初始化的时候都为 false 表示这些数还没有被选择，当我们选定一个数的时候，就将这个数组的相应位置设置为 true ，这样在考虑下一个位置的时候，就能够以 O(1)O(1)O(1) 的时间复杂度判断这个数是否被选择过，这是一种「以空间换时间」的思想。
这些变量称为「状态变量」，它们表示了在求解一个问题的时候所处的阶段。需要根据问题的场景设计合适的状态变量。
代码实现
参考代码 1：
注意：下面的代码是错误的，希望读者能运行测试用例，发现原因，然后再阅读后面的内容。
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
// 使用一个动态数组保存所有可能的全排列
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
boolean[] used = new boolean[len];
List<Integer> path = new ArrayList<>();
dfs(nums, len, 0, path, used, res);
return res;
}
private void dfs(int[] nums, int len, int depth,
List<Integer> path, boolean[] used,
List<List<Integer>> res) {
if (depth == len) {
res.add(path);
return;
}
// 在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。
for (int i = 0; i < len; i++) {
if (!used[i]) {
path.add(nums[i]);
used[i] = true;
dfs(nums, len, depth + 1, path, used, res);
// 注意：下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
used[i] = false;
path.remove(path.size() - 1);
}
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
Solution solution = new Solution();
List<List<Integer>> lists = solution.permute(nums);
System.out.println(lists);
}
}
执行 main 方法以后输出如下：
[[], [], [], [], [], []]
原因出现在递归终止条件这里：
if (depth == len) {
res.add(path);
return;
}
变量 path 所指向的列表 在深度优先遍历的过程中只有一份 ，深度优先遍历完成以后，回到了根结点，成为空列表。
在 Java 中，参数传递是 值传递，对象类型变量在传参的过程中，复制的是变量的地址。这些地址被添加到 res 变量，但实际上指向的是同一块内存地址，因此我们会看到 666 个空的列表对象。解决的方法很简单，在 res.add(path); 这里做一次拷贝即可。
修改的部分：
if (depth == len) {
res.add(new ArrayList<>(path));
return;
}
此时再提交到「力扣」上就能得到通过了，完整代码请见下文「参考代码 2」。
复杂度分析：（初学回溯算法的时候可以暂时跳过。）
回溯算法由于其遍历的特点，时间复杂度一般都比较高，有些问题分析起来很复杂。一些回溯算法解决的问题，剪枝剪得好的话，复杂度会降得很低，因此分析最坏时间复杂度的意义也不是很大。但还是视情况而定。
时间复杂度：O(N×N!)O(N \times N!)O(N×N!)
非叶子结点的个数，依次为（按照层数来）：
1+AN1+AN2+⋯+ANN−1=1+N!(N−1)!+N!(N−2)!+⋯+N!
说明：根结点为 111，计算复杂度的时候忽略；AN1A_N^1AN1 表示排列数，计算公式为 Anm=n!(n−m)!A_n^m
在第 1 层，结点个数为 NNN 个数选 1 个的排列，故为 AN1
在第 2 层，结点个数为 NNN 个数选 2 个的排列，故为 AN2
N!(N−1)!+N!(N−2)!+⋯+N!=N!(1(N−1)!+1(N−2)!+⋯+1)≤N!(1+12+14+⋯+12N−1)<2N!
将常系数 222 视为 111，每个内部结点循环 NNN 次，故非叶子结点的时间复杂度为 O(N×N!)
最后一层共 N!N!N! 个叶节点，在叶子结点处拷贝需要 O(N)O(N)O(N)，叶子结点的时间复杂度也为 O(N×N!)
空间复杂度：O(N×N!)O(N \times N!)O(N×N!)。
递归树深度 logN\log NlogN；
全排列个数 N!N!N!，每个全排列占空间 NNN。取较大者。
理解回溯
从 [1, 2, 3] 到 [1, 3, 2] ，深度优先遍历是这样做的，从 [1, 2, 3] 回到 [1, 2] 的时候，需要撤销刚刚已经选择的数 3，因为在这一层只有一个数 3 我们已经尝试过了，因此程序回到上一层，需要撤销对 2 的选择，好让后面的程序知道，选择 3 了以后还能够选择 2。
执行深度优先遍历，从较深层的结点返回到较浅层结点的时候，需要做「状态重置」，即「回到过去」、「恢复现场」，我们举一个例子。
月光宝盒
只有撤销上一次的选择，重置现场，才能够回到 完全一样 的过去，再开始新的尝试才会是有效的。
《大话西游》里有这样的情节，至尊宝要对着「月光宝盒」喊一声「波若菠萝蜜」，时间就可以回到回去（所有的人物、事物都得一样，才能叫「回到过去」），他才能救人。这个道理其实和这里的「撤销选择」是一模一样的。
image.png
理解回溯比较困难的是理解「回到过去」，现实世界里我们无法回到过去，但是在算法的世界里可以。
通过打印输出观察
参考代码 2：
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Solution {
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
// 使用一个动态数组保存所有可能的全排列
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
boolean[] used = new boolean[len];
Deque<Integer> path = new ArrayDeque<>(len);
dfs(nums, len, 0, path, used, res);
return res;
}
private void dfs(int[] nums, int len, int depth,
Deque<Integer> path, boolean[] used,
List<List<Integer>> res) {
if (depth == len) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < len; i++) {
if (!used[i]) {
path.addLast(nums[i]);
used[i] = true;
System.out.println(" 递归之前 => " + path);
dfs(nums, len, depth + 1, path, used, res);
used[i] = false;
path.removeLast();
System.out.println("递归之后 => " + path);
}
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
Solution solution = new Solution();
List<List<Integer>> lists = solution.permute(nums);
System.out.println(lists);
}
}
控制台输出：
递归之前 => [1]
递归之前 => [1, 2]
递归之前 => [1, 2, 3]
递归之后 => [1, 2]
递归之后 => [1]
递归之前 => [1, 3]
递归之前 => [1, 3, 2]
递归之后 => [1, 3]
递归之后 => [1]
递归之后 => []
递归之前 => [2]
递归之前 => [2, 1]
递归之前 => [2, 1, 3]
递归之后 => [2, 1]
递归之后 => [2]
递归之前 => [2, 3]
递归之前 => [2, 3, 1]
递归之后 => [2, 3]
递归之后 => [2]
递归之后 => []
递归之前 => [3]
递归之前 => [3, 1]
递归之前 => [3, 1, 2]
递归之后 => [3, 1]
递归之后 => [3]
递归之前 => [3, 2]
递归之前 => [3, 2, 1]
递归之后 => [3, 2]
递归之后 => [3]
递归之后 => []
输出 => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
几点说明帮助理解「回溯算法」
每一次尝试都「复制」，则不需要回溯
如果在每一个 非叶子结点 分支的尝试，都创建 新的变量 表示状态，那么
在回到上一层结点的时候不需要「回溯」；
在递归终止的时候也不需要做拷贝。
这样的做法虽然可以得到解，但也会创建很多中间变量，这些中间变量很多时候是我们不需要的，会有一定空间和时间上的消耗。为了验证上面的说明，我们写如下代码进行实验：
参考代码 3：
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<Integer>> permute(int[] nums) {
// 首先是特判
int len = nums.length;
// 使用一个动态数组保存所有可能的全排列
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
boolean[] used = new boolean[len];
List<Integer> path = new ArrayList<>();
dfs(nums, len, 0, path, used, res);
return res;
}
private void dfs(int[] nums, int len, int depth,
List<Integer> path, boolean[] used,
List<List<Integer>> res) {
if (depth == len) {
// 3、不用拷贝，因为每一层传递下来的 path 变量都是新建的
res.add(path);
return;
}
for (int i = 0; i < len; i++) {
if (!used[i]) {
// 1、每一次尝试都创建新的变量表示当前的"状态"
List<Integer> newPath = new ArrayList<>(path);
newPath.add(nums[i]);
boolean[] newUsed = new boolean[len];
System.arraycopy(used, 0, newUsed, 0, len);
newUsed[i] = true;
dfs(nums, len, depth + 1, newPath, newUsed, res);
// 2、无需回溯
}
}
}
}
这就好比我们在实验室里做「对比实验」，每一个步骤的尝试都要保证使用的材料是一样的。我们有两种办法：
每做完一种尝试，都把实验材料恢复成做上一个实验之前的样子，只有这样做出的对比才有意义；
每一次尝试都使用同样的新的材料做实验。
在生活中做实验对材料有破坏性，这个过程通常不可逆。而在计算机的世界里，「恢复现场」和「回到过去」是相对容易的。
在一些字符串的搜索问题中，有时不需要回溯的原因是这样的：字符串变量在拼接的过程中会产生新的对象（针对 Java 和 Python 语言，其它语言我并不清楚）。如果您使用 Python 语言，会知道有这样一种语法：[1, 2, 3] + [4] 也是创建了一个新的列表对象，我们已经在「参考代码 2」中展示这种写法。
为什么不是广度优先遍历
首先是正确性，只有遍历状态空间，才能得到所有符合条件的解，这一点 BFS 和 DFS 其实都可以；
在深度优先遍历的时候，不同状态之间的切换很容易 ，可以再看一下上面有很多箭头的那张图，每两个状态之间的差别只有 111 处，因此回退非常方便，这样全局才能使用一份状态变量完成搜索；
如果使用广度优先遍历，从浅层转到深层，状态的变化就很大，此时我们不得不在每一个状态都新建变量去保存它，从性能来说是不划算的；
如果使用广度优先遍历就得使用队列，然后编写结点类。队列中需要存储每一步的状态信息，需要存储的数据很大，真正能用到的很少 。
使用深度优先遍历，直接使用了系统栈，系统栈帮助我们保存了每一个结点的状态信息。我们不用编写结点类，不必手动编写栈完成深度优先遍历。
不回溯可不可以
可以。搜索问题的状态空间一般很大，如果每一个状态都去创建新的变量，时间复杂度是 O(N)O(N)O(N)。在候选数比较多的时候，在非叶子结点上创建新的状态变量的性能消耗就很严重。
就本题而言，只需要叶子结点的那个状态，在叶子结点执行拷贝，时间复杂度是 O(N)O(N)O(N)。路径变量在深度优先遍历的时候，结点之间的转换只需要 O(1)O(1)O(1)。
最后，由于回溯算法的时间复杂度很高，因此在遍历的时候，如果能够提前知道这一条分支不能搜索到满意的结果，就可以提前结束，这一步操作称为 剪枝。
剪枝
回溯算法会应用「剪枝」技巧达到以加快搜索速度。有些时候，需要做一些预处理工作（例如排序）才能达到剪枝的目的。预处理工作虽然也消耗时间，但能够剪枝节约的时间更多；
提示：剪枝是一种技巧，通常需要根据不同问题场景采用不同的剪枝策略，需要在做题的过程中不断总结。
由于回溯问题本身时间复杂度就很高，所以能用空间换时间就尽量使用空间。
总结
做题的时候，建议 先画树形图 ，画图能帮助我们想清楚递归结构，想清楚如何剪枝。拿题目中的示例，想一想人是怎么做的，一般这样下来，这棵递归树都不难画出。
在画图的过程中思考清楚：
分支如何产生；
题目需要的解在哪里？是在叶子结点、还是在非叶子结点、还是在从跟结点到叶子结点的路径？
哪些搜索会产生不需要的解的？例如：产生重复是什么原因，如果在浅层就知道这个分支不能产生需要的结果，应该提前剪枝，剪枝的条件是什么，代码怎么写？
练习
下面提供一些我做过的「回溯」算法的问题，以便大家学习和理解「回溯」算法。
题型一：排列、组合、子集相关问题
提示：这部分练习可以帮助我们熟悉「回溯算法」的一些概念和通用的解题思路。解题的步骤是：先画图，再编码。去思考可以剪枝的条件， 为什么有的时候用 used 数组，有的时候设置搜索起点 begin 变量，理解状态变量设计的想法。
46. 全排列（中等）
47. 全排列 II（中等）：思考为什么造成了重复，如何在搜索之前就判断这一支会产生重复；
39. 组合总和（中等）
40. 组合总和 II（中等）
77. 组合（中等）
78. 子集（中等）
90. 子集 II（中等）：剪枝技巧同 47 题、39 题、40 题；
60. 第 k 个排列（中等）：利用了剪枝的思想，减去了大量枝叶，直接来到需要的叶子结点；
93. 复原 IP 地址（中等）
题型二：Flood Fill
提示：Flood 是「洪水」的意思，Flood Fill 直译是「泛洪填充」的意思，体现了洪水能够从一点开始，迅速填满当前位置附近的地势低的区域。类似的应用还有：PS 软件中的「点一下把这一片区域的颜色都替换掉」，扫雷游戏「点一下打开一大片没有雷的区域」。
下面这几个问题，思想不难，但是初学的时候代码很不容易写对，并且也很难调试。我们的建议是多写几遍，忘记了就再写一次，参考规范的编写实现（设置 visited 数组，设置方向数组，抽取私有方法），把代码写对。
733. 图像渲染（Flood Fill，中等）
200. 岛屿数量（中等）
130. 被围绕的区域（中等）
79. 单词搜索（中等）
说明：以上问题都不建议修改输入数据，设置 visited 数组是标准的做法。可能会遇到参数很多，是不是都可以写成成员变量的问题，面试中拿不准的记得问一下面试官
题型三：字符串中的回溯问题
提示：字符串的问题的特殊之处在于，字符串的拼接生成新对象，因此在这一类问题上没有显示「回溯」的过程，但是如果使用 StringBuilder 拼接字符串就另当别论。
在这里把它们单独作为一个题型，是希望朋友们能够注意到这个非常细节的地方。
17. 电话号码的字母组合（中等），题解；
784. 字母大小写全排列（中等）；
22. 括号生成（中等） ：这道题广度优先遍历也很好写，可以通过这个问题理解一下为什么回溯算法都是深度优先遍历，并且都用递归来写。
题型四：游戏问题
回溯算法是早期简单的人工智能，有些教程把回溯叫做暴力搜索，但回溯没有那么暴力，回溯是有方向地搜索。「力扣」上有一些简单的游戏类问题，解决它们有一定的难度，大家可以尝试一下。
51. N 皇后（困难）：其实就是全排列问题，注意设计清楚状态变量，在遍历的时候需要记住一些信息，空间换时间；
37. 解数独（困难）：思路同「N 皇后问题」；
488. 祖玛游戏（困难）
529. 扫雷游戏（困难）
链接：https://leetcode.cn/problems/permutations/solutions/9914/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
力扣刷题链接地址：https://github.com/StuBoo3i/LeetCode
3.操作系统
4.计算机网络
5.数据库
6.补充
C++位运算
按位与（&）：
用法：a & b
将a和b的对应二进制位进行与操作，结果中的每个位都是a和b对应位的逻辑与。
按位或（|）：
用法：a | b
将a和b的对应二进制位进行或操作，结果中的每个位都是a和b对应位的逻辑或。
按位异或（^）：
用法：a ^ b
将a和b的对应二进制位进行异或操作，结果中的每个位都是a和b对应位的逻辑异或。
按位取反（~）：
用法：~a
对a的每个位进行取反操作，即0变为1，1变为0。
左移（<<）：
用法：a << b
将a的二进制表示向左移动b位，相当于将a乘以2的b次方。
右移（>>）：
用法：a >> b
将a的二进制表示向右移动b位，相当于将a除以2的b次方。
C++算法
int count = gcd(k, n);求k和n的最大公约数。
swap(a,b);交换a和b
lower_bound 是 C++ STL 中的一个算法，用于在已排序的容器（例如，vector、set、map）中查找第一个不小于某个值的元素的位置。
函数签名如下：
template <class ForwardIt, class T>
ForwardIt lower_bound (ForwardIt first, ForwardIt last, const T& val);
其中 first 和 last 是表示范围的迭代器，val 是要查找的值。函数返回一个迭代器，指向在范围 [first, last) 中的第一个不小于 val 的元素位置。
以下是一个简单的示例：
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {1, 2, 4, 4, 5, 7, 8};
int target = 6;
auto it = std::lower_bound(vec.begin(), vec.end(), target);
if (it != vec.end()) {
std::cout << "First element not less than " << target << " is: " << *it << std::endl;
} else {
std::cout << "No element not less than " << target << " found in the vector." << std::endl;
}
return 0;
}
例中，lower_bound 查找第一个不小于 target 的元素，并输出结果。在给定的已排序容器中，lower_bound 可以高效地找到某个值的插入位置