《算法笔记》学习笔记

本文最后更新于 2025年12月2日下午

第2章 C/C++快速入门

2.1 基本数据类型

2.1.2 变量类型

long long类型赋大于$2^{31}-1$的初值，需要在初值后面加LL，否则会CE

long long bignum = 1234567890123456LL;

简而言之，题目要求$10^{9}$以内，就用int；$10^{18}$以内，就用longlong

浮点型：不要用float，只用double就可以了

char：小写字母比大写字母的ASCII值大32

字符常量必须用单引号标注，以区分是作为字符变量还是字符常量

转义字符

\n 代表换行
\0 代表空字符NULL，其ASCII码为0

字符串常量：由双引号标记的字符集，可以作为初值赋值给字符数组并使用%s的形式输出

不能把字符串常量赋值给字符变量

char c="abcd"

的写法是不允许的

布尔型

只有0才是False，别的整数都是True

2.1.3 强制类型转换

(新类型名)变量名

如果把一个类型的变量赋值给另一个类型的变量却没有写强转，那么IDE会自动强转

但是计算的时候需要强转，那就不能等到算完再强转

2.1.4 符号常量和const常量

格式为

#define 标识符 常量

或者

const 数据类型 变量名 = 常量;

常量的值一旦确定之后就不能改变了。

define除了定义常量以外，还可以定义任何语句或者片段（宏定义），格式如下

#define 标识符 任何语句或者片段

比如

#include<stdio.h>
#define ADD(a,b) ((a)+(b)) //为什么要加这么多括号？是因为宏定义是直接将对应的部分替换，然后才进行编译和运行
int main(){
    int num1 =3, num2 =5;
    prints("%d", ADD(num1,num2)); //8
    return 0;
}

所以，尽量不要用宏定义来做除了定义常量以外的事情

2.1.5 运算符

只复习位运算符详见Oiwiki

2.2 顺序结构

常见数据类型变量的scanf格式符

数据类型	格式符
int	%d
long long	%lld
float	%f
double	%lf
char	%c
字符串(char数组)	%s

录入字符串不需要加&

另外，如果要输入“3 4”这种用空格隔开的两个数字，两个%d直接可以不加空格

int a, b;
scanf("%d%d", &a, &b);

原因：除了%c以外，scanf对于其他格式符(如%d)的输入是以空白符（空格、tab）座位结束判断标志的
另外，字符数组使用%s读入的时候以空格和换行座位读入结束的标识
即scanf的%c格式是可以读入空格和换行的！

常见数据类型变量的printf格式符

数据类型	格式符
int	%d
long long	%lld
float	%f
double	%f
char	%c
字符串(char数组)	%s

与scanf的区别只在于double

三种实用的输出格式

%md
%md可以使不足m位的int型变量以m位进行右对齐输出，其中高位用空格补齐，如果变量本身超过m位则保持原样（不会截断）

#include <bits/stdc++.h>
using namespace std;   
int main()
{
    int a=123, b=1234567;
    printf("%5d\n",a);
    printf("%5d\n",b);
    return 0;
}

输出格式

  123
1234567

在123的前面补了两个空格
2. %0md 补上前导0

#include <bits/stdc++.h>
using namespace std;   
int main()
{
    int a=123, b=1234567;
    printf("%05d\n",a);
    printf("%05d\n",b);
    return 0;
}

输出格式

00123
1234567

%.mf 保留m位小数输出（不等价于四舍五入）

2.2.3 使用getchar和putchar来输入/输出字符

getchar用来输入单个字符，putchar用来输出单个字符，在某些scanf函数使用不便的场合可以使用 getchar 来输入字符。

#include <stdio.h>
int main(){
char cl，c2，c3;
c1 =getchar();
getchar();
c2 =getchar();
c3 = getchar();
putchar(c1);
putchar(c2);putchar(c3);
return 0
}

输入数据

abcd

输出结果

acd

此处第一个字符'a'被c1接收;第二个字符'b'虽然被接收，但是没有将它存储在某个变量中;第三个字符c被 c2 接收;第四个字符'd"被 c3 接收。之后，连续三次 putchar 将把 c1、c2、c3 连续输出。而如果输入"ab"，然后按Enter键，再输入c，再按Enter键，输出结果会是这样:

a
c

这是因为 getchar 可以识别换行符，所以 c2实际上储存的是换行符\n，因此在a和c之间会有一个换行出现。

2.2.4注释

2.2.5 typedef

可以给复杂的数据类型取一个别名

#include <cstdio>
Ltypedef long long LL;//给1ong 1ong起个别名
int main(){
LL a=123456789012345，b=234567890123456;//直接使用 LL
printf("lld\n"，a+b);
return 0;
}

2.2.6 常用math函数

fabs(double x)
用于对double型变量取绝对值
floor(double x) ceil(double x)
pow(double r, double p)
返回$r^{p}$
sqrt(double x)
log(double x)
返回lnx
C语言中不能指定底数，因此必须通过换底公式来求。
sin(double x) cso(double x) tan(double x)
要求参数是弧度制
asin(double x) acos(double x) atan(double x)
反三角函数
round(double x)
将double型变量四舍五入，返回值仍然是double类型

2.3 选择结构

2.3.1 if语句

2.3.3 switch语句

记得什么是break穿透

2.4 循环结构

2.4.1 while语句

2.4.2 do...while语句

#include <iostream>

int main() {
    int sum = 0;
    int i = 1;

    do {
        sum += i;
        i++;
    } while (i <= 100);

    std::cout << "The sum of numbers from 1 to 100 is: " << sum << std::endl;

    return 0;
}

do...while会先执行循环体一次，再去判断循环条件是不是为真

2.4.3 for语句

引用for (int x : s) 是 C++11 引入的一种范围-based for 循环（range-based for loop）语法。它的作...

for (int x : s) 是 C++11 引入的一种范围-based for 循环（range-based for loop）语法。它的作用是遍历容器 s 中的每一个元素，并将每个元素赋值给变量 x，然后在循环体中处理 x。

语法解析
for (int x : s) {
 // 循环体
}
int x：定义一个变量 x，用于存储容器 s 中的每个元素。x 的类型应与容器 s 中元素的类型一致。

s：一个可迭代的容器（如 std::vector、std::set、std::list 等）。

:：表示遍历容器 s 中的每个元素。

{}：循环体，对每个元素 x 执行的操作。

与传统 for 循环的对比

传统 for 循环
for (auto it = s.begin(); it != s.end(); ++it) {
    int x = *it;
    // 循环体
}
范围-based for 循环
for (int x : s) {
    // 循环体
}
范围-based for 循环的优点是：

简洁：不需要手动管理迭代器。

易读：直接表达“遍历容器中的每个元素”的意图。

安全：避免迭代器越界或错误。

示例：遍历 std::set
#include <iostream>
#include <set>

int main() {
    std::set<int> s = {10, 20, 30};

    for (int x : s) {
        std::cout << x << " "; // 输出 10 20 30
    }

    return 0;
}
注意事项
元素类型匹配：
x 的类型必须与容器 s 中元素的类型一致。如果不确定类型，可以使用 auto：
for (auto x : s) {
    // 循环体
}
避免拷贝：
如果容器中的元素是复杂类型（如 std::string 或自定义类），直接使用 for (auto x : s) 会导致元素的拷贝。为了避免拷贝，可以使用引用：
for (const auto& x : s) {
    // 循环体
}
修改元素：
如果需要修改容器中的元素，可以使用非 const 引用：
for (auto& x : s) {
    x = x * 2; // 修改元素
}

2.4.4 break和continue语句

2.5 数组

2.5.1 一维数组

记得初赋值，有两种赋值为0的方法：把第一个元素赋为0，或者只用一个大括号表示

int a[10]={0};
int a[10]={};

递推：

for(int i=1;i<10;i++){
    a[0] =1;
    a[1] =1;
    a[i+1]=a[i]+a[i-1];
} //斐波那契数列

2.5.2 冒泡排序

for (int j = 0; j < len - 1; j++){      //长度为n的数组，只需要执行这样的排序循环n-1次
    for (int i = 0; i < len - 1 - j; i++){
            int temp = arr[i];
            if (arr[i] > arr[i + 1]){
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
    }

别忘记交换两个数的固定写法

2.5.3 二维数组

初始化的方式

int a[5][6] = {{}}; //默认全部赋值0

如果数组大小较大（大概$10^{6}$级别），则需要定义在main函数外面

2.5.4 memset——对数组中每一个元素赋相同的值

格式为

memset(数组名, 值, sizeof(数组名))；

只建议使用memset赋值0或者-1，因为memset是对每个字节赋同样的值。如果要赋值其他数字，用fill函数。

2.5.5 字符数组

字符数组的初始化

除了赋值的时候一个一个赋值

char str[3] = {'a', 'b','\0'};

也可以通过直接赋值字符串来初始化仅限于初始化，程序其他位置不允许这样直接赋值整个字符串

char str[15] = "Good Day!";

字符数组的输入输出

scanf输入 printf输出
%s识别空格作为字符串的结尾
getchar输入，putchar输出

代码CPP · 19 行

#include <bits/stdc++.h>
using namespace std;   
int main()
{
    char str[5][5];
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            str[i][j]=getchar();
            getchar(); //这句是为了把输入中每行末尾的换行符吸收掉
        }
    }
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            putchar(str[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

这段代码就是一个二维数组的示例，输入什么就输出什么。
3. gets输入，puts输出
在C11之后被弃用
现在想要读取一行字符串可以使用while c!=\n或者getline

字符数组的存放方式

结尾是一个'\0 只有char型数组要注意，千万要注意长度要比实际存储字符串的长度至少多1

2.5.6 string.h头文件

strlen()，得到字符数组中第一个\0前字符的个数
strcmp(), 返回两个字符串大小的比较结果，比较原则是按照字典序
引用在 C++ 中，字符串的字典序比较是基于字符的 ASCII 值逐字符进行的。字典序比较的规则类似于英语词典中单词的排序规则。以下是字符串字典序比...
在 C++ 中，字符串的字典序比较是基于字符的 ASCII 值逐字符进行的。字典序比较的规则类似于英语词典中单词的排序规则。以下是字符串字典序比较的详细说明：

1. 字典序比较规则
1. 逐字符比较：
  - 从字符串的第一个字符开始，逐个比较对应位置的字符。
  - 如果两个字符的 ASCII 值不同，则 ASCII 值较小的字符所在的字符串较小。
2. 长度比较：
  - 如果两个字符串的前缀完全相同，但一个字符串比另一个字符串长，则较短的字符串较小。
2. 示例说明

示例 1
- 字符串 "apple" 和 "banana"：
  - 比较第一个字符：'a'（ASCII 97）和 'b'（ASCII 98）。
  - 因为 'a' < 'b'，所以 "apple" < "banana"。
示例 2
- 字符串 "apple" 和 "apricot"：
  - 前两个字符相同（'a' 和 'p'）。
  - 比较第三个字符：'p'（ASCII 112）和 'r'（ASCII 114）。
  - 因为 'p' < 'r'，所以 "apple" < "apricot"。
示例 3
- 字符串 "apple" 和 "app"：
  - 前三个字符相同（'a'、'p'、'p'）。
  - "app" 比 "apple" 短，所以 "app" < "apple"。
3. C++ 中的字符串比较

在 C++ 中，字符串的比较可以通过以下方式实现：
1. 使用比较运算符：
  - ==：判断两个字符串是否相等。
  - !=：判断两个字符串是否不相等。
  - <：判断第一个字符串是否小于第二个字符串。
  - >：判断第一个字符串是否大于第二个字符串。
  - <=：判断第一个字符串是否小于或等于第二个字符串。
  - >=：判断第一个字符串是否大于或等于第二个字符串。
2. 示例代码：
  代码CPP · 18 行
  #include <iostream> #include <string> using namespace std; int main() { string s1 = "apple"; string s2 = "banana"; if (s1 < s2) { cout << s1 << " is less than " << s2 << endl; } else if (s1 > s2) { cout << s1 << " is greater than " << s2 << endl; } else { cout << s1 << " is equal to " << s2 << endl; } return 0; }
输出
```
apple is less than banana
```
4. 字典序的应用

字典序比较在以下场景中非常有用：
1. 字符串排序：
  - 例如，对一组单词按字典序排序。
  - 示例：
    vector<string> words = {"banana", "apple", "apricot"}; sort(words.begin(), words.end()); // 排序后：["apple", "apricot", "banana"]
2. 拼数问题：
  - 在拼数问题中，通过比较字符串拼接后的字典序，可以找到最大的拼接结果。
3. 查找最小或最大字符串：
  - 例如，在一组字符串中找到字典序最小或最大的字符串。
5. 注意事项
1. 大小写敏感：
  - 字典序比较是大小写敏感的。例如，'A'（ASCII 65）和 'a'（ASCII 97）是不同的字符。
  - 如果需要忽略大小写，可以先将字符串转换为统一的大小写形式。
2. 数字字符串的比较：
  - 对于数字字符串（如 "123" 和 "45"），字典序比较可能不符合数值大小的比较结果。
  - 例如，"123" < "45"（因为 '1' < '4'），但数值上 123 > 45。
6. 总结
- 字符串的字典序比较是基于字符的 ASCII 值逐字符进行的。
- 如果两个字符串的前缀相同，较短的字符串较小。
- 在 C++ 中，可以直接使用比较运算符（如 <、>）来比较字符串的字典序。
- 字典序比较在字符串排序、拼数问题等场景中非常有用。
如果你有其他问题，欢迎继续提问！
strcpy()

strcpy(字符数组1， 字符数组2);

注意：是把字符数组2赋值给字符数组1，这里的复制也包括了\0

strcat()

strcat(字符数组1， 字符数组2);

注意：是把字符数组2接到字符数组1后面去

2.5.7 sscanf与sprintf

sscanf从单词上可以理解为 string+scanf,sprintf则可以理解为 string+printf,均在 stdio.h 头文件下。
先来回顾一下scanf与printf，其实可以写成这种形式

scanf(screen, "%d", &n);
printf(screen, "%d", n);

可以发现，scanf的输入其实是把 screen的内容以"%d"的格式传输到n中(即从左至右)
而 printf的输出则是把n以"%d"的格式传输到screen上(即从右至左)。 sscanf与sprintf与上面的格式是相同的，只不过把 screen 换成了字符数组
(假设定义了一个char 数组 str[100])，如下所示:

sscanf(str, "%d", &n);
sprintf(str, "%d", n);

上面sscanf写法的作用是把字符数组str中的内容以"%d"的格式写到n中(还是从左至右)
而sprintf写法的作用是把n以"%d"的格式写到str 字符数组中(还是从右至左)。示例如下

#include <bits/stdc++.h>
using namespace std;   
int main()
{
    int n=233;
    char str[100];
    sprintf(str,"%d", n);
    printf("%s\n", str);
    return 0;
}

输出结果

上面只是一些简单的应用，事实上，可以像使用scanf与printf那样进行复杂的格式输入和输出。例如下面的代码使用sscanf将字符数组str中的内容按"%d:%lf,%s"的格式写到int型变量n、double型变量db、char型数组str2中。

#include <bits/stdc++.h>
using namespace std;   
int main()
{
    int n;
    double db;
    char str[1000] = "2048:3.14,hello", str2[100];
    sscanf(str, "%d:%lf,%s",&n, &db, str2);
    printf("n=%d,db=%.2f,str2=%s\n",n,db,str2);
    return 0;
}

输出结果为

n=2048,db=3.14,str2=hello

类似的

#include <bits/stdc++.h>
using namespace std;   
int main()
{
    int n=12;
    double db=3.1415;
    char str[1000], str2[100]="good";
    sprintf(str, "%d:%.2f,%s",n, db, str2);
    printf("str=%s\n",str);
    return 0;
}

输出结果

str=12:3.14,good

2.6 函数

2.6.1 函数的定义

全局变量：定义在所有函数之前，对于定义之后的所有程序段之内都有效的变量
局部变量：定义在函数内部且只在函数内部生效，函数结束之后局部变量销毁
函数定义内的小括号内的参数被称为形式参数简称形参，而在实际调用时小括号之内的参数称为实际参数或者实参

2.6.2 再谈main函数

return 0；是告知系统，程序正常终止

2.6.3 以数组作为函数参数

数组作为参数时，数组中的第一维不需要填写长度（如果是二维数组，那么第二维需要填写长度），实际调用时也只需要填写数组名。
数组作为参数时，在函数中对数组元素的修改就等同是对原数组元素的修改（这与普通的局部变量不同） 比如

void change(int b[][5]){ //第二维要注明长度

}

数组可以作为参数传入，但是不能作为返回类型。

2.6.4 函数的嵌套调用

2.6.5 函数的递归调用

递归是函数自己调用自身的过程，会在第四章详细介绍

#include <bits/stdc++.h>
using namespace std;   

int F(int n){
    if(n==0) return 1;
    else return F(n-1)*n;
}
int main()
{
    int n=12;
    cin>>n;
    return 0;
}

2.7 指针

指针是一个unsigned类型的int

2.7.2 指针变量

指针变量用来存放指针（或者可以理解成地址），意思是把地址当做常量，然后专门定义了一种指针变量来存放它，在某种数据类型后加型号*来表示这是一个指针变量

如果要同时定义几个指针变量，星号只会结合于第一个变量名

int* p1, p2; //p1是int*类型的 p2是int类型的

一种给指针变量赋值的方式，给指针变量赋值的方式一般是把变量的地址取出来(使用取地址运算符&)，然后赋值给对应的指针变量：

int a;
int *p = &a;

或者

int a;
int *p;
p = &a;

地址&a是赋值给p的而不是赋值给*p的，需要铭记星号是类型的一部分

对于一个指针变量，它的解引用也是使用星号*，比如如下的代码

int main(){
    int a;
    int *p=&a;
    a=233;
    printf("%d",*p); //输出233
}

上述代码中首先定义int型变量a，但是没有初始化。然后定义指针变量p，并将a的地址赋值给p。这时p存放了a的地址。之后a被赋值为233，也就是说a所在地址的房间内的内容被改变了，但是这不影响它的地址。而在后面的输出中使用星号*作为开启房间的钥匙，放在了p的前面，这样*p就能获取到房间里的东西，即储存的数据。

由此可以延伸到，既然p保存的是地址，*p是这个地址存放的元素，那么直接对*进行赋值也可以起到改变保存的元素的功能

int main(){
    int a;
    int *p=&a;
    *p=233;
    printf("%d",a); //输出233
}

指针变量可以进行加减法，对int*型变量p来说，p+1是p所指的int变量的下一个int型变量地址

2.7.3 指针与数组

数组名称可以作为数组的首地址使用 即定义int arr[], 则有a==&a[0];
且有*a+i==&a[i], (a+i)==a[i]; 两个int类型的指针相减，等价于求这两个指针之间相差了几个int，比如下面这段代码

int a[5];
int *p=a;
int *q=a+5;
cout<<q-p;

会输出5，这个解释对于其他类型的指针同样适用

2.7.4 使用指针变量作为函数参数

这时视为把变量的地址传入函数，如果在函数中对这个地址的元素进行改变，那么原先的数据就确实地会被改变。
经典例子，使用指针作为参数交换两个数。

void _swap(int *a, int *b){
    int temp=*a; 
    *a=*b;
    *b=temp;
}

经典错误1

void _swap(int *a, int *b){
    int *temp; 
    *temp=*a;
    *a=*b;
}

错因：指针temp没有初始化，是野指针，很大可能指向系统工作区间，随机地址出错概率特别大。

解决方案：

void _swap(int *a, int *b){
    int x;
    int *temp=&x; 
    *temp=*a;
    *a=*b;
}

经典错误2

void _swap(int *a, int *b){
    int *temp=a;
    a=b;
    b=temp;
}

错因：回顾前面所说的，函数参数的传送方式是单向一次性的，main函数传给swap函数的“地址”其实只是一个unsigned int，swap对地址本身修改并不能对main函数里面的地址进行修改，能够使main函数里面的数据发生变化的只能是swap函数中对地址指向的数据进行的修改。这个函数其实就很类似于为什么不可以写一个这样的函数

void _swap(int a, int b){
    int temp=a; 
    a=b;
    b=temp;
}

因为其实都只是副本罢了。

2.7.5 引用

引用的含义

C++中特有的语法，给原变量起一个别名，且对引用变量的操作就是对于原变量的操作 引用不产生副本
方法：在函数的参数类型后面加一个&就可以了
注意与取地址运算符的&区分开

#include <bits/stdc++.h>
using namespace std;   

void change(int&x){
    x=2;
}
int main()
{
    int n=1;
    change(n);
    cout<<n;
}

指针的引用

可以运用引用，改造上面的经典错误2

void _swap(int* &p1, int* &p2){
    int *temp=p1;
    p1=p2;
    p2=temp;
}

这里相当于把int*视作一个unsigned int类型，而对这样的两个整型变量进行交换是需要加引用的
传入的是指针的别名。
常量不可以使用引用

引用在C++中，引用（Reference）是一种特殊的变量类型，它为另一个变量提供了一个别名。引用本身并不占用额外的内存空间，它只是指向另一个变量的...

在C++中，引用（Reference）是一种特殊的变量类型，它为另一个变量提供了一个别名。引用本身并不占用额外的内存空间，它只是指向另一个变量的内存地址。通过引用，你可以直接操作被引用的变量，而不需要通过指针来间接访问。

引用的声明语法如下：
类型 &引用名 = 变量名;
类型：被引用变量的类型。

引用名：引用的名称，用于后续操作。

变量名：被引用的变量的名称。

示例：
#include <iostream>

int main() {
    int a = 10;  // 定义一个整型变量a
    int &ref = a;  // 定义一个引用ref，它指向变量a

    std::cout << "a = " << a << std::endl;  // 输出: a = 10
    std::cout << "ref = " << ref << std::endl;  // 输出: ref = 10

    ref = 20;  // 通过引用修改a的值

    std::cout << "a = " << a << std::endl;  // 输出: a = 20
    std::cout << "ref = " << ref << std::endl;  // 输出: ref = 20

    return 0;
}
关键点：
初始化：引用必须在声明时进行初始化，并且一旦初始化后，就不能再引用其他变量。
int a = 10;
int &ref = a;  // 正确
int &ref2;  // 错误，引用必须初始化
别名：引用实际上是变量的别名，对引用的操作就是对原变量的操作。
int a = 10;
int &ref = a;
ref = 20;  // 等同于 a = 20;
不能为空：引用不能为空，它必须始终引用某个有效的对象。
int &ref = nullptr;  // 错误，引用不能为空
常量引用：你可以声明一个常量引用，这样引用就不能修改被引用的变量。
int a = 10;
const int &ref = a;  // 常量引用
ref = 20;  // 错误，常量引用不能修改被引用的变量
引用作为函数参数：引用常用于函数参数传递，以避免拷贝大对象，并且可以直接修改传入的参数。
void increment(int &value) {
    value++;
}
                                                                                                                                                                                                                                                                                    
int main() {
    int a = 10;
    increment(a);
    std::cout << a << std::endl;  // 输出: 11
    return 0;
}
总结：

引用在C++中是一个非常强大的工具，它允许你以更直观的方式操作变量，避免了指针的复杂性。通过引用，你可以直接修改被引用的变量，而不需要通过指针来间接访问。引用在函数参数传递、返回值等方面都有广泛的应用。

2.8 结构体的使用

2.8.1 结构体的定义

一个例子

typedef struct
{
    char name;
    int count;
}spot;

定义结构体变量的方式

typedef struct
{
    char name;
    int count;
}spot;
spot A;
spot B;
spot str[100];

或者

struct spot
{
    char name;
    int count;
}A, B, str[100];

结构体里面不能定义自己本身，但是可以定义自身类型的指针变量
一个例子

代码CPP · 40 行

#include <iostream>

// 定义一个链表节点结构体
struct Node {
 int data;           // 节点数据
 Node* next;         // 指向下一个节点的指针
};

int main() {
 // 创建链表节点
 Node* head = new Node();
 head->data = 1;
 head->next = nullptr;

 Node* second = new Node();
 second->data = 2;
 second->next = nullptr;

 Node* third = new Node();
 third->data = 3;
 third->next = nullptr;

 // 将节点连接起来
 head->next = second;
 second->next = third;

 // 遍历链表并输出数据
 Node* current = head;
 while (current != nullptr) {
     std::cout << current->data << " ";
     current = current->next;
 }

 // 释放链表内存
 delete head;
 delete second;
 delete third;

 return 0;
}

2.8.2 访问结构体内的元素

两种方法

struct StudentInfo{
    int id;
    char name[20];
    studentInto *next;
}stu, *p;

访问变量写法

stu.id
stu.name
stu.next

而访问指针变量p

(*p).id //先解引用为一个struct变量
(*p).name
(*p).next

另一种写法

p->id
p->name
p->next

赋值的写法

stu.id = 10086;
int getID = stu.id;

2.8.3 结构体的初始化

使用构造函数，一种用来初始化结构体的函数，有如下几个特征

直接定义在结构体中
不需要写返回类型
函数名与结构体名相同
默认生成，无形参，无函数体，需要自己写

代码CPP · 21 行

struct StudentInfo {
    int id;
    char gender;

    //用以不初始化就定义结构体变量
    StudentInfo(){}
    // 构造函数，用于初始化结构体内部变量
    StudentInfo(int _id, char _gender) {
        id = _id;
        gender = _gender;
    }
    /* 另一种写法，使用成员初始化列表
    StudentInfo(int _id, char _gender) : id(_id), gender(_gender) {}
    */
    //只初始化gender
    StudentInfo(char _gender){
        gender = _gender;
    }
};

StudentInfo student(12345, 'M');

只要参数个数与类型不完全相同，就可以任意定义多个构造函数，以适应不同的初始化场合。
注意：正是因为没有自己重新定义的构造函数什么都没有，才能够不经初始化就定义结构体变量（思考不初始化构造函数时候是怎么定义的？），所以如果自己重新定义了构造函数，就不能不经过初始化就定义结构体变量！

2.9 补充

2.9.1 cin和cout

cin的输入不指定格式，也不需要加取地址运算符&，直接写变量名就可以了
同时读入多个变量的方法

cin>>n>>db>>c>>str;

如果想要读入一整行，使用getline函数

char str[100];
cin.getline(str,100);

引用getline 是 C++ 标准库中的一个函数，用于从输入流（如 cin）中读取一行文本。与 cin 的 >> 操作符不同，getline 可以...

getline 是 C++ 标准库中的一个函数，用于从输入流（如 cin）中读取一行文本。与 cin 的 >> 操作符不同，getline 可以读取包含空格的整行文本，直到遇到换行符（\n）为止。

语法

getline 函数的基本语法如下：
std::getline(std::cin, string_variable);
std::cin：输入流对象，通常是标准输入流。

string_variable：一个 std::string 类型的变量，用于存储读取的文本。

示例

以下是一个简单的示例，展示了如何使用 getline 函数搭配 cin 读取用户输入的一行文本：
#include <iostream>
#include <string>

int main() {
    std::string name;

    std::cout << "请输入你的名字：";
    std::getline(std::cin, name);

    std::cout << "你好，" << name << "！" << std::endl;

    return 0;
}
解释
包含头文件：
#include <iostream>
#include <string>
包含必要的头文件，<iostream> 用于输入输出流操作，<string> 用于使用 std::string 类型。
定义字符串变量：
std::string name;
定义一个 std::string 类型的变量 name，用于存储用户输入的文本。
提示用户输入：
std::cout << "请输入你的名字：";
使用 std::cout 输出提示信息，要求用户输入名字。
读取用户输入：
std::getline(std::cin, name);
使用 std::getline 函数从 std::cin 读取一行文本，并将其存储在 name 变量中。
输出结果：
std::cout << "你好，" << name << "！" << std::endl;
使用 std::cout 输出欢迎信息，其中包含用户输入的名字。
注意事项

读取整行文本：getline 函数会读取整行文本，包括空格和制表符，直到遇到换行符（\n）为止。

处理换行符：getline 会自动处理换行符，不会将其包含在读取的文本中。

与 cin >> 的区别：cin >> 操作符在读取字符串时会忽略空格和换行符，只读取第一个非空白字符到下一个空白字符之间的内容。

总结

getline 函数是一个非常有用的工具，特别是在需要读取包含空格的整行文本时。通过搭配 cin，你可以方便地从用户输入中读取一行文本，并进行后续处理。 char str[100]; cin.getline(str,100);

cout 控制精度好麻烦，还不如scanf,printf

2.9.2 浮点数的比较

引入一个小量eps来对计算机的浮点误差进行修正，再通过一系列的宏定义来实现修正误差的程序一般取

const double eps = 1e-8;

核心部分(画几个数轴来理解)

const double eps=1e-8;
const double PI=acos(-1.0)

#define Equ(a,b) ((fabs((a)-(b)))<(eps))
#define More(a,b) (((a)-(b))>(eps))
#define Less(a,b) (((a)-(b))<(-eps))
#define MoreEqu(a,b) (((a)-(b))>(-eps))
#define LessEqu(a,b) (((a)-(b))<(eps))

由于精度问题，可能一个0在经过一系列运算之后变为一个很小的负数了，那么这个时候进行一些运算比如sqrt就会报错，那么这个时候就需要用eps保证变量本身在定义域内比如

代码CPP · 20 行

#include <iostream>
#include <cmath>

const double eps = 1e-9;

int main() {
    double x = -1e-15;

    // 确保 x 在定义域内
    if (x < 0) {
        x = eps;
    }

    // 计算平方根
    double result = std::sqrt(x);

    std::cout << "sqrt(" << x << ") = " << result << std::endl;

    return 0;
}

2.9.3 复杂度

时间复杂度

定义：算法需要执行基本运算的次数所处的等级
基本运算：加减乘除之类可以直接执行的运算

for(int i=0;i<n;i++){
    sum+=i;
}

for循环执行了n次，时间复杂度为O(n)，也就是线性增长

for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        sum+=arr[i][j];
    }
}

基本运算次数为$n^{2}$次，因此时间复杂度为O($n^{2}$)
类似无穷小，高等级的幂次会覆盖低等级的幂次
评估时间复杂度：一般OJ系统一秒能承受的运算次数大概是$10^{7}$到$10^{8}$，以此作为判断依据

####　空间复杂度

表示算法需要消耗的最大空间，但是一般都是空间够时间不够，所以可以以时间换空间

编码复杂度

就是看你觉得代码是不是很复杂了，比较泛泛而又定性的一个概念

2.10 黑盒测试

建议直接回去看书，不过这里有一点是值得提一下的
scanf()函数其实是有返回值的，返回值也就是传入参数的数量，而当没有参数传入时会返回-1，而且可以用EOF来代表-1

while(scanf("%d",&a)!=EOF){
    ......
}

2.11 lambda表达式

lambda表达式是一种可以在代码中随时声明的匿名函数。换句话说，lambda表达式允许你直接在需要使用函数的地方声明一个临时的函数，而不需要先定义它。

[捕获列表](参数列表) -> 返回类型 { 函数体 };

捕获列表：这个让lambda可以访问外部变量。
参数列表：就像普通函数的参数列表。
返回类型：这个可以省略，编译器会自动推导返回类型。
函数体：lambda的真正执行内容，就像一个小型的函数。

一个例子，假设需要在代码中临时计算两个数字的乘积：

#include<bits/stdc++.h>
using namespace std;

int main(){
  int x,y;
  auto multiply=[](int a,int b)->int{
    return a*b;
  }
  cout<<multiply(x,y)<<endl;
  return 0;
}

在这段代码中，我们通过 auto multiply = [](int a, int b) -> int { return a * b; }; 创建了一个lambda表达式，这个lambda函数接受两个参数 a 和 b，并返回它们的乘积。然后我们调用 multiply(x, y)，输出结果。

再来一个例子：判断一个函数是否是偶数

auto isEven=[](int x)->bool{return x%2==0;}

关于捕获列表

捕获列表决定了lambda能够访问哪些外部变量，并且是否以值或引用的方式捕获它们。

#include<bits/stdc++.h>
using namespace std;

int main(){
  int factor=2;
  auto multiplyByFactor=[factor](int x)->int{return x*factor;}
  return 0;
}

在这个例子中，lambda表达式 multiplyByFactor 捕获了外部变量 factor，并在它的函数体中使用它。捕获列表 [factor] 让lambda能够“记住”这个变量的值，即使是在函数调用时这个值已经改变了。

lambda表达式的一些特殊使用

存储到变量中并调用

#include <iostream>

int main() {
    // 将 lambda 表达式存储在变量中
    auto printMessage = []() {
        std::cout << "Hello, World!" << std::endl;
    };

    // 在后面需要的时候调用它
    printMessage(); // 输出: Hello, World!
    printMessage(); // 可以多次调用
    return 0;
}

返回值为 Lambda 表达式

可以编写一个函数，返回一个 lambda 表达式供后续调用：

#include <iostream>

auto createMultiplier(int factor) {
    return [factor](int x) { return x * factor; };
}

int main() {
    auto doubleValue = createMultiplier(2); // 创建一个将值乘以2的 lambda
    auto tripleValue = createMultiplier(3); // 创建一个将值乘以3的 lambda

    std::cout << doubleValue(5) << std::endl; // 输出: 10
    std::cout << tripleValue(5) << std::endl; // 输出: 15

    return 0;
}

引用在 C++ 的 lambda 表达式中，[&] 表示按引用捕获所有在 lambda 函数体中使用到的外部变量。这意味着：如果在 lambda...

在 C++ 的 lambda 表达式中，[&] 表示按引用捕获所有在 lambda 函数体中使用到的外部变量。这意味着：

如果在 lambda 内部使用了外部变量，那么该变量是以引用的方式捕获的。

你在 lambda 内对这些变量的修改会直接影响到它们在外部的值。

示例
#include <iostream>

int main() {
    int a = 5, b = 10;
    
    // 定义一个 lambda 表达式，按引用捕获所有外部变量
    auto func = [&]() {
        a += 1;
        b += 1;
        std::cout << "Inside lambda: a = " << a << ", b = " << b << std::endl;
    };
    
    func();  // 调用 lambda 表达式
    std::cout << "Outside lambda: a = " << a << ", b = " << b << std::endl;
    
    return 0;
}
输出：
Inside lambda: a = 6, b = 11
Outside lambda: a = 6, b = 11
如上所示，由于 [&] 按引用捕获，所以 lambda 内对 a 和 b 的修改会直接影响外部的变量。

与其他捕获方式的对比

[=]：按值捕获所有外部变量，lambda 内对变量的修改不会影响外部变量。

[a, &b]：对变量 a 按值捕获，对变量 b 按引用捕获。这种方式可以混合使用捕获方式。

总结一下，[&] 是一种便捷的捕获方式，当你需要在 lambda 内使用外部变量并希望能直接修改它们时，这种方式非常有用。

lambda表达式递归的例子（返回值无法确定时）

#include <functional> // 需要添加此头文件

// 在main函数内：
std::function<void(int, int)> dfs; // 显式声明为function类型
dfs = [&](int now, int step) {
    if (step >= f[now]) return;
    f[now] = step;
    if (now == b) return;
    vis[now] = true;
    if (now + k[now] <= n && !vis[now + k[now]]) {
        dfs(now + k[now], step + 1); // 现在可以正确递归
    }
    if (now - k[now] >= 1 && !vis[now - k[now]]) {
        dfs(now - k[now], step + 1);
    }
    vis[now] = false;
};

第4章入门篇（2）——算法初步

4.1 排序

4.1.1 选择排序

4.1.2 插入排序

4.1.3 排序题与sort函数的应用

引用当然可以！std::sort 中的比较函数用于定义排序的顺序。比较函数需要返回一个布尔值，表示两个元素的相对顺序。具体来说，比较函数应该满足以下...

当然可以！std::sort 中的比较函数用于定义排序的顺序。比较函数需要返回一个布尔值，表示两个元素的相对顺序。具体来说，比较函数应该满足以下条件：

严格弱序（Strict Weak Ordering）：比较函数必须定义一个严格弱序关系，这意味着它必须满足以下条件：
- 反自反性（Irreflexivity）：对于所有 x，comp(x, x) 必须返回 false。
- 反对称性（Antisymmetry）：如果 comp(x, y) 返回 true，那么 comp(y, x) 必须返回 false。
- 传递性（Transitivity）：如果 comp(x, y) 返回 true 且 comp(y, z) 返回 true，那么 comp(x, z) 必须返回 true。
一致性（Consistency）：如果 comp(x, y) 和 comp(y, x) 都返回 false，那么 x 和 y 被认为是相等的。

示例：比较整数

假设我们有一个整数数组，我们希望按升序排序：

代码CPP · 21 行

#include <iostream>
#include <algorithm>  // 包含 std::sort
#include <vector>     // 包含 std::vector

// 比较函数：按升序排序
bool compareAscending(int a, int b) {
    return a < b;
}

int main() {
    std::vector<int> numbers = {5, 3, 8, 1, 2};

    std::sort(numbers.begin(), numbers.end(), compareAscending);

    for (int number : numbers) {
        std::cout << number << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出结果：

1 2 3 5 8

示例：比较字符串

假设我们有一个字符串数组，我们希望按字典序（字母顺序）排序：

代码CPP · 22 行

#include <iostream>
#include <algorithm>  // 包含 std::sort
#include <vector>     // 包含 std::vector
#include <string>     // 包含 std::string

// 比较函数：按字典序排序
bool compareLexicographically(const std::string &a, const std::string &b) {
    return a < b;
}

int main() {
    std::vector<std::string> names = {"Alice", "Bob", "Charlie", "David", "Eve"};

    std::sort(names.begin(), names.end(), compareLexicographically);

    for (const auto &name : names) {
        std::cout << name << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出结果：

Alice Bob Charlie David Eve

示例：比较结构体

假设我们有一个包含学生信息的结构体数组，我们希望按年龄排序：

代码CPP · 33 行

#include <iostream>
#include <algorithm>  // 包含 std::sort
#include <vector>     // 包含 std::vector
#include <string>     // 包含 std::string

struct Student {
    std::string name;
    int age;
    float gpa;
};

// 比较函数：按年龄排序
bool compareStudentsByAge(const Student &a, const Student &b) {
    return a.age < b.age;
}

int main() {
    std::vector<Student> students = {
        {"Alice", 20, 3.8},
        {"Bob", 22, 3.5},
        {"Charlie", 21, 3.7},
        {"David", 19, 3.9},
        {"Eve", 23, 3.6}
    };

    std::sort(students.begin(), students.end(), compareStudentsByAge);

    for (const auto &student : students) {
        std::cout << "Name: " << student.name << ", Age: " << student.age << ", GPA: " << student.gpa << std::endl;
    }

    return 0;
}

输出结果：

Name: David, Age: 19, GPA: 3.9
Name: Alice, Age: 20, GPA: 3.8
Name: Charlie, Age: 21, GPA: 3.7
Name: Bob, Age: 22, GPA: 3.5
Name: Eve, Age: 23, GPA: 3.6

示例：多条件比较

假设我们希望在年龄相同的情况下，按 GPA 排序，如果 GPA 也相同，则按名字排序：

代码CPP · 39 行

#include <iostream>
#include <algorithm>  // 包含 std::sort
#include <vector>     // 包含 std::vector
#include <string>     // 包含 std::string

struct Student {
    std::string name;
    int age;
    float gpa;
};

// 比较函数：按年龄、GPA、名字排序
bool compareStudents(const Student &a, const Student &b) {
    if (a.age != b.age) {
        return a.age < b.age;
    }
    if (a.gpa != b.gpa) {
        return a.gpa > b.gpa;  // 按 GPA 降序排序
    }
    return a.name < b.name;
}

int main() {
    std::vector<Student> students = {
        {"Alice", 20, 3.8},
        {"Bob", 22, 3.5},
        {"Charlie", 21, 3.7},
        {"David", 19, 3.9},
        {"Eve", 23, 3.6}
    };

    std::sort(students.begin(), students.end(), compareStudents);

    for (const auto &student : students) {
        std::cout << "Name: " << student.name << ", Age: " << student.age << ", GPA: " << student.gpa << std::endl;
    }

    return 0;
}

输出结果：

Name: David, Age: 19, GPA: 3.9
Name: Alice, Age: 20, GPA: 3.8
Name: Charlie, Age: 21, GPA: 3.7
Name: Bob, Age: 22, GPA: 3.5
Name: Eve, Age: 23, GPA: 3.6

总结

比较函数是 std::sort 的核心部分，它决定了排序的顺序。比较函数需要返回一个布尔值，表示两个元素的相对顺序。通过编写不同的比较函数，你可以实现各种排序需求。

1. 相关结构体的定义

排序题一般会给出个体的许多信息，为了方便常常把这些信息统统存在一个结构体中

struct Student{
	char name[10];
	char id[10];
	int score;
}stu[100100];

2.cmp函数的编写(strcmp函数依据字典序返回两个字符串大小的比较结果)

比如一个排序规则：如果两个学生分数不相同那么分数高的排在前面，否则将姓名字典序小的排在前面
就可以写出这样的cmp函数

bool cmp(Student a,Student b){
    if(a.score!=b.score) return a.score>b.score;
    else return strcmp(a.name,b.name)<0;
}//注意strcmp的返回值不一定是1或者-1，与IDE有关

3.排名的实现

规则一般是：分数不同的排名不同，分数相同的排名相同但是占用一个排位

对这种要求一般需要在结构体类型定义的时候就把排名这一项加入结构体中，于是在数序排序完成之后就有两种方法来实现排名的计算

先将数组第一个个体排名记作1（这个个体数组下标为0），然后遍历剩余的个体：
- 如果当前个体的分数等于上一个个体的分数，那么当前个体的排名=上一个个体的排名
- 否则，当前个体的排名=数组下标+1
```
stu[0].r=1;
for(int i=1;i<n;i++){
    if(stu[i].score==stu.[i-1].score){
        stu[i].r=stu[i-1].r;
    }
    else{
        stu[i].r=i+1;
    }
}
```

而有些时候也不一定需要记下来排名，直接输出就好了

int r=1;
for(int i=0;i<n;i++){
    if(i>0&&stu[i].score!=stu[i-1].score){
        r=i+1;
    }
    //输出当前个体信息
}

4.2 散列

4.2.1 散列的定义与整数散列

散列(hash)是一种常用的算法思想

比如用hashTable的bool/int数组去判断一个数是否出现过即:把输入的数作为数组的下标来对这个数的性质进行统计,是一个很好的以空间换时间的策略,因为查询的复杂度是O(1)

下面我们给出hash的定义，可以浓缩成一句话：将元素通过一个函数转换为整数，使得该整数可以尽量唯一地代表这个元素，其中这个转换函数被称为散列函数H

即：如果元素在转换前为key，那么转换之后就是一个整数H(key),再把转换完的hash值用一个数组去记录

对于key为整数的情况：常用的散列函数有：

直接定址法：H(key)=key 或者 H(key)=a*key+b做一个线性变换
平方取中法：取key的平方中间的若干位作为hash值
除留余数法：把key除以一个数mod得到的余数作为hash值的方法，即H(key)=key%mod

通过这个散列函数可以把很大的数转化为不超过mod的整数，这样就可以把它视为可行的数组下标(需要注意表长>=mod)。显然当mod是一个素数时，H(key)尽可能覆盖[0,mod)范围内的每一个数。因此一般为了方便起见取TSize为一个素数，而mod直接取成与TSize相等

但是很容易注意到这个方法可能会有两个不同的数key1与key2使得H(key1)==H(key2)，这种情况叫“冲突”

下面有三种方法解决冲突，其中第一种和第二种方法都计算了新的hash值，又称为开放定址法
1. 线性探查法：当得到 key 的 hash 值 H(key),但是表中下标为 H(key)的位置已经被某个其他元素使用了那么就检査下一个位置H(key)+1是否被占，如果没有，就使用这个位置;否则就继续检查下一个位置(也就是将hash值不断加1)。如果检查过程中超过了表长，那么就回到表的首位继续循环，直到找到一个可以使用的位置，或者是发现表中所有位置都已被使用。显然，这个做法容易导致扎堆，即表中连续若于个位置都被使用，这在一定程度上会降低效率。
2. 平方探査法：在平方探查法中，为了尽可能避免扎堆现象，当表中下标为H(key)的位置被占时，将按下面的顺序检査表中的位置:H(key)+$1^{2}$、H(key)-$1^{2}$、H(key)+ $2^{2}$、H(key)- $2^{2}$、H(key)+ $3^{2}$…。如果检査过程中 H(key)+$k^{2}$超过了表长 TSize，那么就把 H(key)+$k^{2}$对表长 TSize 取模;
  
  如果检查过程中出现 H(key)-$k^{2}$<0的情况(假设表的首位为 0),那么将((H(key)-$k^{2}$)% TSize+ TSize)% TSize作为结果(等价于将H(key)-$k^{2}$不断加上 TSize 直到出现第一个非负数)。如果想避免负数的麻烦，可以只进行正向的平方探查。可以证明，如果k在[0,TSize)范围内都无法找到位置，那么当k>TSize时，也一定无法找到位置。
3. 链地址法（拉链法）：和上面两种方法不同，链地址法不计算新的 hash 值，而是把所有 H(key)相同的 key 连接成一条单链表(可以在学习完7.3小节后回过头来看)。这样可以设定一个数组Link，范围是Link[0]~ Link[mod]，其中 Link[h]存放 H(key)=h的一条单链表，于是当多个关键字 key 的hash 值都是h时，就可以直接把这些冲突的key直接用单链表连接起来，此时就可以遍历这条单链表来寻找所有H(key)=h的key。当然，一般来说，可以使用标准库模板库中的map(见6.4节)来直接使用hash的功能(C++11 以后可以用unordered map，速度更快)，因此除非必须模拟这些方法或是对算法的效率要求比较高，一般不需要自己实现上面解决冲突的方法。

4.2.2 字符串hash初步

如果key不是整数，该如何设计散列函数？

一个例子是:如何将一个二维整点P的坐标映射为一个整数，使得整点P可以由该整数唯一地代表。假设一个整点P的坐标是(x,y)，其中 0<x,y<Range，那么可以令 hash 函数为H(P)=x*Range+y，这样对数据范围内的任意两个整点P1与P2,H(P1)都不会等于 H(P2),就可以用 H(P)来唯一地代表该整点P,接着便可以通过整数 hash 的方法来进一步映射到较小的范围。本节的重点在于字符串hash。字符串hash是指将一个字符串S映射为一个整数，使得该整数可以尽可能唯一地代表字符串S。本节只讨论将字符串转换为唯一的整数，进阶部分在12.1节。

为了讨论问题方便，先假设字符串均由大写字母A~Z构成。在这个基础上，不妨把A~Z视为0~25，这样就把 26个大写字母对应到了二十六进制中。接着，按照将二十六进制转换为十进制的思路，由进制转换的结论可知，在进制转换过程中，得到的十进制肯定是唯一的，由此便可实现将字符串映射为整数的需求(注意:转换成的整数最大为是$26^{len}$-1(len为字符串长度)，代码如下

int hashFunc(char s[],int len){ //hash函数，将字符串S转换为整数
    int id=0;
    for(int i=0;i<len;i++){
        id=id*26+(s[i]-'A'); //将26进制转化为10进制
    }
    return id;
}

显然len不能太长了，如果里面还有小写字母可以把26进制变成52进制，也是一样的

而如果出现了数字，一般有两种处理方法: ① 按照小写字母的处理方法，增大进制数至 62。

②如果保证在字符串的末尾是确定个数的数字,那么就可以把前面英文字母的部分按上面的思路转换成整数，再将末尾的数字直接拼接上去。例如对由三个字符加一位数字组成的字符串“BCD4”来说，就可以先将前面的“BCD”转换为整数731，然后直接拼接上末位的4变为7314即可。下面的代码体现了这个例子:

int hashFunc(char s[],int len){ //hash函数，将字符串S转换为整数
    int id=0;
    for(int i=0;i<len-1;i++){
        id=id*26+(s[i]-'A'); //将26进制转化为10进制
    }
    id=id*10+(s[len]-'0');
    return id;
}

4.3 递归

4.3.1 分治

分治全称：分而治之，也就是将原问题划分成若干个规模较小而结构与原问题相同或相似的子问题，然后分别解决这些子问题，最后合并子问题的解，即可得到原问题的解，也就是说分治法可以分为三步

分解
解决
合并

需要指出的是分治法分解出的子问题应该是相互独立而没有交叉的，如果存在两个子问题有交叉部分，那么就不应该用分治法求解

特别地，把子问题个数为1的情况称之为减治

分治作为一种算法思想，既可以使用递归的手段去实现，也可以同非递归的手段去实现，不过视情况而定

4.3.2 递归

在编写递归函数的时候，可以当系统库里有一个同名的函数可以实现所需要的功能；当函数编写完成之后，逻辑也就自洽了

递归，在于反复调用自身函数，但是每次把问题范围缩小，直到范围缩小到可以直接得到边界数据的结果，然后再在返回的路上求出对应的解，这样看来递归很适合实现分治思想

写递归的时候不要陷入无尽的分析子过程，分析好边界条件，写好本过程要处理什么东西，然后剩下的就是相信子过程能处理好你的求解问题就行了。和数学归纳法一个套路

确定问题
解决基准问题
拆解问题

递归的逻辑中一般有两个重要概念

递归边界
递归式（或称递归调用）

给出一个例子

//计算n的阶乘
//考虑n!的计算式，不难得出递归式F(n)=nF(n-1)
//所以可以把F(n)变成F(n-1),然后一直递归下去...
//什么时候是尽头呢?考虑0!=1,不妨以F(0)=1作为递归边界
//即:规模减小到n=0的时候开始"回头"

#include<bits/stdc++.h>
using namespace std;

int F(int n){
    if(n==0) return 1; //到达递归边界时返回
    else return n*F(n-1); //没有到达边界时使用递归式递归下去
}

再给出一个例子

//计算Fibonacci数列的第n项
#include<bits/stdc++.h>
using namespace std;

int F(int n){
    if(n==1||n==2) return 1; //到达递归边界时返回
    else return F(n-1)+F(n-2); //没有到达边界时使用递归式递归下去
}
//其实这就是分治法的一种应用，
//对于给定的n把求解F(n)的问题分解成求F(n-1)和F(n-2)这两个子问题,
//而F(0)==F(1)==1是n很小的时候问题的直接解决

由上面两个例子可以知道，实现一个递归函数需要两样东西：递归边界与递归式，其中递归边界用来返回最简单底层的结果，递归式用来减少数据规模并向下一层递归。

再给出一个例子

代码CPP · 29 行

////按照字典序输出全排列
//可以分成若干个子问题：输出1开头的全排列，输出2开头的全排列
//...输出以n开头的全排列
//于是不妨设定一个数组P用以存放当前的排列
//再设定一个hashTable，其中hashTable[x]==true表示x在数组P中

#include<bits/stdc++.h>
using namespace std;
const int maxn=11;
//P为当前排列，hashTable记录整数x是否已在P中
int n,P[maxn],hashTable[maxn]={false};
//当前处理排列的第index号位
void generateP(int index){
    if(index==n+1){//递归边界，已经处理完排列的1~n位
        for(int i=1;i<=n;i++){
            cout<<P[i]; //输出当前排列
        }
        cout<<endl;
        return;
    }
    for(int x=1;x<=n;x++){//枚举1~n，试图将x填入P[index]中
        if(hashTable[x]==false){
            P[index]=x; //令P的第index位为x，即把x加入当前排列
            hashTable[x]=true; //记x已在P中
            generateP(index+1); //处理排列的第index+1号
            hashTable[x]=false; //已处理完P[index]为x的子问题，还原状态
        }
    }
}

最后来看n皇后问题

指的是在一个n*n的棋盘上放置n个皇后使得这n个皇后两两均不在同一行、同一列、同一对角线上，求合法的方案数

代码CPP · 37 行

#include<bits/stdc++.h>
using namespace std;
const int maxn=11;
//每行只能放置一个皇后，每列也只能放置一个
//把n列皇后所在的行号依次写出，就会是1~n的一个排列
//只需要筛选这每个排列中合法的即可
//考虑：递归边界、递归式
//由于到达递归边界时表示生成了一个排列，
//所以需要在其内部判断是否为合法方案
//如何判断？在一个排列中两两遍历两个皇后，
//判断他们是否在一条对角线上
//如果不是就count++
int count=0;
int n,P[maxn],hashTable[maxn]={false};
void A(int index){
    if(index==n+1){//递归边界，表示生成了一个排列（类似上一题）
        bool flag=true;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(abs(i-j)==abs(P[i]-P[j])){//如果在一条对角线上，斜率为±1
                    flag=false;
                    break;
                }
            }
        }
        if(flag) count++;
        return;
    }
    for(int x=1;x<=n;x++){//就是上一题全排列，因为不能在同一行同一列和全排列的数学本质相同
        if(!hashTable[x]){//这一行还没被占用
            P[index]=x;
            hashTable[x]=true;
            A(index+1);
            hashTable[x]=false;
        }
    }
}

但是这种解法事实上太暴力了，因为已经生成一部分排列的时候就可以判断这个排列符不符合要求了，如果不符合也就没必要递归了，直接返回上一层，这种做法一般称之为回溯法

代码CPP · 28 行

#include<bits/stdc++.h>
using namespace std;
const int maxn=11;
int count=0;
int n,P[maxn],hashTable[maxn]={false};
void A(int index){
    if(index==n+1){
        count++; //能到这里的一定符合要求
        return;
    }
    for(int x=1;x<=n;x++){//第x行
        if(!hashTable[x]){//第x行还没有皇后
            bool flag=true;
            for(int pre=1;pre<index;pre++){//遍历之前的皇后
                if(abs(index-pre)==abs(P[index]-P[pre])){
                    flag=false;
                    break;
                }
            }
            if(flag){
            P[index]=x;
            hashTable[x]=true;
            A(index+1);
            hashTable[x]=false;
            }
        }
    }
}

4.4 贪心

4.4.1 简单贪心

贪心是求解一类最优化问题的方法，它总是考虑在当前状态下局部最优（或较优）的策略，来使全局的结果达到最优（或较优）。平常来说，证明贪心法的思路是反证法，即假设策略不能导致最优解，然后通过一系列推导来得到矛盾

例题 PAT B1020 月饼

题意

现有月饼需求量为D，已知n种月饼各自的库存量和总售价，问如何销售这些月饼，使得可以获得的收益最大，并求最大收益

思路

贪心策略：总是选择单价最高的月饼出售，可以获得最大的利润。因此对于每一种月饼都根据其库存量和总售价来计算出该种月饼的单价，之后再把所有单价由低到高排序

之后从单价高的月饼开始枚举，分两种情况

如果该种月饼的库存量不足以填补需求量$\Rightarrow$全部卖出，需求量-=该种月饼库存量，收益值+=该种月饼总售价
如果足够供应，则直接算

[!CAUTION] 需要注意的几点

月饼的库存量和总售价可以是浮点数，虽然题目里只说了D是整数，但是为了计算方便最好也定义成double型

当库存量>需求量时，不能先令需求量为0再计算收益，否则会使得该步收益为0

库存>需求时候记得中断循环

代码实现

代码CPP · 42 行

#include<bits/stdc++.h>
using namespace std;
int n,d;

struct mooncake{
    double storage;
    double price_all;
    double price;
}cake[1010];

bool cmp(mooncake a,mooncake b){
    return a.price>b.price;
}

int main(){
    scanf("%d%d",n,d);

    for(int i=0;i<n;i++){
        scanf("%d",cake[i].storage);
    }
    for(int i=0;i<n;i++){
        scanf("%d",cake[i].price_all);
        cake[i].price=cake[i].price_all/cake[i].storage;
    }

    sort(cake,cake+n,cmp);

    double ans=0;

    for(int i=0;i<n;i++){
        if(cake[i].storage>=d){
            ans+=d*cake[i].price;
            break;
        }
        else{
            ans+=cake[i].price_all;
            d-=cake[i].storage;
        }
    }
    printf("%.2f",ans);
    return 0;
}

例题 PAT B1023 组个最小数

题意

给定若干个数字0~9，在0不做首位的前提下可以任意排列但必须全部使用，输出可以组成的最小的数

分析

先输出最高位：从1-9中选最小的输出

之后：依次按照0-9的顺序输出数字，输出顺序为其剩余的次数

代码实现

代码CPP · 25 行

#include<bits/stdc++.h>
using namespace std;

int n,cnt[10],temp;

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&temp);
        cnt[temp]++;
    }
    for(int i=1;i<=9;i++){
        if(cnt[i]!=0){
            printf("%d",i);
            cnt[i]--;
            break;
        }
    }
    for(int i=0;i<=9;i++){
        for(int j=0;j<cnt[i];j++){
            printf("%d",i);
        }
    }
    return 0;
}

引用【洛谷 P4447 [AHOI2018初中组] 分组】题目描述小可可的学校信息组总共有 $n$ 个队员，每个人都有一个实力值 $a_i$。现...

【洛谷 P4447 [AHOI2018初中组] 分组】

题目描述

小可可的学校信息组总共有 $n$ 个队员，每个人都有一个实力值 $a_i$。现在，一年一度的编程大赛就要到了，小可可的学校获得了若干个参赛名额，教练决定把学校信息组的 $n$ 个队员分成若干个小组去参加这场比赛。

但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队，于是要求分成的每个小组的队员实力值连续，同时，一个队不需要两个实力相同的选手。举个例子：$[1, 2, 3, 4, 5]$ 是合法的分组方案，因为实力值连续；$[1, 2, 3, 5]$ 不是合法的分组方案，因为实力值不连续；$[0, 1, 1, 2]$ 同样不是合法的分组方案，因为出现了两个实力值为 $1$ 的选手。

如果有小组内人数太少，就会因为时间不够而无法获得高分，于是小可可想让你给出一个合法的分组方案，满足所有人都恰好分到一个小组，使得人数最少的组人数最多，输出人数最少的组人数的最大值。

注意：实力值可能是负数，分组的数量没有限制。

输入格式

输入有两行：

第一行一个正整数 $n$，表示队员数量。
第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个队员的实力。

输出格式

输出一行，包括一个正整数，表示人数最少的组的人数最大值。

样例 #1

样例输入 #1
7
4 5 2 3 -4 -3 -5
样例输出 #1
3
提示

【样例解释】分为 $2$ 组，一组的队员实力值是 ${4, 5, 2, 3}$，一组是 ${-4, -3, -5}$，其中最小的组人数为 $3$，可以发现没有比 $3$ 更优的分法了。

【数据范围】

对于 $100%$ 的数据满足：$1\leq n\leq 100000$，$|a_i|\leq10^9$。

本题共 $10$ 个测试点，编号为 $1\sim10$，每个测试点额外保证如下：

测试点编号数据限制

$1\sim2$ $n\leq 6, 1\leq a_i \leq 100$

$3\sim4$ $n\leq 1000, 1\leq a_i\leq 10^5$ 且 $a_i$ 互不相同

$5\sim6$ $n\leq 100000, a_i$ 互不相同

$7\sim8$ $n\leq 100000, 1\leq a_i \leq10^5$

$9\sim 10$ $n\leq 100000, -10^9 \leq a_i \leq 10^9$

测试点编号	数据限制
$1\sim2$	$n\leq 6, 1\leq a_i \leq 100$
$3\sim4$	$n\leq 1000, 1\leq a_i\leq 10^5$ 且 $a_i$ 互不相同
$5\sim6$	$n\leq 100000, a_i$ 互不相同
$7\sim8$	$n\leq 100000, 1\leq a_i \leq10^5$
$9\sim 10$	$n\leq 100000, -10^9 \leq a_i \leq 10^9$

思路：贪心，//贪心策略：每次加人都加在人数最少的那个队里面，这样可以最大化最小组的人数

代码CPP · 44 行

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
const int inf=0x3f3f3f3f;

int main(){
  ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  sort(a.begin(),a.end());
  //贪心策略：每次加人都加在人数最少的那个队里面，这样可以最大化最小组的人数
  
  map<int,priority_queue<int,vector<int>,greater<int>>> group;
  //map的键是这个组的实力值最大值，值是用来存储已经组建的所有符合该最大实力值的组的人数，队首的是人数最少的
  
  //遍历每个队员的实力值，进行分组
  for(int i=0;i<n;i++){
    int groupSize=0; // 当前队员加入后的组大小

    auto it=group.find(a[i]-1); //查看当前实力值减去1的分组（前一个实力值的组）
    if(it!=group.end()){
      if(!it->second.empty()){ //这个其实是使用队列(优先队列也是队列)的好习惯，先判断非空再访问
        groupSize=it->second.top();
        it->second.pop();
      }
    }
    groupSize++;
    group[a[i]].push(groupSize);
  }
  
  int minGroupSize=inf;
  for(auto& now:group){ //区别上一个循环的it是迭代器(指针)，这里的是map类型，所以访问值不需要用->
    if(!now.second.empty()){
      minGroupSize=min(minGroupSize,now.second.top());
    }
  }
  
  cout<<(minGroupSize==inf?0:minGroupSize)<<endl;
  return 0;
}

4.4.2 区间贪心

由一个问题引入：

区间不相交问题

给出N个开区间(x,y)，从中选择尽可能多的开区间使得这些区间两两没有交集。输出满足条件的区间的个数。

例如对于开区间(1,3) (2,4) (3,5) (6,7)来说最多可以选出三个区间(1,3) (3,5) (6,7)满足题意

首先考虑最简单的情况，如果开区间$I_1$被开区间$I_2$包含，那么选择$I_1$会是更好的选择，因为如果选择$I_1$，就会有更大的空间去容纳别的开区间

接下来把开区间按左端点x从大到小排序，如果去掉区间包含的情况就必有$y_1>$$y_2 > \cdots$ $y_n $成立，观察图片可以发现$I_1$的右边必然有一段不与其他区间重合，如果把他去掉那么$I_1$的左边剩余部分就会包含于$I_2$，则由上一种情况又可知应当选择$I_1$，因此对于这种情况总是选择左端点最大的区间

代码实现

代码CPP · 33 行

#include<bits/stdc++.h>
using namespace std;

const int max1=100;

struct interval{
    int x,y;
}iv[max1+5];

bool cmp(interval a,interval b){
    if(a.x!=b.x) return a.x>b.x;
    else return a.y<b.y;
}
int n;

int main(){
    while(scanf("%d",&n),n!=0){ //这样可以保证n小于等于0的时候不会进行
        for(int i=0;i<n;i++){
        scanf("%d%d",&iv[i].x,&iv[i].y);
        }
        sort(iv,iv+n,cmp);
        //ans记录满足条件的区间个数，lastX记录上一次被选中的区间的左端点
        int ans=0,lastX=iv[0].x;
        for(int i=1;i<n;i++){
            if(iv[i].y<=lastX){
                lastX=iv[i].x;
                ans++;
            }
        }
        printf("%d",ans);
    }
    return 0;
}

上面这段代码中while里面的写法，复习一下逗号运算符

逗号运算符的作用是依次执行其左右两边的表达式，并返回右边表达式的结果。

while (scanf("%d", &n), n != 0) 的执行过程：

先执行 scanf("%d", &n)：从输入中读取一个整数并存储到变量 n 中。
然后计算 n != 0：判断 n 是否不等于 0。
整个逗号表达式的结果是 n != 0 的值（true 或 false）。
while 循环会根据 n != 0 的结果决定是否继续循环

事实上总是选择右端点最小的区间的策略也是可行的

类似的问题还有区间选点问题，即给出N个闭区间，求最少需要确定多少个点使得每个闭区间中都至少存在一个点

4.5 二分

4.5.1 二分查找

由于每一步都可以去除当前区间的一半元素，因此时间复杂度是O(logN)

要求：a[]为严格递增（递减）序列

代码实现

int binarysearch(int a[],int left,int right,int x){
    int mid;
    while(left<=right){ //因为left>right就无法形成闭区间了
        mid=(left+right)/2;
        if(a[mid]==x) return mid;
        else if(a[mid]<x){
            left=mid+1;
        }
        else{
            right=mid-1;
        }
    }
    return -1; //查找失败，返回-1
}

序列严格递减的情况是同理的

如果二分上界超过INTMAX/2，可能会导致mid=(left+right)/2中的left+right爆掉，所以一般使用等价语句mid=left+(right-left)/2

讨论一个更进一步的问题，如果序列并非严格单调，如何求出待查询元素的左闭右开的存在区间[L,R)，如果序列中没有x，也可以把L和R理解成假设序列中存在x，则x应该在的位置

可以把这个问题拆解成两个（分治）:

1.求序列中第一个≥x的元素的位置

int lower_bound(int a[],int left,int right,int x){
    int mid;
    while(left<right){ //当left=right的时候就是所需的下界
        mid=left+(right-left)/2;
        if(a[mid]>=x){
            right=mid;
        }
        else{
            left=mid+1;
        }
    }
    return left;
}

循环条件为left<right而非left≤right，因为需要的结果就是left=right夹出来的
二分下界应为0，但是上界是n-1还是n？考虑到x可能不存在，而我们求出来的又是“假设x存在他应该在的位置”（也就是最大的地方），所以开始运行的时候应该取left=0，right=n

2.求序列中第一个大于x的元素的位置

int upper_bound(int a[],int left,int right,int x){
    int mid;
    while(left<right){
        mid=left+(right-left)/2;
        if(a[mid]>x){
            right=mid;
        }
        else{
            left=mid+1;
        }
    }
    return left;
}

容易注意到这两个函数的唯一区别就是把a[mid]>=x改成了a[mid]<x，其余完全一致

其实这两个函数都在解决这样一个问题：寻找有序序列中第一个满足某条件的元素

对于lower_bound函数而言，寻找的就是第一个满足条件“值大于等于x”的元素的位置，而对于upper_bound函数而言，寻找的就是第一个满足条件“值大于x”的元素的位置，则这样的一个“条件”在序列中一定是从左到右先不满足，然后满足（否则将此条件取反）

归纳

//解决“寻找有序序列中第一个满足某条件的元素的位置”的问题的固定模板
//二分区间为左闭右闭的[left,right]，初值必须能够覆盖解的所有可能取值
int solve(int left,int right){
    int mid;
    while(left<right){
        if(条件成立){ //条件成立，第一个满足条件的元素的位置<=mid
            right=mid;
        }
        else{ //条件不成立，则第一个满足条件的元素的位置>mid
            left=mid+1;
        }
    }
    return left;
}

另外，如果想要寻找最后一个满足“条件C”的元素的位置，则可以先求第一个满足“条件!C”的元素的位置，然后再把该元素的位置-1即可

另外，就算二分区间不是闭区间，也可以操作

比如当二分区间为左开右闭区间(left,right]，那么循环条件应当为left+1<right，也即退出循环的时候有left+1=right成立，使得夹逼得到的唯一，而由于变为了左开，left的初值要比解的最小取值要小1，同时语句left=mid+1应该改成left=mid，返回值也应该是right(毕竟闭区间是可以取到的)，代码如下

//解决“寻找有序序列中第一个满足某条件的元素的位置”的问题的固定模板
//二分区间为左开右闭区间(left,right]，初值必须能够覆盖解的所有可能取值
int solve(int left,int right){
    int mid;
    while(left+1<right){
        if(条件成立){ //条件成立，第一个满足条件的元素的位置<=mid
            right=mid;
        }
        else{ //条件不成立，则第一个满足条件的元素的位置>mid
            left=mid;
        }
    }
    return right;
}

如何判断lower_bound函数和upper_bound函数的查询是否成功？可以判断上界是否为n

（因为upper_bound函数求的也是满足条件的元素的位置的后面的第一个）

4.5.2 二分法拓展

如何计算$\sqrt 2$的近似值

对于$f(x)=x^2$当$x>0$时$f(x)$单调递增，那么我们可以考虑使用二分法来逼近，取精确到$10^{-5}$为例

#include<bits/stdc++.h>
using namespace std;

const double eps = 1e-5; //精度为10^{-5}
double f(double x){ //计算f(x)
    return x*x;
}

double calsqrt(){
    double left=1,right=2,mid;
    while(right-left>eps){ //回顾之前学的高精度判断相等
        mid=left+(right-left)/2;
        if(f(mid)>2) right=mid;
        else left=mid;
    }
    return mid;
}

木棒切割问题

给出N根长度已知的木棒，现在希望通过切割他们来得到至少K段长度相等的木棒（长度必须是整数），问这些长度相等的木棒最长能有多长？

容易注意到K越大，则L越小，那么考虑到这个我们可以使用二分法

int F(L){
	给定长度，计算当前总段数
}

int 二分(){
	left=1
	right=杆子最长的长度
	while(left<right){
		mid=直接算
		cnt=F(mid)
		if(cnt>=k) left=mid
		else right=mid
	}
	return mid;
}

4.5.3 快速幂

给定一个问题

给定三个正整数a、b、m（a<$10^9$，b<$10^6$，$1$<m<$10^9$），求$a^{b}$%m

可以采用这种代码，时间复杂度为O(b)

xxxxxxxxxx typedef long long LL;LL LLpow(LL a,LL b,LL m){    LL ans=1;    for(int i=0;i<b;i++){        ans=ans*a%m; //考虑模运算的性质(a×b)modm=[(amodm)×(bmodm)]modm    }    return ans;}cpp

代码中使用LL而非int是防止两个int相乘之后溢出

考虑一个更进一步的问题

给定三个正整数a、b、m（a<$10^9$，b<$10^{18}$，$1$<m<$10^9$），求$a^{b}$%m

对于这个问题，如果还是按上面的做法显然是不行的

这里要使用快速幂的用法，它基于二分的思想，因此也常常被称之为二分幂，快速幂基于以下事实

如果b是奇数，那么有$a^b=a*a^{b-1}$
如果b是偶数，那么有$a^b=a^{b/2}*a^{b/2}$

显然，b是奇数的情况总可以在下一步转换为b是偶数的情况，而b是偶数的情况总可以在下一步转换为b/2的情况，这样在log(b)级别的转换后，就可以把b变为0，而任何正整数的0次方都是1

举个例子，如果需要求$2^{10}$

对$2^{10}$来说，由于幂次10为偶数，因此需要先求$2^{5}$，然后有$2^{10}=2^{5}*2^{5}$
对于$2^{5}$来说，由于幂次5为奇数，因此先要求$2^{4}$，然后有$2^5=2*2^4$
对于$2^4$来说，由于幂次4为偶数，因此先要求$2^2$，然后有$2^4=2^2*2^2$
对于$2^2$来说，由于幂次2为偶数，因此需要先求$2^1$，然后有$2^2=2^1*2^1$
对于$2^1$来说，由于幂次1为奇数，因此需要先求$2^0$，然后有$2^1=2*2^0$
$2^0=1$，然后从下往上依次回退计算即可

这显然是递归的思想，于是可以得到快速幂的递归写法，时间复杂度为O(logb)

typedef long long LL;
LL binaryPow(LL a,LL b,LL m){
    if(b==0) return 1;
    if(b%2==1) return a*binaryPow(a,b-1,m)%m;
    else{
        LL mul=binaryPow(a,b/2,m);
        return mul*mul%m;
    }
}

上面的代码中，条件if(b%2==1)可以用if(b&1)代替，这是因为b&1进行位与操作，判断b的末位是否为1，因此当b为奇数时b&1返回1，if条件成立，这样写执行速度会快一点

还需要注意，当b%2==0时不要直接返回binaryPow(a,b/2,m)*binaryPow(a,b/2,m)，而应计算单个binaryPow(a,b/2,m)之后再乘起来，这是因为前者每次都会调用两个binaryPow函数，导致复杂度变为O($2^{log(b)}$)=O(b)。例如求binaryPow(8)时，会变成binaryPow(4)*binaryPow(4)，而这两个binaryPow(4)又会各自变成binaryPow(2)*binaryPow(2)，而每个binaryPow(2)又会变成binaryPow(1)*binaryPow(1)，因此最后需要求8次binaryPow(1)

另外，针对不同的题目可能有两个细节需要注意

如果初始时a可能大于m，那么需要在进入函数前就让a对m取模
如果m为1，可以直接在函数外部特判为0，不需要进入函数来计算（因为任何正整数对1取模一定等于0）

接下来研究一下快速幂的迭代写法（填坑）

4.6 two pointers

4.6.1 什么是two pointers

two pointers是算法编程中一种非常重要的思想，以一个例子来引入

给定一个递增的正整数序列和一个正整数M，求序列中两个不同位置的数a和b，使得他们的和恰好为M，输出所有满足条件的方案。

例如给定序列{1,2,3,4,5,6}和正整数M=8，就存在$2+6=8$和$3+5=8$成立

本题最直观的一个想法是使用二重循环枚举序列中的a和b，判断他们的和是否为M，代码实现如下

for(int i=0;i<n;i++){
    for(int j=i;j<=n;j++){
        if(a[i]+a[j]==M){
            cout<<i<<j<<endl;
        }
    }
}

这样的时间复杂度是O($n^2$)，太高了，来看看高复杂度的原因是什么：

对于一个确定的a[i]来说，如果当前的a[j]满足a[i]+a[j]>M，显然也会有a[i]+a[j+1]>M（这是由于序列是递增的），因此就不需要对a[j]之后的数进行枚举。如果无视这个性质，就会导致对j进行了大量的无效枚举
对某一个a[i]来说，如果找到一个a[j]，使得a[i]+a[j]>M恰好成立，那么对于a[i+1]来说也一定有a[i+1]+a[j]>M成立，因此在a[i]之后的元素也不必再去枚举

由上面两点可见：i和j的枚举是互相牵制的，事实上本题中two pointers将利用有序序列的枚举特性来有效降低复杂度，算法过程如下：

令下标i的初值为0，下标j的初值为n-1

a[0]	···	a[i]	a[i+1]	···	a[j-1]	a[j]	···	a[n-1]

然后我们就可以设想，只让i往右走（即i++），只让j往左走（即j--），然后根据a[i]+a[j]情况的不同来让i和j恰当地移动，就可以做到遍历所有情况

若a[i]+a[j]=M，则不可能在固定i或者固定j的情况下使另外一个下标移动，二者的和仍为M，那么只能让i++，j--
若a[i]+a[j]>M，那么要让其中一个后退，又只能是j后退，所以i不变，j--
若i]+a[j]<M，同理有i++，j不变

反复执行上面三个判断直到i>=j成立（这样可以遍历所有的情况）

代码实现如下

int i=0,j=n-1;
while(i<j){
    if(a[i]+a[j]==M){
        printf("%d %d",i,j);
        i++;
        j--;
    }
    else if(a[i]+a[j]>M) j--;
    else i++;
}

显然时间复杂度为O(n)

再给一个例子

序列合并问题：给定两个递增序列a和b，合并成同一个递增序列c

同样可以设置两个下标i和j，利用类似的思路完成问题

int merge(int a[],int b[], int c[], int n, int m){
    //n和m分别是数组a和b的长度
    int i=0,j=0,index=0;
    while(i<n&&j<m){
        if(a[i]<=b[j]) c[index++]=a[i++]; //相等的情况放a和b都一样
        else c[index++]=b[j++]; //把b[j]放入序列中
    }
    while(i<n) c[index++]=a[i++]; //把a的剩余元素放入c中
    while(j<m) c[index++]=b[j++]; //把b的剩余元素放入c中
    return index; //返回序列c的长度
}

归纳

two pointers是利用问题本身和序列的特性，使用两个下标对序列进行扫描（可以同向也可以反向），以较低的复杂度解决问题

4.6.2 归并排序

归并排序是一种基于“归并”的排序方法，这里主要介绍最基本的2-路归并排序

思路：将序列两两分组，将序列归并为$\lceil \frac{n}{2} \rceil$个组，组内单独排序，然后再把这些组两两归并，生成$\lceil \frac{n}{4} \rceil$个组，组内再单独排序，以此类推，直到只剩下一个组位置，时间复杂度为O(nlogn)

代码实现：

递归实现

代码CPP · 25 行

const int maxn=100;
//将数组a的[l1,r1]与[l2,r2]区间合并为有序区间（此处l2即r1+1）
void merge(int a[],int l1,int r1,int l2,int r2){
    int i=l1,j=l2;
    int temp[maxn],index=0;
    while(i<=r1&&j<=r2){
        if(a[i]<=a[j]) temp[index++]=a[i++];
        else temp[index++]=a[j++];
    }
    while(i<=r1) temp[index++]=a[i++];
    while(j<=r2) temp[index++]=a[j++];
    for(int i=0;i<index;i++){
        a[l1+i]=temp[i]; //将合并之后的序列赋回给a
    }
}

//将a数组当前区间[left,right]进行归并排序
void mergeSort(int a[],int left,int right){
    if(left<right){
        int mid=left+(right-left)/2;
        mergeSort(a,left,mid); //递归，将左区间归并排序
        mergeSort(a,mid+1,right);  //递归，将右区间归并排序
        merge(a,left,mid,mid+1,right); //将左右子区间合并
    }
}

非递归实现

主要要考虑到每次分组的时候组内元素个数上限都是2的幂次，令步长step的初值为2，然后将数组中每step个元素作为一组，对其内部排序（即在长度为step的子组中，将左step/2和右step/2个元素合并，若元素个数不超过step/2则不操作），再令step*2，反复操作直到step/2>n，代码如下

void mergeSort(int a[]){
    //step为组内元素个数，step/2为左子区间元素个数，注意等号可以不取
    for(int step=2;step/2<n;step*=2){
        //每step个元素一组
        for(int i=1;i<=n;i+=step){ //对于每一组
            int mid=i+step/2-1; //元素个数为step/2
            if(mid+1<=n){
                merge(a,i,mid,mid+1,min(n,i+step-1));
            }
        }
    }
}

4.6.3 快速排序

快速排序时间复杂度为O(nlogn)，其实现需要先解决一个问题：对于一个序列a[]，调整序列中元素的位置，使得a[0]（原序列中的a[0]，下同）左侧的所有元素都小于等于a[0]，右侧的所有元素都大于a[0]。

由于显然存在很多方案，下面给出一种使用two pointers实现的做法，也是最快的方法

先将a[0]存入temp，定义left=0，right=len-1
right一直左移，直到a[right]≤a[0]，就将a[right]指向的元素挪到left处（比如考虑第一次，第一次的时候a[1]被挪走了，可以认为那个地方是空的，那么就可以直接把a[right]指向的元素赋给left处）；之后left一直右移，直到a[left]>a[0]，再把a[left]处的元素赋给right处（因为可以认为之前的right处赋给了之前的left处，那个地方已经空了）；如此交替进行
直到right=left，再把temp赋给这个地方，则完成

一般化考虑left的初值就是划分区间的点，将划分区间的元素a[left]称之为主元

代码实现

int Partition(int a[],int left,int right){
    int temp=a[left];
    while(left<right){
        while(left<right&&a[right]>=temp) right--; //注意这里还要同时满足left<right，这样才能保证外层循环结束时一定有left=right
        a[left]=a[right];
        while(left<right&&a[left]<temp) left++;
        a[right]=a[left];
    }
    a[left]=temp;
    return left; //返回相遇的下标
}

接下来就可以实现快速排序算法了，其思路是：

调整序列中的元素，使当前序列最左端的元素在调整后满足左侧所有元素均不超过该元素、右侧所有元素均大于该元素
对该元素的左侧和右侧分别递归进行1.的调整，直到当前调整区间的长度不超过1

递归实现如下

//快速排序，left与right初值为序列首尾下标
void quickSort(int a[],int left,int right){
    if(left<right){ //当前区间的长度超过1
        //将区间[left,right]按照a[left]一分为二
        int pos=Partition(a,left,right);
        quickSort(a,left,pos-1);
        quickSort(a,pos,right);
    }
}

但是会有一个缺陷：只有序列中的元素排列比较随机的时候效率最高。当序列中元素接近有序的时候会达到最坏时间复杂度O($\mathrm{n}^2$)，产生这种情况的主要原因在于主元没有把当前区间划分为两个长度接近的子区间。解决这个问题的方法之一是随机选择主元，即从[left,right]中随机选择一个数作为主元，这样能保证对于任意输入数据的期望时间复杂度都能达到O(nlogn)

下面来看看如何生成随机数

#include<bits/stdc++.h>
#include<time.h>
int random(int a, int b)
{
    srand((unsigned)time(NULL));
    return ((rand() % (b-a+1)) + a);
}

当b-a>RAND_MAX时，可以这样：

int random(int a,int b){
    srand((unsigned)time(NULL));
    //用rand()生成一个在[0,RAND_MAX]范围内的随机数，除以RAND_MAX得到一个[0,1]之间的浮点数再乘以b-a再+a即可
    return (int)(round(1.0*rand()/RAND_MAX*(b-a)+a));
}

在此基础上继续讨论随机快速排序的写法

int randPartition(int a[],int left,int right){
    int p=(int)(round(1.0*rand()/RAND_MAX*(right-left))+left);
    swap(a[p],a[left]); //交换主元
    //之后一模一样
    int temp=a[left];
    while(left<right){
        while(left<right&&a[right]>=temp) right--; //注意这里还要同时满足left<right，这样才能保证外层循环结束时一定有left=right
        a[left]=a[right];
        while(left<right&&a[left]<temp) left++;
        a[right]=a[left];
    }
    a[left]=temp;
    return left; //返回相遇的下标
}

//quickSort函数无需做出任何改变

4.7 其他高效技巧与算法

4.7.1 打表

打表：以空间换时间。一般是指把所有可能需要用到的结果事先计算出来，这样后面用到时就可以直接查表获得。打表的方式有以下几种：

在程序中一次性计算出所有可能需要用到的结果事先计算出来，之后的查询直接取这些结果

这个最常用。比如一个问题里面需要大量查询斐波那契数F(n)，每查询一次时间复杂度就是O(n)，查询Q次时间复杂度就是O(Qn)，而如果预先先把给定范围内的斐波那契数全部计算出来，那么每次查询就是O(1)的复杂度，Q次查询就是O(Q+n)，n为预处理时间
在另一个程序中分一次或者多次计算出来需要用到的结果，手工把结果打到需要用程序的数组中，然后在这个程序里直接使用
对于一些感觉不会的题目，先用暴力程序计算小范围数据的结果，然后找规律

4.7.2 活用递推

细心考虑题目中是否存在递推关系。例如就一类涉及序列的问题而言，假如序列的每一位所需要计算的值都可以通过该位左右两侧的结果来计算得到，那么就可以考虑所谓的“左右两侧的结果”是否可以通过递推进行预处理来得到，这样在后面的使用中就可以不必反复求解

【PAT A1093/B1040】有几个PAT

字符串APPAPT包含了两个"PAT"，位数：2+4+6和3+4+6，现在给定一个字符串，问一共可以形成多少个PAT？

输入格式：

一行包含一个字符串，长度不超过$10^5$

输出格式：

输入包含多少个PAT，结果可能比较大，输出对1000000007取余的结果

思路：直接暴力会超时，可以这样分析：

对于每一个确定的A，可以形成的PAT的数量=A左边的P的数量*A右边的T的数量，那么问题转化成求每个A左侧P和右侧T的数量

一个比较快的获得每一位左边P的个数的方法：设定一个数组leftNumP，先memset为0，然后如果下标i处为P，那么就有leftNumP[i]=leftNumP[i]+1，如果不是那么就有leftNumP[i]=leftNumP[i]，由此可以在时间复杂度为O(len)内求出

求每一位右边的T也是同理的，但是可以在求出T的同时把ans也求出来，定义int rightNumT，表示遍历到当前的位置的时候这个位置右边的T的数量。如果当前位置是T那么rightNumT++，如果当前位置是A那么ans=(ans+leftNumP[i]*rightNumT)%MOD

4.7.3 随机选择算法

本节主要讨论这个问题：如何从一个无序的数组中求出第K小的数（假设数组中的数两两不同）

如果直接快排，时间复杂度是O(nlogn)，但是存在更优的随机选择算法，对于任何输入都可以达到O(n)的期望时间复杂度。

其原理比较类似于随机快速排序中的randPartition函数，分析这个函数：

当这个函数执行完一遍之后，假设被选择到的主元为a[p]，那么主元左右两侧的元素个数就是确定的（设p为已知），即a[p]是[left,right]中第p-left+1小的数。

不妨设p-left+1=M，则当K==M时，第K小的数就是a[p]，

当K<M时，第K小的数在主元左侧，即第K小的数是[left,p-1]中的第K大，往左侧递归即可

当K>M时，第K小的数在主元右侧，即第K小的数是[p+1,right]中的第K-M大，往右侧递归即可

分析：算法可以以left=right为递归边界，返回a[left]，代码实现如下

//随机选择算法，返回[left,right]中第k小的数
int randSelect(int a[],int left,int right,int k){
    if(left==right) return a[left]; //递归边界
    int p=randPartition(a,left,right);
    int m=p-left+1;
    if(left<right&&k==m) return a[p];
    else if(left<right&&k<m) return randSelect(a,left,p-1,k);
    else if(left<right&&k>m) return randSelect(a,p+1,right,k-m); 
}

这个算法对于任意输入的期望时间复杂度均为O(n)

下面给出一个应用的例题

给定一个由整数组成的集合，集合中的整数两两不同，现在需要将它分为两个子集合，使得这两个子集合的并为原集合，交为空集。同时在两个子集合元素个数之差的绝对值$|n_1-n_2|$的绝对值尽可能小的情况下，要求它们各自的元素之和的差的绝对值$|S_1-S_2|$尽可能大，求这个$|S_1-S_2|$等于多少

可以分成两类：当n为偶数时，显然有$n_1=n_2=\frac{n}{2}$；n为奇数时，不妨取$n_1=\frac{n}{2}+1,n_2=\frac{n}{2}$（均为向下取整）

为了使得$|S_1-S_2|$尽可能大，显然应当把原集合从小到大排，前$n_1$个的和为$S_1$，后$n_2$的和为$S_2$

但是如果要把整个序列排序时间复杂度是O(nlogn)，我们可以优化成O(n)。这里我们可以考虑使用随机选择算法

只需要使用randSelect函数求出第$\frac{n}{2}$大的数即可，函数会自动切分好两个集合，然后让i从0遍历到n/2求和即可。

4.7.4 前缀和

int main(){
  vector<int> preFix(n);
  for(int i=0;i<n;++i){
    if(i==0) preFix[i]+=a[i];
    preFix[i]=preFix[i-1]+a[i];
  }
}

c++系统库中也有一个库函数partial_sum

代码CPP · 18 行

#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5};
    std::vector<int> result(arr.size());  // 存储部分和的容器

    // 计算部分和并存储到 result
    std::partial_sum(arr.begin(), arr.end(), result.begin());

    // 输出结果
    for (int num : result) {
        std::cout << num << " ";
    }

    return 0;
}

第5章入门篇（3）——数学问题

5.1 简单数学

【PAT B119/A1069 数字黑洞】

代码CPP · 39 行

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

void to_array(int a[],int b){
    for(int i=0;i<4;i++){
        a[i]=b%10;
        b/=10;
    }
}

int to_number(int a[]){
    int b=0;
    for(int i=0;i<4;i++){
        b=b*10+a[i];
    }
    return b;
}

bool cmp(int a,int b){
    return a>b;
}

int main(){
    int n;
    cin>>n;
    int ans,a1,a2;
    int t[5];
    while(ans!=6174){
        to_array(t,n);
        sort(t,t+4);
        a1=to_number(t);
        sort(t,t+4,cmp);
        a2=to_number(t);
        ans=a2-a1;
        n=ans;
        printf("%04d-%04d=%04d\n",a2,a1,ans);
    }
}

5.2 最大公约数和最小公倍数

5.2.1 最大公约数

基于欧几里得算法（辗转相除法）

gcd(a,b)=gcd(b,a%b)

上式可以看成递归式

又有递归边界gcd(a,0)=a

代码实现

int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
或者
int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}

5.2.2 最小公倍数

先求最大公约数d=gcd(a,b)，则有最小公倍数为$\frac{a}{d}*b$

5.3 分数的四则运算

5.3.1 分数的表示和化简

1.分数的表示

struct Fraction{
    int up,down;
};

其中需要对这种表示指定三项规则：

使down为非负数，如果分数为负则令up为负数
如果分数为0则令up=0,down=1
分子和分母互素

2.分数的化简

主要用来使Fraction变量满足分数的三项规定

Fraction reduction(Fraction result){
    if(result.down<0){ //满足第一条规定
        result.up=-result.up;
        result.down=-result.down;
    }
    if(result.up==0) result.down=1; //满足第二条规定
    else{ //满足第三条规定
        int d=gcd(abs(result.up),abs(result.down));
        result.up/=d;
        result.down/=d;
    }
    return result;
}

5.3.2 分数的四则运算

1.2.3.4 加减乘除

大同小异。就通分死算，记得最后返回return reduction(result)

5.3.3 分数的输出

先化简
如果f.down=1，直接输出up
带分数的输出：整数部分为r.up/r.down，分子部分为abs(r.up)%r.down，分母为r.down

由于分数的乘法和除法的过程中可能使分子或分母超过int型表示范围，因此一般情况下分子和分母使用long long来存储

5.4 素数

5.4.1 素数的判断

bool isPrime(int n){
    if(n<=1) return false;
    int sqr=(int)sqrt(1.0*n); //在n前面乘上1.0使之变为浮点型
    for(int i=2;i<=sqr;i++){
        if(n%i==0) return false;
    }
    return true;
}

如果n比较小（i^2没有解决int类型上线）也可以这样写

bool isPrime(int n){
    if(n<=1) return false;
    for(int i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}

5.4.2 素数表的获取

暴力法复杂度为O($n \sqrt n$)，下面介绍效率更高的两种筛法

//埃氏筛法：从2开始，将每个质数的倍数都标记成合数，以达到筛选素数的目的
int visit[maxn];  //maxn是需要打的素数表（布尔数组）
void Prime(){
    memset(visit,0,sizeof(visit)); //初始化都是素数，如果是素数的话就是1，不是素数才是0
    for (int i = 2; i < maxn; i++) { //注意不能写成i<=maxn
        if (!visit[i]) {         //如果i是素数，让i的所有倍数都不是素数
            for (int j = i+i; j < maxn; j += i) { 
                visit[j] = 0;
            }
        }
    }
}

时间复杂度为O(nloglogn)

原理：从小到大到达某数a时，假如a还没有被前面的步骤筛去，那么a一定是素数。因为假设a不是素数，那么a必有小于a的因子，那么a一定会在之前的步骤中被筛掉

代码CPP · 18 行

//欧拉筛法：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。
bool visit[maxn+5]; //1表示是素数，0表示不是素数
int prime[maxn+5]; //需要打的素数表
int cnt;
void findPrime(){
    memset(visit,1,sizeof(visit));
    for(int i=2;i<maxn;i++){
        if(visit[i]){
            prime[cnt++]=i;
        }
        //遍历已知的素数来标记合数
        for(int j=0;j<cnt&&i*prime[j]<maxn;j++){
            //循环条件保证遍历的是已知的素数，以及标记的合数不超过maxn
            visit[i*prime[j]]=0;
            if(i%prime[j]==0) break; //看下文
        }
    }
}

当 i % prime[j] == 0 时，说明 i可以被 prime[j] 整除，即 i=k×prime[j]。
此时，i 乘上更大的素数的结果（如 i * prime[j+1]）一定会被 prime[j] 的倍数筛掉。（这里break之后，之后i增大总会到达一个程度使得i是原来时候的i的倍数）
例如，当 i=4时：
- prime[j] = 2，i * prime[j] = 8。
- 因为 4 % 2 == 0，所以 4 * 3 = 12 会被 2 的倍数筛掉（即 6 * 2 = 12，i=6的时候就可以筛掉了）。
- 因此，不需要继续标记 4 * 3 = 12，直接跳出循环。

5.5 质因子分解

最后都要归结到若干不同质数的乘积，所以不妨先打个素数表，而打素数表的方法见上文。

由于每个质因子可能不止出现一次，可以定义一个结构体来存放一个数的质因子

struct Factor{
    int x,cnt;
    //x为质因子，cnt为其数目
}fac[10];

这里fac[]数组是存放给定的正整数n的所有质因子，比如对于n=20=2*2*5

fac[0].x=2
fac[0].cnt=2
fac[1].x=5
fac[1].cnt=1

由于$23571113171923*29>\mathrm{INT_MAX}$，fac[]开到10就足够了

我们不难注意到这样一个性质：对于一个合数n，它的质因子要么全部小于等于$\sqrt n$，要么只有一个质因子大于$\sqrt n$，其余的质因子全部小于等于$\sqrt n$

利用这样的性质我们可以对一个合数n进行质因数分解

首先在素数表中，枚举2~$\sqrt n$的所有素数，试是不是n的质因子

如果是的话就在fac数组中加入这个因子，然后反复除，每除一次cnt++
如果在上面的操作之后n仍然大于1，说明n有且仅有一个大于$\sqrt n$的质因子，而且就是就是现在的n

至此质因数分解完成，时间复杂度为O($\sqrt n$)

代码实现

代码CPP · 23 行

struct Factor{
    int x,cnt=0;
}fac[10];

int main(){
    int n;
    int cnt=0;
    int prime[100];
    int temp=n; //要在外部用n
    for(int i=2; prime[i]<=sqrt(temp);i++){
        if(n%prime[i]==0){
            fac[cnt].x=prime[i];
            while(n%prime[i]==0){
                fac[cnt].cnt++;
                n/=prime[i]; //注意这两个语句的顺序
            }
        }
    }
    if(n>1){
        fac[cnt++].x=n;
        fac[cnt].cnt=1;
    }
}

下面来看一道例题

【PAT A1059】 Prime Factors

给出一个int范围的整数，按照从小到大的顺序输出其分解为质因数的乘法形式

输入样例

97532468

输出样例

97532468=2^2*11*17*101*1291

代码实现

代码CPP · 58 行

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

const int maxn=100005;

struct Factor{
    int x,cnt=0;
}fac[10];


int prime[maxn],cnt;
int t[maxn]={0}; //0表示是素数，1表示不是素数
void findPrime(){
    for(int i=2;i<maxn;i++){
        if(!t[i]){
            prime[cnt]=i;
            cnt++;
            for(int j=i+i;j<maxn;j+=i){
                t[j]=1;
            }
        }
    }
}

int main(){ 
    int n;
    cin>>n;
    if(n==1){
        cout<<"1=1";
        return 0;
    }
    findPrime();
    int temp=n;
    int num=0;
    for(int i=0;prime[i]<=sqrt(1.0*temp);i++){
        if(n%prime[i]==0){
            fac[num].x=prime[i];
            while(n%prime[i]==0){
                fac[num].cnt++;
                n/=prime[i];
            }
            num++;
        }
    }
    if(n>1){
        fac[num].x=n;
        fac[num].cnt++;
        num++;
    }
    cout<<temp<<'=';
    for(int i=0;i<num;i++){
        if(i!=0) cout<<'*';
        if(fac[i].cnt==1) cout<<fac[i].x;
        else cout<<fac[i].x<<'^'<<fac[i].cnt; 
    }
    return 0;
}

易错点总结：

在INT_MAX范围内分解，素数表开到10^5就够了
n==1特判
main函数开头调用findPrime()
findPrime函数中不要写成i<=maxn是i<maxn
要在循环外定义变量储存sqrt(n)

5.6 大整数运算（高精度）

代码CPP · 263 行

#include <iostream>
#include <cstring>
using namespace std;

class BigInt
{
private:
    static constexpr int N = 1000; // 位数上限
public:
    int a[N]; // 低位在前，高位在后

    // 默认构造函数，支持 int 初始化
    BigInt(int x = 0) : a{}
    {
        for (int i = 0; x; i++)
        {
            a[i] = x % 10;
            x /= 10;
        }
    }

    // 复制构造函数
    BigInt(const BigInt &b)
    {
        memcpy(a, b.a, sizeof(a));
    }

    // 赋值运算符
    BigInt &operator=(const BigInt &b)
    {
        if (this != &b)
        {
            memcpy(a, b.a, sizeof(a));
        }
        return *this;
    }

    // 加法（BigInt + BigInt）
    BigInt operator+(const BigInt &x) const
    {
        BigInt res = *this;
        res += x;
        return res;
    }

    // 加法（BigInt += BigInt）
    BigInt &operator+=(const BigInt &x)
    {
        for (int i = 0; i < N; i++)
        {
            a[i] += x.a[i];
            if (a[i] >= 10)
            {
                a[i + 1] += a[i] / 10;
                a[i] %= 10;
            }
        }
        return *this;
    }

    // 减法（BigInt - BigInt）
    BigInt operator-(const BigInt &x) const
    {
        BigInt res = *this;
        res -= x;
        return res;
    }

    // 减法（BigInt -= BigInt）
    BigInt &operator-=(const BigInt &x)
    {
        for (int i = 0; i < N; i++)
        {
            a[i] -= x.a[i];
            if (a[i] < 0)
            {
                a[i] += 10;
                a[i + 1] -= 1;
            }
        }
        return *this;
    }

    // 乘法（BigInt * int）
    BigInt operator*(int x) const
    {
        BigInt res = *this;
        res *= x;
        return res;
    }

    // 乘法（BigInt *= int）
    BigInt &operator*=(int x)
    {
        for (int i = 0; i < N; i++)
        {
            a[i] *= x;
        }
        for (int i = 0; i < N - 1; i++)
        {
            a[i + 1] += a[i] / 10;
            a[i] %= 10;
        }
        return *this;
    }

    // 乘法（BigInt * BigInt）
    BigInt operator*(const BigInt &x) const
    {
        BigInt res;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j + i < N; j++)
            {
                res.a[i + j] += a[i] * x.a[j];
                if (res.a[i + j] >= 10)
                {
                    res.a[i + j + 1] += res.a[i + j] / 10;
                    res.a[i + j] %= 10;
                }
            }
        }
        return res;
    }

    // 取模（BigInt % int）
    int operator%(int x) const
    {
        int remainder = 0;
        for (int i = N - 1; i >= 0; i--)
        {
            remainder = (remainder * 10 + a[i]) % x;
        }
        return remainder;
    }

    // 除法（BigInt /= int）
    BigInt &operator/=(int x)
    {
        for (int i = N - 1; i >= 0; i--)
        {
            if (i)
            {
                a[i - 1] += (a[i] % x) * 10;
            }
            a[i] /= x;
        }
        return *this;
    }

    // 比较运算（BigInt == BigInt）
    bool operator==(const BigInt &x) const
    {
        for (int i = 0; i < N; i++)
        {
            if (a[i] != x.a[i])
                return false;
        }
        return true;
    }
    // 比较运算（BigInt < BigInt）
    bool operator<(const BigInt &x) const
    {
        for (int i = N - 1; i >= 0; i--)
        {
            if (a[i] < x.a[i])
                return true;
            if (a[i] > x.a[i])
                return false;
        }
        return false;
    }
    // 比较运算（BigInt > BigInt）
    bool operator>(const BigInt &x) const
    {
        return x < *this;
    }
    // 比较运算（BigInt <= BigInt）
    bool operator<=(const BigInt &x) const
    {
        return !(x < *this);
    }
    // 比较运算（BigInt >= BigInt）
    bool operator>=(const BigInt &x) const
    {
        return !(*this < x);
    }
    // 一元负号（取反运算）
    BigInt operator-() const
    {
        BigInt res = *this;
        for (int i = 0; i < N; i++)
        {
            res.a[i] = -res.a[i];
        }
        return res;
    }
    // 括号运算符（获取某个位数）
    int operator()(int index) const
    {
        if (index < 0 || index >= N)
            return -1; // 返回 -1 代表超出范围
        return a[index];
    }


    // Pre-increment (++obj)
    BigInt& operator++() 
    {
        *this += BigInt(1);
        return *this;
    }

    // Post-increment (obj++)
    BigInt operator++(int) 
    {
        BigInt temp = *this; 
        ++(*this);
        return temp;
    }

    // Pre-decrement (--obj)
    BigInt& operator--() 
    {
        *this -= BigInt(1); 
        return *this;
    }

    // Post-decrement (obj--)
    BigInt operator--(int) 
    {
        BigInt temp = *this;
        --(*this);
        return temp;
    }
    
    // 输出运算符
    friend ostream &operator<<(ostream &o, const BigInt &b)
    {
        int t = N - 1;
        while (t > 0 && b.a[t] == 0)
        {
            t--;
        }
        for (int i = t; i >= 0; i--)
        {
            o << b.a[i];
        }
        return o;
    }
    // 输入运算符
    friend istream &operator>>(istream &in, BigInt &b)
    {
        string s;
        in >> s;
        memset(b.a, 0, sizeof(b.a));
        for (int i = 0; i < s.size(); i++)
        {
            b.a[i] = s[s.size() - 1 - i] - '0';
        }
        return in;
    }
};

5.7 扩展欧几里得算法

待填坑

5.8 组合数

待填坑

第6章 C++标准模板库(STL)介绍

6.1 vector的常见用法详解

定义方式举例

vector<int> name;
vector<char> name;
vector<vector<int> > name; //两个>>之间加上空格以防止被识别成移位操作
//这个可以理解成两个维度都可以变成的二维数组

定义vector数组的方式

vector<int> arr[100]; //这种定义方式就是一维的长度被固定成100了

vector容器内元素的访问

通过下标访问

就类似普通的数组

通过迭代器访问

迭代器(iterator)可以理解成一种类似指针的东西

vector<typename>::iterator it; //it是一个vector<typename>::iterator型的变量

这样就得到了迭代器it，并且可以通过*it来访问vector中的元素，举例如下

vector<int> vi;
for(inti=1;i<=5;i++){
    vi.push_back(i); //push_back(i)在vi的末尾添加元素i，即依次添加1 2 3 4 5
}

可以使用类似下标和指针访问数组的方式来访问容器中的元素

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> vi;
    for(int i=1;i<=5;i++){
        vi.push_back(i);
    }
    //vi.begin()为取vi的首元素地址，而it指向这个地址
    vector<int>::iterator it=vi.begin();
    for(int i=0;i<5;i++){
        printf("%d ",*(it+i));
    }
    return 0;
}

这里可以看出vi[i]==*(vi.begin()+i)
再提一下end()函数：取尾元素地址的下一个地址，end()作为迭代器末尾标志不存储任何元素。（美国人思维习惯左闭右开）

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> vi;
    for(int i=1;i<=5;i++){
        vi.push_back(i);
    }
    //vector的迭代器不支持it<vi.end()的元素，循环条件只能用it!=vi.end()
    for(vector<int>::iterator it=vi.begin();it!=vi.end();it++){
        printf("%d ",*it);
    }
    return 0;
}

强调一下，STL容器中只有在vector和string中才允许vi.begin()+3这种迭代器带上整数的写法

vector常用函数实例解析

push_back()

在vector后面增加一个元素(x),时间复杂度O(1),实例见上文

pop_back()

直接使用不需要传参,用以删除vector的尾元素,时间复杂度O(1)

size()

用以获取vector中元素的个数,返回值unsigned不过一般用%d就可以了，时间复杂度O(1)

clear()

清空vector中的所有元素，时间复杂度O(N),N为vector中元素个数

insert()

insert(it,x)用以向vector的任意迭代器it处插入一个元素x，时间复杂度O(N)

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> vi;
    for(int i=1;i<=5;i++){
        vi.push_back(i);
    }
    vi.insert(vi.begin()+2,-1);
    for(int i=0;i<vi.size();i++){
        printf("%d ",vi[i]);
    }
    return 0;
}

引用是的，对于 std::vector<int> vi 而言，vi + i == vi[i] 并不成立。原因分析 vi[i] 的含义： vi[i]...

是的，对于 std::vector<int> vi 而言，vi + i == vi[i] 并不成立。

原因分析
vi[i] 的含义：
vi[i] 是 std::vector 提供的操作符重载，用于访问向量中索引为 i 的元素。其底层实现相当于：
*(vi.begin() + i)
其中 vi.begin() 是一个指向 vi 开头元素的迭代器，而迭代器支持偏移。
vi + i 的含义：

vi 是 std::vector 类型的对象，不是指针或迭代器。C++ 中不允许直接对对象使用加法运算，因此 vi + i 是非法的，会导致编译错误。
正确用法

如果想通过指针或迭代器实现类似 vi[i] 的效果，应该使用 vi.begin() 或指针加偏移量。例如：
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> vi = {10, 20, 30, 40};
    
    // 使用下标访问
    cout << vi[2] << endl;  // 输出：30

    // 使用迭代器
    auto it = vi.begin();
    cout << *(it + 2) << endl;  // 输出：30

    return 0;
}
对比：普通数组中的 arr + i == arr[i]

对于普通数组（如 int arr[5]），arr 是指向数组首元素的指针，因此 arr + i 是合法的，指向数组第 i 个元素的地址。而 arr[i] 其实是通过指针偏移访问到值的语法糖，其本质是 *(arr + i)。

结论

在 std::vector 中：

vi[i] 是通过索引访问元素的合法操作。

vi + i 是非法的，因为 vi 是一个对象而不是指针。如果需要实现类似 vi[i] 的操作，应使用迭代器或下标索引。

erase()

有两种用法：删除单个元素，删除一个区间内的所有元素，时间复杂度均为O(N)

删除单个元素
erase(it)即删除迭代器处的元素

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> vi;
    for(int i=1;i<=5;i++){
        vi.push_back(i); //1 2 3 4 5
    }
    vi.erase(vi.begin()+1); //删除2 不是vi.begin()+1因为*(vi.begin())==vi[0]
    for(int i=0;i<vi.size();i++){
        printf("%d ",vi[i]);
    }
    return 0;
}

删除一个区间之内的所有元素
erase(first,last)即删除[first,last)内的所有元素
由此可见vi.clear()等价于vi.erase(vi.begin(),vi.end())

6.2 set的常见用法详解

set，也就是集合，是一个内部自动有序而且不含重复元素的容器

set的定义

set<typename> name;

类似vector,或者说绝大部分STL的定义方式都是这样的

set容器内元素的访问

set只能通过迭代器访问

set<int>::iterator it;

除vector和string以外的STL容器都不支持*(it+i)的访问方式所以只能这样枚举

#include <bits/stdc++.h>
using namespace std;
int main(){
    set<int> st;
    st.insert(2);
    st.insert(1);
    st.insert(3);
    st.insert(1);
    //不支持it<st.end()
    for(set<int>::iterator it=st.begin();it!=st.end();it++){
        cout<<*it;
    } //要理解迭代器，不是针对一个对象，而是这个类中的一种数据类型
    return 0;
}

输出结果

1 2 3

由此可见set内的元素自动升序排序而且自动去除重复元素

set常用函数实例解析

insert()

会有自动递增排序和去重，时间复杂度O(logN)

find()

find(value)返回set中对应值为value的迭代器，时间复杂度O(logN)

#include <bits/stdc++.h>
using namespace std;
int main(){
    set<int> st;
    st.insert(2);
    st.insert(1);
    st.insert(3);
    st.insert(1);
    set<int>::iterator it=st.find(2);
    cout<<*it<<endl; //输出2
    return 0;
}

如果查找不到就会返回st.end()，可以用这个功能搭配set实现复杂的hash

erase()

- st.erase(it) 删除单个元素(对应迭代器处的)，可以结合find函数来使用时间复杂度为O(1)
- st.erase(value) 删除单个元素(值为value的) 时间复杂度为O(logN)
- 为什么可以这样？因为value的类型是typename，而it的类型是set::iterator
删除一个区间之内的所有元素 st.erase(first,last)，其中first和last都是迭代器，时间复杂度为O(last-first)

size()

略了，O(1)

clear()

O(N)

6.3 string的常见用法详解

string的定义

string str;
string str1="abcd";

string中内容的访问

通过下标访问

就像访问字符数组那样去访问string

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str="abcd";
    for(int i=0;i<str.length();i++){
        printf("%c", str[i]); //输出abcd
    }
    return 0;
}

如果要读入和输出整个字符串那就只能用cin和cout

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin>>str;
    cout<<str;
    return 0;
}

不过真的要使用printf也可以使用c_str()强转

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str="abcd";
    printf("%s\n", str.c_str());
    return 0;
}

通过迭代器访问

主要是有些函数比如insert()和erase()要求迭代器为参数
由于定义string的时候并没有<typename>这一项，因此可以直接这样定义

string::iterator it;

那么就可以使用迭代器来对string进行遍历了

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str="abcd";
    for(string::iterator it=str.begin();it!=end();it++){
        cout<<*it;
    }
    return 0;
}

这里循环条件也可以写成it<str.end()，因为只有vector和string支持这样的对迭代器比如str.begin()+3直接加减某个数字的操作

string常用函数实例解析

operator+=

可以把两个string直接拼接起来

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str1="abc",str2="xyz",str3;
    str3=str1+str2;
    cout<<str3; //abcxyz
}

compare operator

两个string类型直接用比较运算符比较大小，依据是字典序

if(str1>str2){

}

length() 或 size()

str.length();
str.size();

均返回string的长度且基本相同，时间复杂度O(1)

insert()

string的insert()函数有多种写法，时间复杂度均为O(N)

insert(pos,string),在pos号位置插入字符串string
这个pos号位可以是0

string str1="abc",str2="opq";
str1.insert(3,str2); //往str[3]处插入opq，这里也可以直接写"opq"
cout<<str1<<endl; //abcopq

insert(it,it2,it3), it为原字符串的欲插入位置，it2和it3为待插入字符串的首尾迭代器，用以表示[it2,it3)将被插入it的位置上

string str1="abc",str2="opq";
str.insert(str.begin(),str2.begin,str2.end());
cout<<str1<<endl; //abcopq

erase()

时间复杂度均为O(N)

删除单个元素

str.erase(it);

删除一个区间内的所有元素两种方法
- str.erase(first,last) 均为迭代器
- str.erase(pos,length) pos为起始位置(不是迭代器),length为删除的字符个数
```
string str="abcdefg";
str.erase(3,2); //删除c和d，从第三位开始的两个(包括第三位)
```
这个pos号位可以是0

clear()

O(1)

substr()

substr(pos,len)返回从pos号位开始、长度为len的子串，时间复杂度为O(len)，示例如下、

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str="Thank you for your smile.";
    cout<<str.substr(0,5)<<endl; //Thank
    cout<<str.substr(14,4)<<endl; //Your
}

这个pos号位可以是0

string::npos

string::npos是一个常数其本身的值为-1，但是由于其本身是unsigned_int类型，也可以认为是unsigned_int类型的最大值。string::npos作为find函数失配时候的返回值，可以认为string::npos=-1或4294967295

find()

str.find(str2),当str2是str的子串的时候，返回其在str中第一次出现的位置（不是迭代器）；如果str2不是str的子串，返回string::npos
str.find(str2,pos)从pos位开始匹配str2，返回值与上面的相同时间复杂度O(mn)，m和n分别是两个数组的长度


using namespace std;
int main{
string str ="Thank you for your smile."
string str2 "you";
string str3 "me";
if (str.find (str2) string!=npos)
cout << str.fånd (str2) << endl;
if (str.find(str2, 7) String:!=npos) (
cout str.find (str2, 7) endl;
if (str. find (str3) String:!=npos)
cout << Str. find(str3) endl;
) else {
cout "I know there is no position for me." << endl;}
return O;
}

输出结果

6
14
I know there is no position for me.

replace()

str.replace(pos,len,str2)将str从pos号位开始、长度为len的子串替换为str2
str.replace(it1,it2,str2)把str的迭代器[it1,it2)范围内的子串替换为st2
时间复杂度为O(str.length())

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str="Maybe you will turn around";
    string str2="will not";
    string str3="surely";
    cout<<str.replace(10,4,str2)<<endl;
    cout<<str.replace(str.begin(),str.begin()+5,str3);
    return 0;
}

输出

Maybe you will not turn around
surely you will not turn around

c.str()

可以将string转换成char []，之后就可以使用sprintf和sscanf函数了。

sscanf(login_date.c_str(),"%d-%d",&year,&month);

PAT A1060 ARE THEY EQUAL

6.4 map的常用用法详解

map翻译为映射(其实这里只能是一个单射),比如数组 typename arr[]就是int类型向其他类型的一个映射，但是map可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器）,比如string到int的映射

map的定义

map<typename1,typename2> mp;

前一个是映射前类型(键key)，后一个是映射后类型(value)
如果是字符串到整型的映射，必须使用string而不能使用char数组

map<string,int> mp;

这是因为char作为数组是不能作为键值的，所以只能使用string
也有这样的map

map<set<int>,string> mp;

map容器内元素的访问

map有两种访问方式

通过下标访问

和访问普通的数组的方式一样，比如对于一个定义为

map<char,int> mp;

的map来说，就可以使用

mp['c']

的方式来访问它的对应的int
但是需要注意，和函数一样，map中的键是唯一的，比如

map<char,int> mp;
mp['c']=20;
mp['c']=30; //20被覆盖
cout<<mp['c']; //输出30

通过迭代器访问

map<typename1,typename2>::iterator it;

由于map的每一对映射都有两个typename，因此一个it必须可以同时访问键和值

it->first //访问键
it->second //访问值

比如下面这个例子

int main(){
    map<char,int> mp;
    mp['m']=20;
    mp['r']=30;
    mp['a']=40;
    for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++){
        printf("%c %d\n",it->first,it->second);
    }
    return 0;
}

输出如下：

a 40
m 20
r 30

其实由此可见，map会按照键从小到大的顺序自动排序（因为a<m<r）,这个就是类似set的（因为他的底层原理和set一样都是红黑树）

map常用函数实例解析

find()

find(key)返回键为key的映射的迭代器,时间复杂度O(logN),N为map中映射的个数

map<char,int> mp;
mp['a']=1;
mp['b']=2;
map<char,int>::iterator it=mp.find('b');
printf("%c %d", it->first,it->second);

输出结果为

b 2

erase() 可以类比set的学习

删除单个元素
- mp.erase(it),it为需要删除的元素的迭代器，时间复杂度O(1)，可以搭配find()函数使用
```
map<char,int> mp;
mp['a']=1;
mp['b']=2;
map<char,int>::iterator it=mp.find('b');
mp.erase(it); //删除b 2
```
- mp.erase(key),key为欲删除的映射的键,时间复杂度O(logN)
```
map<char,int> mp;
mp['a']=1;
mp['b']=2;
mp.erase('b'); //删除b 2
```
删除一个区间之内的所有元素
mp.erase(first,last),传入的都是迭代器,删除[first,last)内的元素,时间复杂度O(last-first)

size()

O(1)，获得映射的对数

clear()

O(N)

常见用途

建立char或者string与int之间的映射
把map当bool数组使用

6.5 queue的常见用法详解

queue的定义

queue <typename> name;

queue容器内元素的访问

由于queue是先进先出的，因此在STL中只能通过front()来访问队首元素或者使用back()来访问队尾元素

#include<bits/stdc++.h>
using namespace std;

int main(){
    queue<int> q;
    for(int i=1;i<=5;i++){
        q.push(i);
    }
    cout<<q.front()<<' '<<q.back(); //输出1 5
}

queue常用函数实例解析

push()

把x推入queue

front() back()

获得队首元素和队尾元素

pop()

令队首元素出队

int main(){
    queue<int> q;
    for(int i=1;i<=5;i++){
        q.push(i);
    }
    for(int i=1;i<=3;i++){
        q.pop(); //弹出1 2 3
    }
    cout<<q.front()<<' '<<q.back(); //输出4 5
}

empty()

返回true则为空，返回false则为非空

size()

返回queue内元素的个数

queue的常见用途

广度优先搜索

需要注意的是使用front()和pop()之前需要使用empty()判断是否为空

6.5+ deque的常见用法详解

deque的定义

类似queue

deque容器内元素的访问

类似queue

deque常用函数

push_back()

在末尾添加元素

push_front()

在前端添加元素

pop_front()和pop_back()

front()和back()

size()和clear()

6.6 priority_queue的常见用法详解

priority_queue又称优先队列，底层使用堆来实现。在优先队列中队首元素一定是当前队列中优先级最大的那一个

例如在队列中有以下元素且指定好了优先级

桃子（优先级3）
梨子（优先级4）
苹果（优先级1）

那么出队的顺序为梨子（优先级4）→桃子（优先级3）→苹果（优先级1）

当然，可以在任何时候往优先队列里push元素，而优先队列底层的数据结构堆(heap)会随时调整结构，使得每次出来的队首元素都是优先级最大的

关于这里的优先级，则是规定出来的，在上面的例子中也可以规定数字越小的优先级越大

priority_queue的定义

priority_queue<typename> name;

priority_queue容器内元素的访问

与queue不一样的是priority_queue没有front()和back()函数，只能通过top()函数来访问队首元素，也就是优先级最高的元素

int main(){
    priority_queue<int> q;
    q.push(1);
    q.push(3);
    q.push(2);
    cout<<q.top(); //输出3
}

priority_queue常见函数实例解析

push()

O(logN)，N为当前元素个数

top()

O(1)

访问堆顶元素

pop()

令队首元素出队

O(logN)

int main(){
    priority_queue<int> q;
    q.push(1);
    q.push(3);
    q.push(2);
    cout<<q.top(); //输出3
    q.pop();
    cout<<q.top(); //输出2
}

empty()

返回true则空，返回false则非空

O(1)

size()

返回优先队列内的元素个数

O(1)

priority_queue内元素优先级的设置

基本数据类型的优先级设置

指的是int double char等可以直接使用的数据类型，优先队列对它们的优先级设置一般是数字大的优先级最高，因此队首元素就是优先队列中元素最大的那个（如果是char类型就是字典序最大的）。

对于基本数据类型来说下面两种优先队列的定义是等价的（以int类型为例）

priority_queue<int> q;
priority_queue<int,vector<int>,less<int> > q; //注意最后两个>之间有空格

vector<int>填写的是用来承载底层数据结构堆(heap)的容器，vector<typename>与之前的typename保持一致
less<int>是对第一个参数的比较类，less<int>表示数字大的优先级越大，而greater<int>表示数字小的优先级越大

因此如果想要优先队列总是把最小的元素放在队首，只需进行如下定义

priority_queue<int,vector<int>,greater<int> > q; //注意最后两个>之间有空格

事实上即使是基本数据类型也可以使用下面讲解的结构体的优先级设置方法，不过三个参数的写法不太一样了。

结构体的优先级设置

以本节开头的水果为例

struct Fruit{
	string name;
	int price;
};

现在希望按水果价格高的为优先级高，就需要重载小于号"<"。重载是指对已有的运算符进行重新定义，也就是说，可以改变小于号的功能，写法示例如下

struct Fruit {
    string name;
    int price;
    friend bool operator < (fruit f1,fruit f2) {
        	return f1.price<f2.price;
	}
};

可见Fruit结构体中增加了一个函数，

其中"friend"为友元，具体含义此处不赘述

后面的bool operator < (fruit f1,fruit f2)对fruit类型的操作符'<'进行了重载

重载运算符的本质是对这一种特定的类型而言，运算符的效果不同了！所以可以定义int double set也是可以的

（重载大于号会造成编译错误，因为从数学上来说只需要重载小于号，即f1>f2等价于判断f2<f1，而f1=f2等价于判断!(f1<f2)&&!(f2<f1)）

函数内部为return f1.price<f2.price，因此重载之后小于号还是小于号的作用，此时就可以直接定义Fruit类型的优先队列，其内部就是以价格高的水果为优先级高，如下

priority_queue<fruit> q;

同理如果想要价格低的水果优先级高，那么就只需要把return中的小于号改为大于号

struct Fruit {
    string name;
    int price;
    friend bool operator < (fruit f1,fruit f2) {
        	return f1.price>f2.price;
	}
};

不难注意到此处对于小于号的重载类似于sort中的cmp函数，的确有点相似。参数都是两个变量，返回值都是bool型，但是效果看上去是“相反”的。在排序中若是return f1.price>f2.price，那么则是从高到低排序，但是在优先队列中却是价格低的优先级高

优先队列的这个函数与sort中的cmp函数的效果是相反的

也可以像sort的cmp函数一样写在结构体外面，只需要把friend去掉，小于号改成一对小括号，然后把重载的函数写在结构体外面，同时将其拿struct包装起来

struct cmp {
    bool operator () (fruit f1,fruit f2){
		return f1.price>f2.price; //价格小的优先级大，仍然与sort的相反
    }
}

这种情况下使用之前说的第二种定义方式来定义优先队列

priority_queue<fruit,vector<fruit>,cmp> q;

应当注意到即使是基本数据类型或者其他STL容器（比如set）也可以这样定义优先级

#include <set>
#include <iostream>
#include <functional>
using namespace std;
int main() {
    // 使用greater定义降序排序的 set
    set<int, greater<int>> s;
    s.insert(10);
    s.insert(5);
    s.insert(20);

    for (int x : s) {
        cout << x << " "; // 输出 20 10 5
    }
    return 0;
}

或者是

代码CPP · 35 行

#include<bits/stdc++.h>

using namespace std;

struct Fruit {
    string name;
    int price;
};

// 自定义比较函数对象
struct cmp {
    bool operator()(const Fruit& f1, const Fruit& f2) const {
        return f1.price > f2.price; // 按价格从大到小排序
    }
};

int main() {
    // 创建一个 set，使用自定义比较函数对象
    set<Fruit, cmp> fruitSet;

    // 添加元素
    fruitSet.insert({"Apple", 5});
    fruitSet.insert({"Banana", 3});
    fruitSet.insert({"Orange", 8});

    // 遍历并输出
    for (const Fruit& fruit : fruitSet) {
        cout << fruit.name << " (" << fruit.price << ")\n";
        // 输出 Orange (8)
        //      Apple (5)
        //      Banana (3)
    }

    return 0;
}

最后指出，如果结构体内的数据较为庞大（例如出现了字符串和数组），建议使用引用来提高效率，此时比较类的参数中需要加上const和&，如下所示

friend bool operator < (const fruit &f1, const fruie &f2){
    return f1.price>f2.price;
}
bool opreator () (const fruit &f1, const fruie &f2) {
    return f1.price>f2.price;
}

priority_queue的常见用途

可以解决一些贪心问题

在使用top()函数之前必须判断优先队列是否为空

6.7 stack的常见用法详解

stack的定义

#include<stack>
stack<typename> name;

typename可以是任何基本数据类型或容器

stack容器内元素的访问

由于stack本身就是一种后进先出的数据结构，在STL中的stack只能通过top()来访问栈顶元素

int main(){
    stack<int> st;
    st.push(1);
    st.push(2);
    cout<<st.top(); //输出2
}

stack常用函数实例解析

push()

O(1) push(x)将x推入栈

top()

O(1) 获得栈顶元素

pop()

O(1) 弹出栈顶元素，示例如下

int main(){
    stack<int> st;
    for(int i=1;i<=5;i++){
        st.push(i); //分别把1 2 3 4 5推入栈中
    }
    for(int i=1;i<=3;i++){
        st.pop(); //相当于推出5 4 3
    }
    cout<<st.top(); //输出2
    return 0;
}

empty()

检测stack是否为空，返回true为空，返回false为非空

st.empty()

size()

返回stack中元素的个数 O(1)

st.size()

如何清空栈

没有自带的函数，可以这样写

while(!st.empty()){
	st.pop();
}

但是更常用的做法是重新定义一个栈来变相实现栈的清空。

stack的常见用途

用来模拟实现一些递归，防止程序对栈内存的限制导致程序运行出错

6.8 pair的常见用法详解

当想要将两个元素绑在一起作为一个合成元素、又不想因此定义结构体的时候，使用pair可以很方便地作为一个替代品。也就是说pair实际上可以看成一个内部有两个元素的结构体，而且这两个元素的类型是可以指定的。

有时候运行的速度会比结构体快

pair的定义

pair <typename1,typename2> name;

等价于

struct pair {
    tyoename1 first;
    typename2 first;
}

初始化的方式如下(举例)，在后面加一对小括号

pair<string,int> p("haha",5);

而如果想要在代码中临时构建一个pair，有如下两种方法

将类型定义写在前面，后面用小括号内两个元素的方式
使用自带的make_pair函数
```
make_pair("haha",5);
```

pair中元素的访问

pair中只有两个元素first和second，按照正常结构体的方式去访问即可

pair<string,int> p("haha",5);
cout<<p.first; //输出haha
cout<<p.second; //输出5

pair常用函数实例解析

比较操作数

两个pair型可以直接比较大小，比较规则是先以first的大小作为标准，只有当first相等时才去判别second的大小

pair的常见用途

用来代替二元结构体及其构造函数，可以节省编码时间

作为map的键值对来进行插入，比如下面的例子

#include<bits/stdc++.h>
using namespace std;

int main(){
    map<string,int> mp;
    mp.insert(make_pair("abc",123));
    mp.insert(make_pair("efg",456));
    for(auto x:mp){
        cout<<x.first<<' '<<x.second<<endl;
    }
}

输出

abc 123
efg 456

这是因为map的内部实现中涉及到了pair

6.9 常用算法函数

6.9.1 max()、min()和abs()

含义显然。

max()和min()的参数可以是int也可以是浮点数；想求三个数的最大值的时候可以这样：

max(x,max(y,z));

也可以这样

max({x,y,z});

abs()的形参只能是整数

6.9.2 swap()

swap(x,y)用来交换x,y的值

int x=1,y=2;
swap(x,y);
cout<<x<<' '<<y; //输出2 1

6.9.3 reverse()

reverse(it1,it2)可以将数组指针在[it1，it2)之间的元素或容器的迭代器在[it1，it2)范围内的元素进行反转

//对数组进行反转
#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[5]={1,2,3,4,5};
    reverse(a,a+5); //将a[0]~a[4]反转
    for(int i=0;i<5;i++){
        cout<<a[i]<<' '; //输出5 4 3 2 1
    }
}

容器也可以 一定得是迭代器

#include<bits/stdc++.h>
using namespace std;

int main(){
    string str="abcdefg";
    reverse(str.begin(),str.begin()+3); //对str[0]~str[2]进行反转
    for(int i=0;i<str.length();i++){
        cout<<str[i]<<' '; //输出cbadefg
    }
}

6.9.4 next_permutation()

next_permutation()给出一个序列在全排列中的下一个序列

比如当n==3时的全排列为

这样231的下一个序列就是312

示例如下

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[10]={1,2,3};
    //a[0]~a[2]之间的序列需要求解next_permutation
    do{
        printf("%d%d%d\n",a[0],a[1],a[2]);
    }while(next_permutation(a,a+3));
    return 0;
}

输出结果

在上述代码中使用循环是因为next_permutation在已经到达全排列的最后一个时会返回false，这样方便退出循环。而使用do...while语句而不使用while是因为序列1 2 3本身也需要输出

6.9.5 fill()

fill()可以把数组或容器内某一段区间赋为某个相同的值。不同于memset只能赋0或-1，这里随便赋

int a[5];
fill(a,a+5,233);
//a[5]={233,233,233,233,233};

6.9.6 sort()

如何使用sort函数

sort(首元素地址（必填），尾元素地址的下一个地址，比较函数（非必填）);

不写比较函数则默认递增排序

如何实现比较函数cmp

基本数据类型数组的排序

比如要对一个数组实现降序排序

bool cmp(int a,int b){
    return a>b; //可以理解成当a>b的时候把a放在b前面
}

记忆方法：如果要升序，就用'<'，因为"a<b"就是左小右大；如果要降序，就用'>'，因为"a>b"就是左大右小

结构体数组的排序

比如如下的结构体

struct node{
    int x,y;
}ssd[10];

如果进行按照x的一级排序

bool cmp(node a,node b){
    return a.x>b.x;
}

二级排序

bool cmp(node a,node b){
    if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}

当然也可以使用重载运算符

struct node{
    int a;
    int b;
    bool operator < (const node &other) const{
        return x<other.x;
    }
}

容器的排序

在STL标准容器中只有vector,string,deque可以使用sort

//以vector为例
bool cmp(int a,int b){
    return a>b; //降序
}
int main(){
    vector<int> vi;
    vi.push_back(2);
    vi.push_back(3);
    vi.push_back(1;
   	sort(vi.begin(),vi.end(),cmp); //3 2 1
}

//以string为例
string str[3]={"aa","bbbb","ccc"};
sort(str,str+3); //按照字典序
//或者按照长度排序
bool cmp(string s1,string s2){
    return s1.length()<s2.length(); 
}

6.9.7 lower_bound()和upper_bound()

这两个函数需要用在一个有序数组或容器中，在4.5.1节已经讨论过了它们的实现

lower_bound(first,last,val)用来寻找在数组或容器的[first,last)范围内第一个值大于等于val的元素的位置，如果是数组则返回该位置的指针；如果是容器则返回该位置的迭代器

upper_bound(first,last,val)用来寻找在数组或容器的[first,last)范围内第一个值大于val的元素的位置，如果是数组则返回该位置的指针；如果是容器则返回该位置的迭代器

如果数组或容器中没有需要寻找的元素，则这两个函数均返回可以插入该元素位置的指针或迭代器（即假设存在该元素时，该元素应该在的位置）

时间复杂度O(log(last-first))

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[10]={1,2,2,3,3,3,5,5,5,5};
    int* lowerPos;
    int* upperPos;
    //寻找3
    lowerPos=lower_bound(a,a+10,3);
    upperPos=upper_bound(a,a+10,3);
    printf("%d %d",lowerPos-a,upperPos-a); //输出3 6
    return 0;
}

可见如果只是想获得欲查元素的下标，就可以不使用临时指针，直接令返回值减去数组首地址即可

二分函数的第四个参数：比较函数

当比较体没有明确的比较类型的时候：

struct ore{
  int w,v;
  bool operator<(const ore&other)const{
    return w<other.w;
  } //一定要有重载运算符
};

方法一：构造一个临时对象

// 假设 Ore 已经按 w 升序排序了
    vector<ore> Ore = { {1, 10}, {3, 20}, {5, 30}, {7, 40}, {9, 50} };
    
    int mid = 6;
    // 构造一个临时的 ore 对象，w 为 mid，v 可以为任意值
    ore tmp{mid, 0};
    
    auto it = lower_bound(Ore.begin(), Ore.end(), tmp);

方法二：使用自定义比较器 Lambda

// 假设 Ore 已经按 w 升序排序了
    vector<ore> Ore = { {1, 10}, {3, 20}, {5, 30}, {7, 40}, {9, 50} };
    
    int mid = 6;
    auto it = lower_bound(Ore.begin(), Ore.end(), mid, [](const ore &o, int value) {
        return o.w < value;
    });

这里传入了一个 lambda 作为比较器，lambda 定义为：给定一个 ore o 和一个 int value，如果 o.w < value 返回 true。

这样 lower_bound() 会查找第一个满足 !(o.w < mid)（即 o.w >= mid）的元素。

6.9.8 accumulate()

这个函数可以帮你计算一个范围内所有元素的累积和，还可以指定初始值和自定义操作。

#include <iostream>
#include <vector>
#include <numeric>  // 别忘了包含这个头文件
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    int sum = accumulate(nums.begin(), nums.end(), 0);

    cout << "累积和是：" << sum << endl; //15

    return 0;
}

在这个例子中，我们用 accumulate 计算了一个整型向量 nums 中所有元素的和。第三个参数 0 是累积的初始值，也就是从0开始加。最终，sum 变量中保存了所有元素的累积和。

6.9.10 unique()

它能帮助我们去除相邻的重复元素，并返回一个新的范围结束位置。

代码CPP · 18 行

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 2, 3, 4, 4, 5};
    auto it = unique(nums.begin(), nums.end());
    nums.erase(it, nums.end());

    cout << "去重后的元素是：";
    for(int num : nums) {
        cout << num << " ";
    }
    cout << endl;
	//去重后的元素是：1 2 3 4 5 
    return 0;
}

unique 会将相邻的重复元素移到向量的末尾，然后返回一个新的迭代器 it。接着，我们用 erase 将这些重复的元素移除，最终得到了一个没有相邻重复元素的向量。

6.9.11 find()

find 函数可以帮你在一个范围内找到第一个等于指定值的元素，并返回指向该元素的迭代器。下面是它的用法：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {10, 20, 30, 40, 50};
    auto it = find(nums.begin(), nums.end(), 30);

    if(it != nums.end()) {
        cout << "找到目标元素：" << *it << endl;
    } else {
        cout << "未找到目标元素。" << endl;
    }

    return 0;
}

在这个例子中，find 函数找到了向量 nums 中的元素 30，并返回了指向它的迭代器。如果找不到目标元素，find 会返回 end 迭代器。

6.9.12 count()

count 函数能帮你数数指定值在一个范围内出现了多少次。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 2, 3, 4, 2, 5};
    int count_of_2 = count(nums.begin(), nums.end(), 2);

    cout << "数字2出现的次数是：" << count_of_2 << endl;

    return 0;
}

在这个例子里，count 函数计算了数字 2 在向量 nums 中出现的次数，并将结果保存到 count_of_2 变量中。

6.9.13 partition()

partition 函数根据指定的条件将范围内的元素分为两部分，使得符合条件的元素位于前半部分。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    partition(nums.begin(), nums.end(), [](int x){ return x % 2 == 0; });

    cout << "分区后的结果是：";
    for(int num : nums) {
        cout << num << " ";
    }
    cout << endl;
	//分区后的结果是：8 2 6 4 5 3 7 1 9 
    return 0;
}

这里，我们用 partition 将向量 nums 中所有的偶数放在前面，奇数放在后面。这个分区操作利用了一个Lambda表达式来判断元素是否符合条件。

6.9.14 nth_element()

nth_element() 是 C++ 标准库中的一个算法函数，位于 <algorithm> 头文件中。其主要作用是对容器中的元素进行部分排序，使得第 n 小的元素位于容器的第 n 个位置（从零开始计数）。除此之外，函数保证该位置之前的所有元素都不大于该元素，之后的元素都不小于该元素，但它并不对整个容器进行排序。

用法如下

nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

first：容器的起始迭代器，指向要处理的第一个元素。
nth：一个迭代器，指向所需的 "n" 小元素的位置（即，想要排到第 n 小的位置）。
last：容器的末尾迭代器。

代码CPP · 23 行

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 示例数据
    std::vector<int> vec = {1,2,3,9,4,5,8,6,10};

    // 求第 4 小的元素 (index 3)，即在排序后的数组中的第 4 个位置
    std::nth_element(vec.begin(), vec.begin() + 3, vec.end());

    // 输出第 4 小的元素和数组
    std::cout << "The 4th smallest element: " << vec[3] << std::endl;

    // 输出部分排序后的数组
    std::cout << "Array after nth_element: ";
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出

The 4th smallest element: 4
Array after nth_element: 2 1 3 4 9 5 8 6 10

注意，nth_element 并不会对数组做完整的排序。

6.9.15 is_sorted()

检查一个范围内的元素是否已经有序，默认是如果是升序或者降序排列就返回true否则返回false，当然也可以自己传入比较函数

bool is_sorted(InputIterator first, InputIterator last, Compare comp);

6.9.16 merge()

用于将两个已经排序的范围合并成一个新的排序范围。

std::vector<int> v1 = {1, 3, 5};
std::vector<int> v2 = {2, 4, 6};
std::vector<int> result(6);
    
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());

其实就是这一段函数

int merge(int a[],int b[], int c[], int n, int m){
    //n和m分别是数组a和b的长度
    int i=0,j=0,index=0;
    while(i<n&&j<m){
        if(a[i]<=b[j]) c[index++]=a[i++]; //相等的情况放a和b都一样
        else c[index++]=b[j++]; //把b[j]放入序列中
    }
    while(i<n) c[index++]=a[i++]; //把a的剩余元素放入c中
    while(j<m) c[index++]=b[j++]; //把b的剩余元素放入c中
    return index; //返回序列c的长度
}

6.10 unordered_set的使用

非常接近于set 只是内部不有序

引用哈希集合的用法哈希集合（Hash Set）是一个无序集合，主要用于快速查找、插入和删除操作。它的核心特点是：元素唯一：集合中不能有重复的元素...

哈希集合的用法

哈希集合（Hash Set）是一个无序集合，主要用于快速查找、插入和删除操作。它的核心特点是：

元素唯一：集合中不能有重复的元素。
操作的时间复杂度为 O(1)O(1)（平均情况）。
哈希集合在C++中由 std::unordered_set 实现。

常用函数

以下是 std::unordered_set 的常用操作：

1. 插入元素

unordered_set<int> s;
s.insert(10);  // 插入元素10
s.insert(20);  // 插入元素20

2. 查找元素

if (s.find(10) != s.end()) {
    cout << "10在集合中" << endl;
}

3. 删除元素

s.erase(10);  // 删除元素10

4. 清空集合

s.clear();  // 清空集合

5. 获取集合大小

cout << "集合大小：" << s.size() << endl;

6. 判断集合是否为空

if (s.empty()) {
    cout << "集合为空" << endl;
}

7. 遍历集合

由于 unordered_set 是无序的，遍历时的顺序可能和插入顺序不同。

for (int x : s) {
    cout << x << " ";
}

8. 判断元素是否存在

使用 count 函数，返回值为 0 或 1。

if (s.count(10)) {
    cout << "10在集合中" << endl;
}

实例解析

实例1：判断数组中是否有重复元素

代码CPP · 32 行

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    int n;
    cout << "请输入数组长度：";
    cin >> n;

    unordered_set<int> s;
    bool hasDuplicate = false;
    cout << "请输入数组元素：" << endl;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        // 如果集合中已经有该元素，则有重复
        if (s.find(x) != s.end()) {
            hasDuplicate = true;
            break;
        }
        s.insert(x);  // 否则插入集合
    }

    if (hasDuplicate) {
        cout << "数组中有重复的元素！" << endl;
    } else {
        cout << "数组中没有重复的元素。" << endl;
    }

    return 0;
}

运行示例：

输入1：

请输入数组长度：5
请输入数组元素：
1 2 3 4 5

输出1：

数组中没有重复的元素。

输入2：

请输入数组长度：5
请输入数组元素：
1 2 3 2 5

输出2：

数组中有重复的元素！

实例2：统计字符串中不重复字符的个数

代码CPP · 18 行

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    string str;
    cout << "请输入一个字符串：";
    cin >> str;

    unordered_set<char> s;  // 使用哈希集合存储字符
    for (char c : str) {
        s.insert(c);  // 每个字符插入集合
    }

    cout << "不重复字符的个数：" << s.size() << endl;

    return 0;
}

运行示例：

输入：

请输入一个字符串：hello

输出：

不重复字符的个数：4

实例3：快速查找目标和对

给定一个数组，判断是否存在两个数的和等于目标值。

代码CPP · 28 行

#include <iostream>
#include <unordered_set>
using namespace std;

bool hasPairWithSum(int arr[], int n, int target) {
    unordered_set<int> s;  // 哈希集合存储访问过的元素
    for (int i = 0; i < n; i++) {
        int complement = target - arr[i];
        if (s.find(complement) != s.end()) {
            return true;  // 找到和为目标值的两个数
        }
        s.insert(arr[i]);  // 否则插入集合
    }
    return false;
}

int main() {
    int arr[] = {1, 4, 6, 8, 10};
    int target = 14;

    if (hasPairWithSum(arr, 5, target)) {
        cout << "存在和为 " << target << " 的两个数！" << endl;
    } else {
        cout << "不存在和为 " << target << " 的两个数！" << endl;
    }

    return 0;
}

运行示例：

输入数组：

[1, 4, 6, 8, 10], target = 14

输出：

存在和为 14 的两个数！

总结

优点：unordered_set 适合用于查找和去重，操作效率高（平均 O(1)O(1)）。
缺点：由于其无序性，无法直接获得有序结果。如果需要有序集合，可以使用 std::set（基于红黑树实现，操作复杂度为 O(log⁡n)O(\log n)）。

6.11 list的使用

引用std::list 是 C++ 标准模板库（STL）中的一个容器，它实现了一个双向链表（doubly linked list）。与向量（std:...

std::list 是 C++ 标准模板库（STL）中的一个容器，它实现了一个双向链表（doubly linked list）。与向量（std::vector）不同，std::list 在以下场景中非常有用：

高效的插入与删除：在链表中，你可以在任意位置进行常数时间复杂度（O(1)）的插入和删除操作，而不需要像 std::vector 那样可能涉及大量数据的移动。

不支持随机访问：由于底层是链表，std::list 不支持下标访问（例如 list[i]），只能通过迭代器进行顺序遍历。

下面介绍一些常用的 std::list 操作，并附上示例代码：

1. 创建与初始化
代码CPP · 19 行
#include <iostream>
#include <list>
using namespace std;

int main() {
    // 创建一个空的 list，元素类型为 int
    list<int> myList;

    // 使用初始化列表创建 list
    list<int> numbers = {10, 20, 30, 40};

    // 输出 numbers 中的元素
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}
2. 插入元素

在末尾插入：使用 push_back()

在开头插入：使用 push_front()

在任意位置插入：使用 insert()，insert(it, val)成员函数用于在链表中插入元素。it为该链表的一个迭代器，val为待插入的值，插入后val位于it所指位置的前一位。返回值为一个迭代器，表示val插入到了哪个位置。
代码CPP · 26 行
#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> myList;

    // 在末尾插入元素
    myList.push_back(10);
    myList.push_back(20);

    // 在开头插入元素
    myList.push_front(5);

    // 通过迭代器在第二个位置插入元素 15
    auto it = myList.begin();
    ++it; // 指向原来的第一个元素后面的位置
    myList.insert(it, 15);

    // 输出 list 中的元素
    for (int num : myList) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}
3. 删除元素

删除开头元素：使用 pop_front()

删除末尾元素：使用 pop_back()

删除指定位置的元素：使用 erase()，传入对应的迭代器

remove(it)成员函数用于删除某个迭代器所指的节点。注意在删除之后it就失效了，除非给it重新赋值，否则对它的任何操作都会导致错误！

清空所有元素：使用 clear()
代码CPP · 22 行
#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> myList = {5, 10, 15, 20};

    // 删除第一个元素
    myList.pop_front();

    // 删除最后一个元素
    myList.pop_back();

    // 删除中间的元素（例如，删除当前 list 中的第一个元素）
    auto it = myList.begin();
    myList.erase(it);

    // 此时 list 为空，或者可以再次添加元素
    myList.clear(); // 清空所有元素

    return 0;
}
4. 遍历与访问

由于 std::list 不支持随机访问（不能用下标访问），所以必须使用迭代器或范围 for 循环来遍历：
代码CPP · 21 行
#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> myList = {10, 20, 30, 40};

    // 使用范围 for 循环遍历
    for (int num : myList) {
        cout << num << " ";
    }
    cout << endl;

    // 使用迭代器遍历
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}
5. 常用算法成员函数

sort()：对链表排序

reverse()：将链表中的元素反转

unique()：移除连续重复的元素

merge()：合并两个已排序的 std::list
代码CPP · 39 行
#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> myList = {30, 10, 20, 20, 40};

    // 排序
    myList.sort();  // 排序后：10, 20, 20, 30, 40

    // 移除连续重复的元素
    myList.unique(); // 结果：10, 20, 30, 40

    // 反转链表
    myList.reverse(); // 结果：40, 30, 20, 10

    // 输出结果
    for (int num : myList) {
        cout << num << " ";
    }
    cout << endl;

    // 合并两个已排序的 list
    list<int> list1 = {1, 3, 5};
    list<int> list2 = {2, 4, 6};

    // 确保两个 list 都已经排序
    list1.sort();
    list2.sort();
    list1.merge(list2);  // list1 合并了 list2，且 list2 变为空

    // 输出合并后的 list1
    for (int num : list1) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}
6. 注意事项

迭代器失效：在对 std::list 进行插入或删除操作时，其他迭代器通常不会失效（与 std::vector 不同），但被删除元素对应的迭代器将无效。

内存使用：由于链表的每个节点都需要额外的指针存储前后节点的信息，因此在内存使用上可能比连续存储的容器（如 std::vector）稍高。

不支持随机访问：如果需要频繁地进行随机访问（例如，直接访问第 n 个元素），建议使用 std::vector 或 std::deque。

总的来说，std::list 提供了在任意位置快速插入和删除的能力，适用于对数据进行频繁修改的场景，但在需要随机访问和高空间效率

时，应考虑其他容器。

6.12 multiset的使用

multiset的定义

multiset 是一个集合容器，它可以存储多个相同的元素。换句话说，如果你有一堆重复的数，比如 3、5、5、5、7，你可以用multiset来妥善管理它们。与set不同的是，set不会允许重复的元素，而multiset非常欢迎重复元素的加入。

可以使用统一初始化的元素来创建

int main() {
    multiset<int> numbers = {3, 5, 5, 7, 3, 9};

    // 基于范围的for循环遍历multiset
    for (int num : numbers) {
        cout << num << " ";
    }

    return 0;
}

注意，multiset会自动按升序排列元素。

如果是自定义类型，需要重载小于号

multiset内元素的访问

使用迭代器

multiset常用函数实例解析

insert()

略了

erase()

erase方法用来删除元素。但是要注意！如果你直接传入一个值，所有与这个值相同的元素都会被删除。如果你只想删除一个特定的元素，最好先找到它的迭代器，然后用这个迭代器来删除。

int main() {
    multiset<int> numbers = {3, 5, 5, 7};

    // 删除所有的5
    numbers.erase(5);

    // 打印当前的multiset
    for (int num : numbers) {
        cout << num << " ";
    }

    return 0;
}

如果只想删除第一个5

auto it = numbers.find(5);  // 找到第一个5
if (it != numbers.end()) {
    numbers.erase(it);  // 只删除找到的第一个5
}

size()

略了

clear()

略了

empty()

略

lower_bound()

略 和algorithm中的不一样

upper_bound()

略 和algorithm中的不一样

第7章提高篇（1）——数据结构专题（1）

7.1 栈的应用

栈(stack)是一种后进先出的数据结构。

可以把栈理解成一个箱子，箱子的长宽仅够一本书放入或拿出。每次可以把一本书放在箱子的最上方，也可以把箱子最上方的书拿出。

栈顶指针：始终指向栈的最上方元素的一个标记，当使用数组实现栈时，栈顶指针是一个int型的变量（数组下标从0开始），通常记作TOP；而当使用链表实现栈时，则是一个int*的指针。栈中没有元素（即栈空）时令TOP=-1

下面使用数组st[]来实现栈，int型变量TOP表示栈顶元素的下标，对常用的几个操作进行示范实现

清空 clear

栈的清空操作指令TOP=-1表示栈中没有元素

void clear(){
	TOP=-1;
}

获取栈内元素个数 size

由于数组下标从0开始，元素个数为TOP+1

int size(){
    return TOP+1;
}

判空 empty

bool empty(){
    if(TOP==-1) return true;
    else return false;
}

进栈 push

void push(int x){
	st[++TOP]=x; //先把TOP+1，再把x存入TOP指向的位置
}

出栈 pop

void pop(){
	TOP--;
}

取栈顶元素 top

int top(){
	return st[TOP];
}

需要特别注意的是pop和top操作必须在栈非空的情况下才能使用，因此在这之前必须使用empty()函数判断

事实上使用STL的stack容器更简单。

需要注意的是STL中清空栈没有自带的函数，可以这样写

while(!st.empty()){
	st.pop();
}

但是更常用的做法是重新定义一个栈来变相实现栈的清空。

下面来看一个题

引用【codeup 1918】简单计算器读入一个只包含+ - x / 的非负整数计算表达式，计算该表达式的值输入格式：一个长度不超过100的...

【codeup 1918】简单计算器

读入一个只包含+ - x / 的非负整数计算表达式，计算该表达式的值

输入格式：

一个长度不超过100的字符串，其中操作符和操作数仅由+、−、∗、/、整数（不小于1且不大于9）构成，且操作符和操作数之间用空格分隔。数据确保表达式一定合法，且计算过程的所有结果不会超过10^9。

输出格式：

输出一行，即该表达式的值，精确到小数点后两位

样例输入

3 + 4 * 5

输出

23.00

引用1. 中缀表达式（Infix Expression）中缀表达式是我们日常生活中最常见的数学表达式形式。它的特点是运算符位于两个操作数之间。例如...

1. 中缀表达式（Infix Expression）

中缀表达式是我们日常生活中最常见的数学表达式形式。它的特点是运算符位于两个操作数之间。例如：

3 + 4

(5 - 2) * 6

2 + 3 * 4

特点

运算符位于操作数之间。

需要使用括号来明确运算顺序。

人类易于理解和书写，但计算机处理起来较为复杂。

示例

2 + 3 * 4 的中缀表达式需要根据运算符优先级计算：先计算 3 * 4，再计算 2 + 12，结果为 14。

2. 后缀表达式（Postfix Expression，也称为逆波兰表达式）

后缀表达式是一种不需要括号的表达式形式，它的特点是运算符位于操作数之后。例如：

3 4 +

5 2 - 6 *

2 3 4 * +

特点

运算符位于操作数之后。

不需要括号，运算顺序完全由运算符的位置决定。

计算机处理起来非常方便，适合用栈（Stack）来求值。

示例

2 3 4 * + 的后缀表达式计算过程：

遇到 3 4 *，计算 3 * 4 = 12。

表达式变为 2 12 +。

计算 2 + 12 = 14，结果为 14。

3. 中缀表达式转后缀表达式

将中缀表达式转换为后缀表达式是计算机科学中的一个常见任务，通常使用栈（Stack）来实现。以下是转换的步骤：

转换规则

初始化一个空栈和一个空输出列表。

从左到右扫描中缀表达式。

如果遇到操作数，直接添加到输出列表。

如果遇到左括号 (，将其压入栈。

如果遇到右括号 )，将栈中的运算符弹出并添加到输出列表，直到遇到左括号 (。左括号弹出但不添加到输出列表。

如果遇到运算符：

弹出栈中优先级高于或等于当前运算符的所有运算符，并添加到输出列表。

将当前运算符压入栈。

扫描结束后，将栈中剩余的运算符依次弹出并添加到输出列表。

示例

将中缀表达式 2 + 3 * 4 转换为后缀表达式：

输出列表：2

栈：+

输出列表：2 3

栈：+ *

输出列表：2 3 4

栈：+ *（扫描结束，弹出栈中所有运算符）

输出列表：2 3 4 * +

7.2 队列的应用

队列（queue）是一种先进先出的数据结构，与栈有所不同。

举一个例子来理解：食堂打饭排队，最先进去的先打到饭出队，也就是先进先出

一般来说需要一个队首指针front来指向队首元素的前一个位置，而使用一个队尾指针rear来指向队尾元素。

与栈类似，当使用数组来实现queue时，队首指针front和队尾指针rear为int型变量（下标从0开始）；而当使用链表来实现时则为int*型变量的指针

下面使用数组q[]来实现队列，而int型变量front存放队首元素的前一个下标，rear存放队尾元素的下标（下标从0开始），下面演示常见操作：

清空 clear

初始状态为front=-1、rear=-1

void clear(){
    front=rear=-1;
}

获取队列内元素的个数 size

in size(){
    return rear-front;
}

判空 empty

bool empty(){
    if(front==rear) return true;
    else return false;
}

入队 push

由于rear指向队尾元素，因此元素入队时需先把rear+1，再存放到rear指向的位置

void push(){
    q[++rear]=x;
}

出队 pop

可以把队首指针+1来实现

void pop(){
	front++;
}

取队首元素 get_front

由于front指向的是队首元素的前一个元素，因此front+1才是队首元素的位置

int get_front(){
    return q[front+1];
}

取队尾元素 get_rear

int get_rear(){
	return q[rear];
}

与栈类似，这些操作必须在队列非空的情况下时候，要先判断

另外，多用STL比较好

7.3 链表处理

7.3.1 链表的概念

线性表：常用的一种数据结构

顺序表：可以简单地理解成“数组”
链表

按正常方式定义一个数组的时候，计算机会从内存中取出一块连续的地址来存放给定长度的数组；而链表则是由若干个结点组成（每个结点代表一个元素），且结点在内存中的存储位置通常是不连续的。除此之外，链表的两个结点之间一般通过一个指针来从一个结点指向另一个结点，因此链表的结点一般由两部分构成，即数据域和指针域：

struct node {
    typename data; //数据域
    node* next; //指针域
}

一般来说，数据域存放要储存的数据，而指针域指向下一个结点的地址，这样就会产生从某个节点开始的由指针链接的一条链式结构，即链表。

可以分为两类

带头结点的链表
不带头结点的链表

头结点一般称为head，其数据域data不存放任何内容，而指针域next指向第一个数据域有内容的结点（一般直接把这个结点叫做第一个结点），我们在这里统一采用带头结点的写法。最后一个结点的next指针指向NULL，表示一条链表的结尾

7.3.2 使用malloc函数或new运算符为链表节点分配内存空间

malloc函数

C语言中stdlib.h头文件下用于动态内存申请的函数，返回类型是申请的同变量类型的指针

typename* p=(typename*)malloc(sizeof(typename));

以申请一个int型变量和一个node型结构体变量为例：

int *p=(int*)malloc(sizeof(int));
node* p=(node*)malloc(sizeof(node));

这个写法的逻辑是：以需要申请的内存空间大小（即sizeof(node)）为malloc函数的参数，这时malloc函数就会向内存申请一块大小为sizeof(node)的空间，并且返回指向这块空间的指针。但这时这个指针类型未确定(void*)，因此需要将它强转为node*型，这样等号右边就得到了一个node*型的指针，并通过赋值等号把这个指针赋给了node*型的指针变量p，就成功申请了一块node类型大小的内存空间，即一个node型的结构体变量，并通过指针p来访问它。

new运算符

new是C++中用来申请动态空间的运算符，其返回类型同malloc函数的返回类型，基本用法如下

tyoename* p=new typename;

同样以申请一个int型变量和一个node型变量为例

int *p=new int;
node* p=new node;

内存泄漏

指malloc与new开劈出来的内存空间在使用之后没有释放，导致其在程序结束之前始终占据该内存空间，所以在使用完malloc和new开辟出来的空间之后必须将其释放。

free函数

free函数是对应malloc函数的，同样在stdlib.h下面

//在free的参数中填写需要释放的内存空间的指针变量即可
free(p);

free函数的效果：

释放指针变量p所指向的内存空间
将指针变量p指向空地址NULL

需要注意的是malloc和free必须成对出现否则容易爆

delete运算符

对应new运算符，使用方法和实现效果与free相同

delete(p);

delete和new运算符必须成对出现

7.3.3 链表的基本操作

创建列表

现在可以通过malloc和new来获得若干个零散的结点，只需要把他们串起来，只需要让每个结点的next指针指向下一个结点的地址即可

1. -> 操作符的作用

-> 操作符用于通过指针访问对象的成员。它的作用相当于：

解引用指针（*ptr）。

访问对象的成员（(*ptr).member）。

换句话说，ptr->member 等价于 (*ptr).member。

2. 使用场景

-> 操作符通常用于以下场景：

访问动态分配对象的成员：

当对象是通过 new 动态分配时，返回的是指针，此时需要使用 -> 访问成员。

访问结构体或类的指针成员：

当结构体或类的实例是通过指针引用时，使用 -> 访问成员。

访问智能指针的成员：

对于智能指针（如 std::unique_ptr 或 std::shared_ptr），使用 -> 访问成员。

代码CPP · 38 行

#include<bits/stdc++.h>
using namespace std;

struct node {
    int data;
    node* next;
};

node *create(int a[],int len){
    node *p,*pre,*head; //当前结点 前驱结点 头结点
    head=new node; //创建头结点
    head->next=NULL; //初始化，让头结点指向NULL
    //pre=new node; //创建前驱结点
    //上面一行不需要，因为前驱结点（pre）一开始就应该指向头结点，并不需要为 pre 创建一个新的结点，因为 pre 只需要作为指向头结点的指针
    pre=head; //最开始前驱结点就是头结点
    for(int i=0;i<len;++i){
        p=new node; //创建结点 即前驱结点的后继结点
        p->data=a[i]; //读入结点数据域 也可以scanf
        p->next=NULL; //先初始化
        pre->next=p; //前驱结点的指针域（指向前驱结点的后继结点）设为当前新建结点的地址，把前后两个结点连接起来
        //必须要理解这里的pre和p都是指针，本质是地址
        //所以比如i=0的情况下，原本是head->NULL的，现在是head->1了，因为修改了pre就等同于修改了head，因为pre和head的地址相同
        pre=p; //把pre作为p，作为下一个结点的前驱结点
        //其实是把pre的地址换个地方，现在pre的地址是上面那一通操作生成的p的地址
    }
    return head; //返回头结点指针
}

int main(){
    int a[5]={1,2,3,4,5};
    node* L=create(a,5);
    L=L->next; //从第一个结点开始有数据域
    while(L!=NULL){
        printf("%d",L->data);
        L=L->next;
    } //输出1 2 3 4 5
    return 0;
}

第 17 行和第 18 行：指针的传递
pre->next = p;  // 将前驱节点的指针域（next）指向新节点p
pre = p;         // 将pre指向当前节点p，作为下一个节点的前驱
这两行代码的目的是 更新链表中各个节点的链接关系。让我们逐一解释：

pre->next = p;

：

这行代码是将前一个节点（即 pre 指向的节点）的 next 指针指向新创建的节点 p。

例如，假设链表目前有节点 A 和节点 B，此时 pre 指向节点 A，p 指向新创建的节点 B。你要做的是将 A->next 指向 B，也就是说，链表从 A 到 B 连接起来。

pre = p;

：

这行代码的作用是更新前驱节点 pre 的指向。

将 pre 更新为当前的节点 p，也就是将 pre 指向 B。

下一次循环时，pre 就是 B，此时它会作为前一个节点参与到 next 指针的更新。

换句话说， pre->next = p; 负责建立新节点的链接关系，而 pre = p; 则是更新 pre 为当前节点 p，为下一轮创建新的节点做准备。

查找元素

从第一个结点开始，不断判断当前结点的数据域是否等于x，如果等于就cnt++，这样结尾的时候cnt的值就是列表中元素x的个数

int search(node *head,int x){
    int cnt=0;
    node *p=head->next; //从第一个节点开始
    while(p!=NULL){
        if(p->data==x) cnt++;
        p=p->next;
    }
    return cnt;
}

插入元素

“在第3个位置插入元素4”的意思是在插入完成之后第3个位置的元素是4，意思是把原先第三个位置的元素让开（在第2和3之间插入）

假设原本是6 7 8 9 10

在第三个位置插入4之后，就是7指向4，而4指向8，依此思路进行代码实现

//将x插入以head为头结点的链表的第pos个位置上
void insert(node *head,int pos,int x){
    node* p=head;
    for(int i=0;i<pos-1;i++){
        p=p->next; //pos-1是为了插入位置的前一个结点，这里相当于移动p的指针
    }
    node *q=new node;
    q->data=x; //这个时候q还是野指针
    q->next=p->next;
    p->next=q;
}

这份代码可以直接写在“创建链表”部分的代码中进行使用，把create函数返回的头指针L直接作为第一个参数传入即可

顺序必须是先把新节点的指针域next指向后继结点，之后才能把前一个元素所在节点的指针指向新节点的地址

删除元素

对链表来说，删除元素是指删除链表上所有值为给定的数x，操作是这样进行的：

由指针变量p枚举结点，指针变量pre作为p指向的结点的前驱结点
当p指向的结点的数据域恰好为x时，进行下面三个操作
1. 令pre指向的结点的指针域指向指针变量p指向的结点的后继结点
2. 释放p所指向结点的内存空间
3. 令p指向pre指向的结点的后继结点

代码实现如下

//删除以head为头结点的链表中所有数据域为x的结点
void del(node* head,int x){
    node *p=head->next; //p从第一个结点开始枚举
    node *pre=head; //pre始终保存p的前驱结点的指针
    while(p!=NULL){
        if(p->data==x){ //数据域恰好为x，说明要删除该结点
            pre->next=p->next;
            delete(p);
            p=pre->next;
        }
        else{ //数据域不是x，把pre和p都往后移一位
            pre=p;
            p=p->next;
        }
    }
}

这份代码可以直接写在“创建链表”部分的代码中进行使用，把create函数返回的头指针L直接作为第一个参数传入即可

最后总结一下这几个板子

代码CPP · 59 行

#include<bits/stdc++.h>
using namespace std;
struct node {
    int data;
    node* next;
};

node *create(int a[],int len){
    node *p,*pre,*head;
    head=new node;
    head->next=NULL;
    pre=head;
    for(int i=0;i<len;i++){
        p=new node;
        p->next=NULL;
        p->data-a[i];
        pre->next=p;
        pre=p;
    }
    return head;
}
int search(node *head,int x){
    int cnt=0;
    node *p=head->next; //从第一个节点开始
    while(p!=NULL){
        if(p->data==x) cnt++;
        p=p->next;
    }
    return cnt;
}

//将x插入以head为头结点的链表的第pos个位置上
void insert(node *head,int pos,int x){
    node* p=head;
    for(int i=0;i<pos-1;i++){
        p=p->next; //pos-1是为了插入位置的前一个结点，这里相当于移动p的指针
    }
    node *q=new node;
    q->data=x; //这个时候q还是野指针
    q->next=p->next;
    p->next=q;
}

//删除以head为头结点的链表中所有数据域为x的结点
void del(node* head,int x){
    node *p=head->next; //p从第一个结点开始枚举
    node *pre=head; //pre始终保存p的前驱结点的指针
    while(p!=NULL){
        if(p->data==x){ //数据域恰好为x，说明要删除该结点
            pre->next=p->next;
            delete(p);
            p=pre->next;
        }
        else{ //数据域不是x，把pre和p都往后移一位
            pre=p;
            p=p->next;
        }
    }
}

7.3.4 静态链表

对于有些问题来说，结点的地址是比较小的整数，这样无必要建立动态链表，应使用简单的静态链表

实现原理是hash，通过建立一个结构体数组，并令数组的下标直接表示该结点的地址，来达到直接访问数组中的元素就能访问结点的效果，因为访问非常方便所以不需要头结点

struct Node{
    typename data; //数据域
    int next; //指针域
}node[size]; //注意数组名和结构体名不要相同

next=-1表示没有后继结点

【PAT A1032】 Sharing

给出两条链表的首地址以及若干结点的地址、数据、下一个结点的地址，求两条链表的首个共用结点的地址。如果两条链表没有共用结点则输出-1

注意：使用map容易超时

代码CPP · 34 行

#include<bits/stdc++.h>
using namespace std;

const int maxn=100010;
struct Node{
    char data;
    int next;
    bool flag; //数据是否在第一条链表里面出现
    Node(){
        flag=false;
        next=-1;
    }
}node[maxn];

int main(){
    int s1,s2,n; //s1 s2分别表示两条链表的首地址
    scanf("%d%d%d",&s1,&s2,&n);
    char data;
    int address,next;
    for(int i=0;i<n;i++){
        scanf("%d %c %d",&address,&data,&next);
        node[address].data=data;
        node[address].next=next;
    }
    int p;
    for(int p=s1;p!=-1;p=node[p].next){
        node[p].flag=true;
    }
    for(int p=s2;p!=-1;p=node[p].next){
        if(node[p].flag) break;
    }
    if(p!=-1) printf("%05d",p);
    else printf("-1");
}

这是一道静态列表所能解决的比较简单的题，而对于稍微复杂一点的题此处归纳一种通法

定义静态链表

struct Node{
    typename data; //数据域
    int next; //指针域
    XXX; //结点的某个性质，不同的题目会有不同的设置
}node[100010];

例如可以设置结点是否为链表上的一个结点

在程序的开始对静态链表进行初始化，一般来说需要对定义里的XXX进行初始化，定义为正常情况下达不到的数字（一般来说需要小于所有能达到的数字）
题目一般都会给出一条链表的首结点的地址，那么我们就可以根据这个地址来遍历得到整条链表，同时需要注意这一步同时也是对性质XXX进行标记、并且对有效节点的个数进行计数的时候
由于使用静态链表的时候是采用hash的方式，这就会使得数组下标的不连续，而很多时候题目给出的结点并不都是有效结点（即可能存在不在链表上的结点）。为了能够可控地访问有效结点，一般需要对数组进行排序，把有效结点移到数组左端，这样就可以用步骤3得到的cnt来访问它们。

既然需要把有效结点移到前面，那么就可以使用之前定义的XXX来帮忙。在步骤2中XXX需要被初始化为比正常结点的XXX取值要小的数值，而由于无效结点的XXX在步骤3中并不会被修改，因此一定比有效结点的XXX小。于是可以使用特定的cmp函数来将cmp的两个参数结点中有无效结点时按XXX降序，这样就可以把有效结点全部移到数组左端
```
bool cmp(Node a,Node b){
	if(a.XXX==-1||b.XXX==-1){ //至少一个结点是无效结点 把它放在数组后面
        	return a.XXX>b.XXX;
    }
    else{
        //第二级排序
    }
}
```
在步骤4之后有效结点均位于数组左端，且已经按结点的顺序进行了排序，接下来依题目而定

【PAT A1052】 Linked List Sorting

给出N个结点的地址address、数据域data以及指针域next，然后给出链表的首地址，要求把这个链表上的结点按data值从大到小输出。（输入格式与输出格式相同）

代码CPP · 40 行

//给出N个结点的地址address、数据域data以及指针域next，然后给出链表的首地址，要求把这个链表上的结点按data值从大到小输出。（输入格式与输出格式相同）
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
struct Node{
    int address;
    int data;
    int next=-1;
    bool flag=false;
}node[maxn];
bool cmp(Node a,Node b){
    if(!a.flag||!b.flag) return a.flag>b.flag;
    else return a.data<b.data;
}
int main(){
    int headAddress,n;
    scanf("%d%d",&n,&headAddress);
    int address,data,next;
    for(int i=0;i<n;i++){
        scanf("%d%d%d",&address,&data,&next);
        node[address].address=address;
        node[address].data=data;
        node[address].next=next;
    }
    int p,cnt=0;
    for(int p=headAddress;p!=-1;p=node[p].next){
        node[p].flag=true;
        cnt++;
    }
    if(!cnt) printf("0 -1");
    else{
        sort(node,node+maxn,cmp);
        printf("%d %05d\n",cnt,node[0].address);
        for(int i=0;i<cnt;i++){
            if(i!=cnt-1) printf("%05d %d %05d\n",node[i].address,node[i].data,node[i+1].address);
            //这里一定要注意第三项不要写成node[i].next，因为sort完了，我们要打印的顺序并不是按照链表链接的顺序
            else printf("%05d %d -1",node[i].address,node[i].data);
        }
    }
}

第8章提高篇（2）——搜索专题

8.1 深度优先搜索（DFS）

以枚举所有完整路径以遍历所有情况的搜索方法

dfs可以用栈来实现，但是递归更简单

把递归式理解成岔道口，递归边界理解成死胡同

有n件物品，每件物品的重量为w[i]，价值为c[i]。现在需要选出若干件物品放入一个容量为V的背包中，使得在选入背包的物品重量和不超过容量V的前提下，让背包中物品的价值最大，求最大价值（1<=n<=20）

分析：

死胡同：物品重量总和超过V

岔道口：每次选择的不同的物品

代码CPP · 34 行

#include<bits/stdc++.h>
using namespace std;

const int maxn=25;

int n,v,maxValue,w[maxn],c[maxn];

void dfs(int idx,int sumW,int sumC){
    //死胡同
    if(idx==n){ //已经完成对n件物品的选择
        if(sumW<=v&&sumC>maxValue){
            maxValue=sumC;
        }
        return;
    }
    //岔路口
    dfs(idx+1,sumW,sumC); //不选第idx件物品
    //如果不选第idx件物品无法做到最大的话
    dfs(idx+1,sumW+w[idx],sumC+c[idx]); //选第idx件物品（0起计）
    //因为数组下标0起计，w[idx]其实就是已经选了idx+1件
}

int main(){
    cin>>n>>v;
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    for(int i=0;i<n;i++){
        cin>>c[i];
    }
    dfs(0,0,0); //初始时第0件物品，总重量和总价值均为0
    cout<<maxValue;
    return 0;
}

由于每件物品有两种选择，时间复杂度O($2^n$)，但是可以稍加优化来让效率更高。

上述代码中总是把n件物品的选择全部确定之后才更新最大价值，但是事实上忽略了背包容量不超过v这个特点。也就是说完全可以把sumW的判断加入“岔道口”，只有当sumW<=V的时候才进入岔道，修改如下

void dfs(int idx,int sumW,int sumC){
    if(idx==n) return; //已经完成了对n件物品的选择
    //岔道口
    dfs(idx+1,sumW,sumC); //不选第idx件物品
    //只有加入第idx件物品后未超过容量v才能继续
    if(sumW+w[idx]<=v){
        if(sumC+c[idx]>maxValue) maxValue=sumC+c[idx];
    }
    dfs(idx+1,sumW+w[idx],sumC+c[idx]); //选第idx件物品
}

这样优化了时间复杂度。

这种通过题目条件限制来节省DFS计算量的方法叫做剪枝

事实上下面给出了一类DFS问题的解决方法：给定一个序列，枚举这个序列中的所有子序列（可以不连续）

给定n个整数（可能有负数），从中选择恰好k个数，使这k个数的和恰好等于一个给定的数x；如果有多种方案，选择平方和最大的那一个

void dfs(int idx,int nowK,int sum,int sumSqu){
    if(nowK==k&&sum==x){
        if(sumSqu>maxSumSqu){
            maxSumSqu=sumSqu;
            ans=temp;
        }
        return;
    }
    //已经处理完n个数，或者超过k个数，或者和超过x，返回
    if(idx==n||nowK>k||sum>x) return;
    //选idx号数
    temp.push_back(a[idx]);
    dfs(idx+1,nowK+1,sum+a[idx],sumSqu+a[idx]*a[idx]);
    temp.pop_back();
    //不选
    dfs(idx+1,nowK,sum,sumSqu);
}

dfs的一些剪枝技巧

先给出一段深搜模板

int ans = 最坏情况, now;  // now 为当前答案
这个模板要求在调用dfs之前先将起点标记，防止回溯出现环路。
void dfs(传入数值) {
  if (到达目的地) ans = 从当前解与已有解中选最优;
  for (遍历所有可能性)
    if (可行) {
      进行操作;
      dfs(缩小规模);
      撤回操作;
    }
}

其中的 ans 可以是解的记录，那么从当前解与已有解中选最优就变成了输出解。

记忆化搜索

代码CPP · 19 行

int g[MAXN];  // 定义记忆化数组
int ans = 最坏情况, now;

void dfs f(传入数值) {
  if (g[规模] != 无效数值) return;  // 或记录解，视情况而定
  if (到达目的地) ans = 从当前解与已有解中选最优;  // 输出解，视情况而定
  for (遍历所有可能性)
    if (可行) {
      进行操作;
      dfs(缩小规模);
      撤回操作;
    }
}

int main() {
  // ...
  memset(g, 无效数值, sizeof(g));  // 初始化记忆化数组
  // ...
}

最优性剪枝

int ans = 最坏情况, now;

void dfs(传入数值) {
  if (now比ans的答案还要差) return;
  if (到达目的地) ans = 从当前解与已有解中选最优;
  for (遍历所有可能性)
    if (可行) {
      进行操作;
      dfs(缩小规模);
      撤回操作;
    }
}

可行性剪枝

int ans = 最坏情况, now;

void dfs(传入数值) {
  if (当前解已不可用) return;
  if (到达目的地) ans = 从当前解与已有解中选最优;
  for (遍历所有可能性)
    if (可行) {
      进行操作;
      dfs(缩小规模);
      撤回操作;
    }
}

8.2 广度优先搜索（BFS）

以广度为第一关键词。当碰到岔道口时，总是先依次访问从该岔道口能直接到达的所有结点，然后再按这些结点被访问的顺序去依次访问它们能直接到达的所有结点。

算法依靠队列来实现。

void BFS(int s){ //s为起点
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        取出队首元素top;
        访问队首元素top; //访问可以是任何事情,例如输出
        将队首元素出队; 
        将top的下一层结点中未曾入队的结点全部入队,并设置为已入队;
        //并标记它们的层号为now++，同时设置这些结点已入队
    }
}

例题

给出一个m*n的矩阵，矩阵中的元素为0或1。称位置(x,y)与其上下左右四个位置是相邻的。如果矩阵中有若干（1个也算若干个）个1是相邻的（不必两两相邻），那么称这些1构成了一个“块”，求给定的矩阵中块的个数。

使用bfs的思想：枚举每一个位置的元素，如果是0就跳过，如果是1就使用bfs查询与该位置相邻的4个元素（前提是不出界），判断是否为1，如果是1那么继续查询，直到整个1块访问完毕。而为了避免走回头路可以定义一个bool数组inq(即in queue的缩写)来记录每个位置是否在bfs中已经入过队。

对于当前位置(x,y)而言，可以设置两个增量数组来访问相邻的4个位置。

int X[]={0,0,1,-1};
int Y[]={1,-1,0,0};

分别对应(x,y+1) (x,y-1) (x+1,y) (x-1,y)

这样就可以用for循环去枚举4个方向，以确定当前坐标(nowX,nowY)相邻的4个位置

for(int i=0;i<4;i++){
    newX=nowX+X[i];
    newY=nowY+Y[i];
}

本题的bfs代码实现如下

代码CPP · 53 行

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=105;
struct node{
    int x,y; //存放位置
}Node;
int n,m; //矩阵大小
int matrix[maxn][maxn]; //01矩阵
bool inq[maxn][maxn]; //记录是否入过队
int X[4]={0,0,1,-1},Y[4]={1,-1,0,0}; //坐标增量数组
bool judge(int x,int y){
    if(x>m||x<1||y>n||y<1||inq[x][y]||matrix[x][y]==0) return false;
    //只要出界||入过队||在该点不为1,就不访问
    return true;
}
//访问位置(x,y)所在的块，设置一个块内的1的inq为true
void bfs(int x,int y){
    queue<node> q;
    Node.x=x;Node.y=y;
    q.push(Node);
    while(!q.empty()){
        node top=q.front(); //取队首元素top
        q.pop();
        for(int i=0;i<4;i++){ //得到相邻位置
            int newX=top.x+X[i],newY=top.y+Y[i];
            if(judge(newX,newY)){ //如果这个新位置是符合要求的，需要访问
                Node.x=newX;Node.y=newY;
                q.push(Node); //入队
                inq[newX][newY]=true; //已经入过队
            }
        }
    }
}
int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>matrix[i][j];
        }
    }
    int ans=0; //记录答案（块数
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(matrix[i][j]==1&&!inq[i][j]){ //如果这个位置是1而且没有被访问过
                ans++; //块数++
                bfs(i,j);
            }
        }
    }
    cout<<ans;
}

当然也可以使用dfs来实现

代码CPP · 42 行

#include<iostream>
#include<algorithm>
using namespace std;
/*dfs的思路：
从输入的点开始搜索，如果碰到0了就return
否则走岔路口：往四个方向走*/
const int maxn=105;
int m,n,matrix[maxn][maxn];
int X[4]={0,0,1,-1},Y[4]={1,-1,0,0}; //坐标增量数组
bool visited[maxn][maxn];//记录是否查询过
bool judge(int x,int y){
    if(x<1||x>m||y<1||y>n||visited[x][y]||!matrix[x][y]) return false;
    //只要出界||入过队||在该点不为1,就不访问
    return true;
}
//搜索一个块内，并标记为true
void dfs(int x,int y){
    if(!judge(x,y)) return;
    visited[x][y]=true;
    for(int i=0;i<4;i++){
        int newX=x+X[i],newY=y+Y[i];
        dfs(newX,newY);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>matrix[i][j];
        }
    }
    int ans=0; //记录答案（块数
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(matrix[i][j]&&!visited[i][j]){ //如果这个位置是1而且没有被访问过
                dfs(i,j);
                ans++;
            }
        }
    }
    cout<<ans;
}

接下来再来看一个例题

给定一个大小为n*m的迷宫，其中*代表不可通过的墙壁，而'.'代表平地，S表示起点，T表示终点。在移动过程中，如果当前位置是(x,y) （下标从0开始），且每次只能前往上下左右四个位置的平地，求从起点S到终点T的最少步数。

由于求的是最少步数，而bfs是按照层次的顺序来遍历的，因此可以从S开始计数遍历的层数，到达终点T时的层数就是需要求解的起点S到终点T的最少步数。

代码CPP · 47 行

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int n,m;
int X[4]={0,0,-1,1},Y[4]={1,-1,0,0}; //增量数组
char maze[maxn][maxn]; //迷宫
bool inq[maxn][maxn]={false}; //是否已入过队
struct node{
    int x,y;
    int step; //从起点S到该位置的最少步数（即层数）
}S,T,Node; ///起点、终点、临时结点
//判断这个路径是否可行
bool judge(int x,int y){
    if(x<0||x>=n||y<0||y>=m||maze[x][y]=='*'||inq[x][y]) return false;
    return true;
}
//找到一条最短的路径
int bfs(){
    queue<node> q;
    q.push(S);
    while(!q.empty()){
        node top=q.front();
        q.pop();
        if(top.x==T.x&&top.y==T.y) return top.step;
        for(int i=0;i<4;i++){
            int newX=top.x+X[i],newY=top.y+Y[i];
            if(judge(newX,newY)){
                Node.x=newX,Node.y=newY;
                Node.step=top.step+1;
                q.push(Node);
                inq[newX][newY]=true;
            }
        }
    }
    return -1; //无法到达的时候返回-1
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>maze[i][j];
        }
    }
    cin>>S.x>>S.y>>T.x>>T.y;
    S.step=0; //初始化
    cout<<bfs();
}

这里如果要改成“输出最短的路径”

代码CPP · 51 行

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
struct node{
    int x,y;
    vector<pair<int,int> > path;
}S,T,Node; //起点、终点、临时结点
int n,m,maze[maxn][maxn],X[4]={0,0,-1,1},Y[4]={1,-1,0,0};
bool inq[maxn][maxn]={false};//是否已入过队
//判断这个路径是否可行
bool judge(int x,int y){
    if(x<1||x>n||y<1||y>m||maze[x][y]||inq[x][y]) return false;
    return true;
}
void bfs(){
    queue<node> q;
    q.push(S);
    inq[S.x][S.y]=true; //起点入队
    while(!q.empty()){
        node top=q.front();
        q.pop();
        if(top.x==T.x&&top.y==T.y){ //到达终点
            for(const auto& x:top.path){
                cout<<x.first<<' '<<x.second<<endl;
            }
            return;
        }
        for(int i=0;i<4;i++){
            int nowX=top.x+X[i],nowY=top.y+Y[i]; //得到相邻的点
            if(judge(nowX,nowY)){ //如果可以走
                Node.x=nowX,Node.y=nowY;
                Node.path=top.path; //复制之前的路径
                Node.path.push_back({Node.x,Node.y}); //加上现在的路径
                q.push(Node); //入队
                inq[Node.x][Node.y]=true;
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>maze[i][j];
        }
    }
    S.x=1,S.y=1,S.path.push_back({1,1});
    T.x=n,T.y=m;
    bfs();
    return 0;
}

在BFS中设置的inq数组的含义是结点是否已经入过队，而非结点是否已经被访问。

区别：如果设置成是结点是否已经被访问，有可能某个结点正在队列中（但还未被访问）的时候由于其他结点可以到达他而将这个结点再次入队，导致很多结点反复入队。

由于元素入队的时候相当于是在队列里面创造了一个副本，因此在对应的容器中修改并不会修改到另一个元素。

所以当需要对队列中的元素进行修改而不仅仅是访问的时候，队列中存放的元素最好不要是元素本身而应该是它们的编号。

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

struct node{
    int data;
}a[10];
int main(){
    queue<int> q;
    for(int i=1;i<=3;i++){
        a[i].data=i;
        q.push(i); //这里存放的是下标
    }
    a[q.front()].data=100;
    cout<<a[1].data; //输出100
}

第9章提高篇（3）——数据结构专题（2）

9.1 树与二叉树

9.1.1 树的定义与性质

数据结构中将树枝分叉处、树叶、树根抽象为结点（node），其中树根抽象为根节点（root），且对于一棵树最多只存在一个根节点；把树叶抽象为叶子结点（leaf），且叶子结点不再延伸出新的结点；把茎干和树枝统一抽象为边（edge），且一条边只用来连接两个结点（一个端点一个）。

在数据结构中一般把根节点置于最上方（与现实中相反），然后向下延伸出若干条边到达子结点（从而向下形成子树(child），而子结点又向下延伸出边并连接一些结点，直至到达叶子结点。

下面给出树的几个比较实用的概念和性质，其中1,5经常用来出边界数据

树可以没有结点，这种情况称之为空树
树的层次从根节点开始算起，即根结点为第一层，根结点子树的根结点为第二层，以此类推
二叉树的宽度（Width of a Binary Tree）通常指的是同一层中节点的最大个数。
由于一条边连接两个结点，且树中不存在环，因此对于有n个结点的树，边数一定是n-1，且满足连通、边数=顶点数-1的结构一定是一棵树
叶子结点被定义为度为0的结点，因此当树中只有一个结点（即只有根节点）时，根节点也算做叶子结点
结点的深度（depth）是指从根节点（深度为1）开始自顶而下逐层累加至该结点时的深度值，结点的高度（height）是指从最底层叶子结点（高度为1）开始自底向上逐层累加至该结点的高度值。树的深度是指树中结点的最大深度，树的高度是指树中结点的最大高度。对树而言深度==高度，但是具体到某个结点就不一定了。
多棵树组合在一起称之为森林（forest）

9.1.2 二叉树的递归定义

直接给出二叉树的递归定义

要么二叉树没有根节点，是一颗空树
要么二叉树由根节点、左子树、右子树组成，且左子树和右子树都是二叉树

递归定义：用自身来定义自身（比如斐波那契数列F(n)=F(n-1)+F(n-2)就是一种递归定义，用自身序列的元素来定义这个序列本身）

或者说一个家族里面，爷爷是父亲的父亲，曾爷爷是父亲的父亲的父亲，这样直系血缘关系的男性都可以用父亲这个定义来定义

再分析二叉树的递归定义的递归边界和递归式：

递归边界：如果当前结点为空，递归就到达了树的边界
递归式：一个结点连接的两个子树都是二叉树

介绍几种特殊的二叉树

满二叉树：每一层的结点个数都达到了当层能达到的最大结点数
完全二叉树：除了最下面一层以外每一层的结点个数都达到了当层能达到的最大结点数，且最下面一层只是从左到右存在若干的连续结点，而这些连续结点右边的结点全部不存在

从二叉树的角度来理解几个树的概念

层次：把二叉树看作家谱，那么层次就是辈分
孩子结点、父亲结点、兄弟节点、祖先节点、子孙节点：一个结点的子树的根节点称之为该节点的孩子结点，而它称之为该孩子结点的父亲结点，与该结点同父亲的结点称之为该结点的兄弟节点（同一层次非同父亲的结点称之为堂兄弟节点）。如果存在一个从结点X到结点Y从上而下的路径，称X是Y的祖先结点，Y是X的子孙结点。自己就是自己的祖先节点，也是自己的子孙结点。

9.1.3 二叉树的存储结构与基本操作

1.二叉树的存储结构

使用链表来定义，区别是由于二叉树每个结点有两条出边，指针域也变成了两个。如果子树是空树，那么就指向NULL，也把这种链表称为二叉链表

struct node{
    typename data; //数据域
    node* lchild; //指向左子树根节点的指针
    node* rchild; //指向右子树根节点的指针
}

由于二叉树建树之前根节点不存在，地址一般设置为NULL

node *root=NULL;

如果需要新建节点（比如往二叉树里面插入结点的时候）可以使用这个函数

node* newNode(int v){
    node *Node=new node;
    Node->data=v; //结点的数据/权值为v
    Node->lchild=Node->rchild=NULL; //初始状态下没有左右孩子
    return Node;
}

2.二叉树结点的查找、修改

查找：在给定数据域的条件下，在二叉树中找到所有数据域为给定数据域的结点

修改：在查找的基础上，将它们的数据域修改为给定的数据域

void search(node* root,int x,int newData){
    if(root==NULL) return;
    if(root->data==x) root->data=newData;
    //往左右子树递归查找
    search(root->lchild,x,newData);
    search(root->rchild,x,newData);
}

3.二叉树结点的插入

可以这样考虑：查找失败的位置就是该插入的位置

//insert函数将在二叉树中插入一个数据域为x的新结点
//注意根结点root要使用引用
void insert(node* &root,int x){
    if(root==NULL){ //查找失败：插入位置：递归边界
        root=newNode(x);
        return;
    }
    if(由二叉树的性质，x应该插在左子树){
        insert(root->lchild,x);
    }
    else{
        insert(root->rchild,x);
    }
}

为什么root一定要引用呢？这是因为在insert函数中将新建的结点赋给了root，如果不使用引用这个语句就无法作用到原变量（即上一层的root->lchild和root->rchild）上去，也就不能把新结点接到二叉树上面去，因此insert函数必须加引用

判断是否需要加引用的方法：如果函数中需要新建结点，即对二叉树的结构进行修改，就需要加引用；如果是指修改当前已有结点的内容或只是遍历树，就不需要加引用。

至于有时候可能判断不出来，不妨试一下加引用和不加引用的区别再来进行选择。

新建结点之后务必令新结点的左右指针域为NULL，表示这个新结点暂时没有左右子树

4.二叉树的创建

二叉树的创建其实就是二叉树结点的插入过程，而插入所需要的结点数据域一般都会由题目给出。一般是把需要插入的数据存在数组中然后再一个一个insert进去，最终返回指向根节点的指针root

//二叉树的建立
node* Create(int data[],int len){
    node* root=NULL;
    for(int i=0;i<len;i++){
        insert(root,data[i]);
    }
    return root;
}

5.二叉树存储结构图示

root==NULL是结点地址为NULL，也即结点不存在

而*root==NULL是错误的，因为这个意思是root指向的空间为空，但无法说明地址是否为空

6.完全二叉树的存储结构

对于完全二叉树来说有更方便的存储方法。假设从上到下从左到右从1开始编号：

对于完全二叉树中的任何一个结点（设编号为x）则其左孩子的编号一定是2x而右孩子的编号一定是2x+1

因此可以建立一个大小为$2^k$的数组存放所有结点的信息，其中k为完全二叉树的最大高度，其中1号位存放的是根节点（不从0开始）

且该数组中元素存放的顺序恰好为该完全二叉树的层序遍历序列，而判断某个结点是否为叶结点的标志是：该结点（记下标为root）的左子节点（为什么是左子节点？因为完全二叉树允许右边全空）的编号root*2大于结点总个数；判断某个结点是否为空节点的标志是该结点下标大于结点总个数n

9.2 二叉树的遍历

指通过一定顺序访问二叉树中的所有节点。

把一颗二叉树分为3个部分：根结点、左子树、右子树，然后这样就可以递归遍历。

前三种遍历无论是哪一种，都有左子树一定先于右子树遍历，且所谓的”先中后“都是指根结点root在遍历中的位置。

9.2.1 先序遍历

1.先序遍历的实现

先访问根结点root，再访问左子树和右子树。顺序为根->左->右

考虑递归式：顺序为根->左->右

递归边界：访问到子树为空树即死胡同

void preorder(node *root){
	if(root==NULL) return;
	//访问根结点root，例如将其数据域输出
	cout<<root->data;
	//访问左子树
	preorder(root->lchild);
	//访问右子树
	preorder(root->lchild);
}

2.先序遍历序列的性质

由于先序遍历先访问根结点，因此对于一棵二叉树的先序遍历序列，序列的第一个一定是根结点。

9.2.2 中序遍历

1.中序遍历的实现

左子树->根节点->右子树

void inorder(node *root){
	if(root==NULL) return;
	//访问左子树
	inorder(root->lchild);
	cout<<root->data; //把根结点的访问放在左右子树之间
	inorder(root->rchild);
}

2.中序遍历序列的性质

只要知道根结点，就可以通过根结点在中序遍历序列中的位置区分出左右子树。

9.2.3 后序遍历

1.后序遍历的实现

左子树->右子树->根节点

void postorder(node* root){
	if(root==NULL) return;
	postorder(root->lchild);
	postorder(root->rchild);
	cout<<root->data;
}

2.后序遍历序列的性质

序列的最后一个一定是根节点。

无论是先序遍历序列还是后序遍历序列，都必须知道中序遍历序列才能唯一地确定一棵树。

因为只有通过中序遍历序列才能利用根结点把左右子树分开从而递归生成一棵二叉树。

当然这个做法必须要保证元素两两不同才能使用。

9.2.4 层序遍历

按照层次的顺序从根结点往下逐层进行遍历，且对同一层的结点从左到右进行遍历。这个比较像BFS。基本思路如下

将根节点加入队列q
取出队首结点并访问之
如果该节点有左孩子，将左孩子入队
如果该节点有右孩子，将右孩子入队
返回2.直到队列为空

void LayerOrder(node *root){
	queue<node*> q; //注意队列里面是存放地址
	q.push(root);
	while(!q.empty()){
		node* top=q.front();
		q.pop();
		//（访问队首元素）
		if(top->lchild!=NULL) q.push(top->lchild);
		if(top->rchild!=NULL) q.push(top->rchild);
	}
}

可以发现这里队列中的元素是node*而不是node，这是因为之前提到过queue中存放的只是元素的副本，如果想要对原元素进行修改就存放地址也就是node*型变量。

另外，许多时候题目要求计算出每个结点所在的层次，这个时候需要在二叉树结点的定义中添加一个layer变量

代码CPP · 23 行

struct node{
    int data,layer;
    node* lchild;
    node* rchild;
};
void LayerOrder(node *root){
    queue<node*> q;
    root->layer=0; //设置根结点的层号为0
    q.push(root);
    while(!q.empty()){
        node* top=q.front();
        q.pop();
        //访问队首元素
        if(top->lchild!=NULL){
            top->lchild->layer=top->layer+1;
            q.push(top->lchild);
        }
        if(top->rchild!=NULL){
            top->rchild->layer=top->layer+1;
            q.push(top->rchild);
        }
    }
}

最后解决一个重要的问题，给定一棵二叉树的先序遍历序列和中序遍历序列，重建这棵二叉树。

设已知先序序列为$pre_1、pre_2、\cdots 、pre_n$，中序序列为$in_1、in_2、\cdots、in_n$，则$pre_1$是当前二叉树根结点。

又由中序序列可知，当前二叉树的根结点将中序序列划分为左子树和右子树。因此需要在中序序列中找到$in_k=pre_1$这样就在中序序列中找到了根结点。易知左子树结点个数为numLeft=k-1，于是左子树的先序序列区间就是[2,k]，中序序列区间是[1,k-1]；右子树的先序序列区间是[k+1,n]，中序序列区间是[k+1,n]，于是就只需要往左子树和右子树递归构建二叉树即可。

事实上如果当前递归过程中先序序列的区间为[preL,preR]，中序序列的区间为[inL,inR]，那么左子树的结点个数为numLeft=k-inL，这样左子树的先序序列区间就是[preL+1,preL+numLeft]，左子树的中序序列区间是[inL,k-1]；右子树的先序序列区间是[preL+numLeft+1,preR]，中序序列区间是[k+1,inR]。

递归边界是当先序序列的长度小于0时，当前二叉树不存在。

代码CPP · 19 行

int pre[],in[]; //先序序列和中序序列
//当前先序序列区间为[preL,preR]，中序序列区间为[inL,inR]，返回根结点地址]
node* create(int preL,int preR,int inL,int inR){
    if(preL>preR) return NULL;
    node* root=new node;
    root->data=pre[preL];
    int k;
    for(k=inL;k<=inR;k++){ //这里循环变量可以不使用i
        if(in[k]==root->data) break; //在中序序列中找到根结点
    }
    int numLeft=k-inL;
    //左子树的结点个数为numLeft=k-inL，左子树的先序序列区间就是[preL+1,preL+numLeft]，左子树的中序序列区间是[inL,k-1]；
    //右子树的先序序列区间是[preL+numLeft+1,preR]，中序序列区间是[k+1,inR]
    //返回左子树的根结点地址，赋值给root的左指针
    root->lchiild=create(preL+1,preL+numLeft,inL,k-1);
    //返回右子树的根结点地址，赋值给root的右指针
    root->rchild=create(preL+numLeft+1,preR,k+1,inR);
    return root; //返回根结点地址
}

如果使用静态实现

代码CPP · 22 行

struct node{
    char data;
    int lchild;
    int rchild;
}Node[30];
int idx=0	;
//Node[0]为根结点

int create(int preL,int preR,int inL,int inR){
    if(preL>preR) return -1;
    int cur=idx++;
    Node[cur].data=pre[preL];
    int k;
    for(k=inL;k<=inR;k++){
        if(in[k]==pre[preL]) break;
    }
    int numLeft=k-inL;
    
    Node[cur].lchild=create(preL+1,preL+numLeft,inL,k-1);
    Node[cur].rchild=create(preL+numLeft+1,preR,k+1,inR);
    return cur;
}

结论：中序序列可以与先序序列、后序序列、层序序列中的任意一个来构建一棵唯一的二叉树，而后面三个两两搭配均不可以。

【PAT A1020】 Tree Traversals

给出一棵二叉树的后序遍历序列和中序遍历序列，求这颗二叉树的层序遍历序列。

考虑先用后序遍历序列和中序遍历序来重建二叉树，再对二叉树进行层序遍历。

代码CPP · 46 行

#include<bits/stdc++.h>
using namespace std;
const int maxn=35;
struct node{
    int data;
    node *lchild,*rchild;
};
int n,in[maxn],post[maxn];
//中序序列的开始和结尾，后序序列的开始和结尾
//返回构建出的二叉树的根结点
node *create(int inL,int inR,int postL,int postR){
    if(postL>postR) return NULL;
    //初始化根结点
    node* root=new node;
    root->data=post[postR];
    //先找到根节点所在的位置
    int k;
    for(k=inL;k<=inR;k++){
        if(in[k]==post[postR]) break;
    }
    int numLeft=k-inL; //左子树的结点个数
    //左子树：中序序列区间为[inL,k-1] 后序序列区间为[postL,postL+numLeft-1]
    root->lchild=create(inL,k-1,postL,postL+numLeft-1);
    //右子树：中序序列区间为[k+1,inR] 后序序列区间为[postL+numLeft,postR-1]
    root->rchild=create(k+1,inR,postL+numLeft,postR-1);
    return root;
}
//对二叉树进行层序遍历
void layerOrder(node *root){
    queue<node*> q;
    q.push(root);
    while(!q.empty()){
        node *top=q.front();
        q.pop();
        cout<<top->data<<' ';
        if(top->lchild!=NULL) q.push(top->lchild);
        if(top->rchild!=NULL) q.push(top->rchild);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>post[i];
    for(int i=1;i<=n;i++) cin>>in[i];
    node *root=create(1,n,1,n);
    layerOrder(root);
}

9.2.5 二叉树的静态实现

struct node{
    typename data;
    int lchild;
    int rchild;
}Node[maxn];

int idx=0;
int newNode(int v){
    Node[idx].data=v;
    Node[idx].lchild=-1; // 以-1表示空
    Node[idx].rchild=-1;
    return idx++;
}

诸如此类的。反正就是静态化。

需要注意的是与非静态的二叉树的层序遍历相同，静态实现的二叉树的层序遍历在定义队列的时候应该是queue<int> q，其中int是下标，而不应该是queue<node> q。

9.3 树的遍历

一般意义上的树，即子结点个数不限且子结点没有先后次序。

9.3.1 树的静态写法

令指针域存放其所有子结点的地址（或者为其单开一个数组存放所有子结点的地址）。

静态写法如下：

struct node{
    typename data; //数据域
    vector<int> child; //指针域，存放所有子结点的下标
}Node[maxn];

与二叉树的静态实现类似，当需要新建一个结点时，就按顺序从数组中取出一个下标即可。

int idx=0;
int newNode(int v){
    Node[idx].data=v;
    Node[idx].child.clear(); //清空子结点
    return idx++; //返回结点下标并令idx自增
}

不过一般题目里涉及非二叉树的树的考察的时候都会给出结点的编号，且一般都是0-n-1,所以不需要newNode函数。

9.3.2 树的先根遍历

即先访问根结点，再去访问所有子树。

void preOrder(int root){
    //访问当前结点，比如输出
    for(const auto&x:Node[root].child){
	preOrder(x); //递归访问结点root的所有子结点
    }
}

在树的先根遍历代码中，虽然没有显式地写出递归边界，但实际上递归边界是存在的。递归边界是由树的结构决定的，具体来说，当遍历到一个叶子节点时，该节点没有子节点，因此不会进入for循环，递归调用自然终止。

9.3.3 树的层序遍历

代码CPP · 21 行

struct node{
    int layer;
    int data;
    vector<int> child;
}Node[maxn];
void layerOrder(int root){
    queue<int> q; //记得queue里面存放的是指针/下标
    Node[root].layer=0;
    q.push(root);
    while(!q.empty()){
        int top=q.front();
        q.pop();
        cout<<Node[top].data;
        for(const auto&x:Node[top].child){
            if(x!=-1){
                Node[x].layer=Node[top].layer+1;
                q.push(x);
            }
        }
    }
}

9.3.4 从树的遍历看DFS和BFS

1.DFS与先根遍历

对于所有合法的DFS求解过程，都可以把它画成树的形式，此时死胡同等价于树中的叶子结点，而岔道口等价于树中的非叶子结点，而且对这棵树的DFS遍历过程就是树的先根遍历的过程。

2.BFS与层序遍历

对所有合法的BFS求解过程，也可以画成树的形式。

【PAT A1053] Path of Equal Weight

给定一棵树和每个结点的权值，求所有从根结点到叶子结点的路径，使得每条路径上的结点的权值之和等于给定的常数S。如果有多条这样的路径则按路径非递增的顺序输出。其中路径的大小指的是类似于字典序的排序(a1->a2->....an)

代码CPP · 51 行

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=105;
int n,m,S; //树的结点数，非叶子结点个数（边数），给定权
int id,k,child;
//记录路径(记录的是结点的编号)，有更高权值的路径应优先输出，而读入时已经对权值排好了序，因此dfs的时候总是会优先访问权值更大的进行输出
vector<int> path;
struct node{
    int data;
    int layer;
    vector<int> child;
}Node[maxn];
bool cmp(int a,int b){
    return Node[a].data>Node[b].data;
}
void dfs(int idx,int sum){ //idx是目前访问的结点编号，sum是目前的权值和
    if(sum>S) return; //剪枝
    if(sum==S){
        if(Node[idx].child.empty()){ //如果这个时候是叶子结点才输出,否则直接return
            for(const auto&x:path) printf("%d ",Node[x].data);
            printf("\n");
        }
        return;
    }
    for(const auto&x:Node[idx].child){//枚举所有孩子结点
        //选择这个孩子结点
        path.push_back(x); //将结点child加到路径path末尾 
        dfs(x,sum+Node[x].data); //递归进入下一层
        //不选择这个孩子结点,回溯
        path.pop_back();
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&S);
    for(int i=0;i<n;i++){
        scanf("%d",&Node[i].data);
    }
    for(int i=0;i<m;i++){
        scanf("%d%d",&id,&k);
        for(int i=0;i<k;i++){
            scanf("%d",&child);
            Node[id].child.push_back(child); 
        }
        //输出的时候按照路径的权值输出，先把孩子的权值排好序
        sort(Node[id].child.begin(),Node[id].child.end(),cmp);
    }
    path.push_back(0); //插入根结点
    dfs(0,Node[0].data);
}

9.4 二叉查找树（BST）

9.4.1 二叉查找树的定义

要么是空树
若左子树不空，则左子树上所有结点的值均小于等于它的根结点的值
若右子树不空，则右子树上所有结点的值均大于它的根结点的值
左、右子树也分别为二叉排序树

其实有两种定义方式，还有一种是

若左子树不空，则左子树上所有结点的值均小于它的根结点的值

若右子树不空，则右子树上所有结点的值均大于它的根结点的值

没有权值相等的结点

这种情况下在结点里面加一个cnt变量记录这个权值的出现次数。

9.4.2 二叉查找树的基本操作

1.查找

代码CPP · 19 行

struct node{
    int v;
    int lchild,rchild;
    int siz; //(两子树+自己本身)的大小（结点数之和）
}bst[maxn];

int search(int v,int idx){
    if(idx==0) return 0; //查找失败
    
    if(v==bst[idx].v){
        return idx;
    }
    else if(v<bst[idx].v){
        search(v,bst[idx].lchild);
    }
    else{
        search(v,bst[idx].rchild);
    }
}

注：统一采用静态实现

2.插入

代码CPP · 25 行

void insert(int v,int idx){ //v表示权值，idx表示当前的结点编号
    bst[idx].siz++;
    if(v>bst[idx].v){ //说明v应该插入到右子树
        if(bst[idx].rchild!=0){
            insert(v,bst[idx].rchild);
        }
        else{ //不存在右孩子
            cnt++;
            bst[cnt].v=v;
            bst[cnt].siz=1;
            bst[idx].rchild=cnt;
        }
    }
    else{
        if(bst[idx].lchild!=0){
            insert(v,bst[idx].lchild);
        }
        else{
            cnt++;
            bst[cnt].v=v;
            bst[cnt].siz=1;
            bst[idx].lchild=cnt;
        }
    }
}

3.删除

删除二叉搜索树（BST）中的节点有三种情况：

目标节点是叶子节点：直接删除即可。
目标节点只有一个子节点：用它的唯一子节点代替它。
目标节点有两个子节点：找到它的前驱（左子树的最大值）或后继（右子树的最小值）替换它，然后递归删除这个前驱或后继节点。

先给出找前驱和后继的函数

代码CPP · 29 行

int findPre(int v){
    int idx=1; //从根结点开始搜索
    int ans=-inf;
    while(idx){
        if(bst[idx].v<v){
            ans=bst[idx].v;
            idx=bst[idx].rchild;
        }
        else{
            idx=bst[idx].lchild;
        }
    }
    return ans;
}

int findPost(int v){
    int idx=1;
    int ans=inf;
    while(idx){
        if(bst[idx].v>v){
            ans=bst[idx].v;
            idx=bst[idx].lchild;
        }
        else{
            idx=bst[idx].rchild;
        }
    }
    return ans;
}

再给出删除的函数

代码CPP · 35 行

void remove(int &idx, int v) {
    if (idx == 0) return; // 树为空，直接返回

    if (v < bst[idx].v) {
        // 目标值在左子树
        remove(bst[idx].lchild, v);
    } else if (v > bst[idx].v) {
        // 目标值在右子树
        remove(bst[idx].rchild, v);
    } else {
        // 找到目标节点
        if (bst[idx].lchild == 0 && bst[idx].rchild == 0) {
            // 情况1：叶子节点，直接删除
            idx = 0;
        } else if (bst[idx].lchild == 0) {
            // 情况2：只有右子树
            idx = bst[idx].rchild;
        } else if (bst[idx].rchild == 0) {
            // 情况2：只有左子树
            idx = bst[idx].lchild;
        } else {
            // 情况3：有两个子节点
            int preIdx = bst[idx].lchild;
            while (bst[preIdx].rchild) { // 找前驱
                preIdx = bst[preIdx].rchild;
            }
            bst[idx].v = bst[preIdx].v; // 用前驱值替换
            remove(bst[idx].lchild, bst[preIdx].v); // 递归删除前驱
        }
    }

    if (idx != 0) { // 维护子树大小信息
        bst[idx].siz = 1 + bst[bst[idx].lchild].siz + bst[bst[idx].rchild].siz;
    }
}

9.4.3 二叉查找树的性质

9.5 平衡二叉树（AVL树）

9.5.1 平衡二叉树的定义

9.5.2 平衡二叉树的基本操作

9.6 并查集

9.6.1 并查集的定义

并查集是一种维护集合的数据结构。

“并”“查”“集”分别取自合并、查找、集合。

并查集支持以下两个操作

合并：合并两个集合
查找：判断两个元素是否在一个集合

实现方式：

int father[N];

其中father[i]表示元素i的父亲结点，而父亲结点本身也是这个集合内的元素。比如father[1]=2表示元素1的父亲结点是元素2，以这种父系关系来表示元素所属的集合。另外如果father[i]==i则说明元素i是该集合的根结点，但对于同一个集合来说只存在一个根结点，且将其作为所属集合的标识。

9.6.2 并查集的基本操作

1.初始化

一开始每个元素都是独立的一个集合，只需要全令father[i]=i或令father[i]=-1

2.查找

由于规定了同一个集合只存在一个根结点，因此查找操作就是对给定的结点去寻找其根结点的过程，实现的方式可以是递推或者递推。思路都是反复寻找父亲结点直到寻找到根结点。

int findFather(int x){
    while(x!=father[x]){
        x=father[x];
    }
    return x;
}

int findFather(int x){
    if(x==father[x]) return x;
    else return findFather(father[x]);
}

3.合并

合并指的是把两个集合并成一个集合。题目中一般给出两个元素然后要求把这两个元素所在的集合合并。具体实现是先判断两个元素是否属于一个集合，只有当两个元素属于不同集合的时候才合并，而合并的过程一般是把其中一个集合的根结点的父亲指向另一个集合的根结点。思路如下：

对于给定的两个元素a b，先判断他们是否属于同一个集合，调用查找函数判断根结点是否相同即可。
合并两个集合：在1中已经获得了两个元素的根结点faA和faB，因此只需要把其中一个的父亲结点指向另一个结点。比如令father[faA]=faB或者反过来都可以。

void Union(int a,int b){
    int faA=findFather(a);
    int faB=findFather(b);
    if(faA!=faB){
        father[faA]=faB;
    }
}

9.6.3 路径压缩

上面提到的函数都没有进行优化。下面考虑一种极端情况，即题目给出的元素数量很多而且形成一条链，那么这个查找函数的效率就会很低。下面提出一种优化思路。

因为我们findFather()函数就只是为了寻找根结点，我们完全可以把当前查询结点的路径上的所有结点的父亲都指向根结点，查找的时候就不需要一直回溯去寻找父亲，时间复杂度降为$O(1)$。

进行转换的步骤可以这样概括：

按照原来的写法获得x的根结点r
重新从x开始走一遍寻找根结点的过程，把路径上经过的所有结点的父亲全部改为根结点r。

int findFather(int x){
    int a=x; //由于x在下面的while循环会变成根结点，先存一下原来的x
    while(x!=father[x]){
        x=father[x];
    }
    //到这里x存放的是根结点，下面把路径上所有结点的father都改成根结点。
    while(a!=father[a]){
        int z=a;
        a=father[a];
        father[z]=x;
    }
    return x;
}

也有递归写法

int findFather(int x){
    return x==father[x] ? x : father[x]=findFather(father[x]);
}

下面给出一个简单使用并查集的题目

例题好朋友

引用题目描述有一个叫作“数码世界”的奇异空间，在数码世界里生活着许许多多的数码宝贝，其中有些数码宝贝之间可能是好朋友。并且数码世界有两条不成文的规...

题目描述

有一个叫作“数码世界”的奇异空间，在数码世界里生活着许许多多的数码宝贝，其中有些数码宝贝之间可能是好朋友。并且数码世界有两条不成文的规定:

第一，数码宝贝A和数码宝贝B是好朋友等价于数码宝贝B和数码宝贝A是好朋友。

第二，如果数码宝贝A和数码宝贝C是好朋友，而数码宝贝B和数码宝贝C也是好朋友，那么A和B也是好朋友。现在给出这些数码宝贝中所有好朋友的信息，问:可以把这些数码宝贝分成多少组，满足每组中的任意两只数码宝贝都是好朋友，且任意两组之间的数码宝贝都不是好朋友。

输入格式

输入的第一行有两个正整数n(n<=100)和m(m<=100)，分别表示数码宝贝的个数和好朋友的组数，其中数码宝贝编号为1~n。接下来有m行，每行两个正整数a和b，表示数码宝贝a和数码宝贝b是好朋友。

样例输入
4 2
1 4
2 3
样例输出
2

本题是一个并查集模型，可以把题目中的“组”视为集合，而题目中给出的好朋友关系视为两个结点之间的边，那么在输入这些好朋友关系时就可以同时对它们进行并查集的合并操作。

对于集合个数的求解，需要用到这条规则：对于同一个集合来说只存在一个根结点，且将其作为所属集合的标识。因此开一个bool flag[n]来记录每个结点是否作为某个集合的根结点，这样在处理完输入数据之后就可以遍历所有元素，令它所在的集合的根结点的flag设置为true，最后累加flag中的元素即可。代码如下

代码CPP · 49 行

#include<bits/stdc++.h>
using namespace std;

const int maxn=110;
int father[maxn];
bool flag[maxn];

int findFather(int x){
    int a=x;
    while(x!=father[x]){
        x=father[x];
    }
    while(a!=father[a]){
        int z=a;
        a=father[a];
        father[z]=x;
    }
    return x;
}
void Union(int a,int b){
    int faA=father[a];
    int faB=father[b];
    if(faA!=faB){
        father[faA]=faB;
    }
    return;
}

int main(){
    int n,m,a,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        father[i]=i;
        //flag[i]=false; 全局变量默认是false
    }
    for(int i=0;i<m;i++){
        cin>>a>>b;
        Union(a,b);
    }
    for(int i=1;i<=n;i++){
        flag[findFather(i)]=true;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=(int)flag[i];
    }
    cout<<ans;
    return 0;
}

9.7 堆

9.7.1 堆的定义与基本操作

9.7.2 堆排序

9.8 哈夫曼树

9.8.1 哈夫曼树

9.8.2 哈夫曼编码

第10章提高篇（4）——图算法专题

10.1 图的定义和相关术语

图由顶点和边组成。分为有向图和无向图。

顶点的度：与该顶点相连的边的条数。

对于有向图：顶点的出边条数称为出度，入边条数称为入度。

顶点和边的权值分别称为点权和边权。

10.2 图的存储

10.2.1 邻接矩阵

设图G(V,E)的顶点编号从0到n-1，则可以令二维数组G[n][n]的两维分别表示图的顶点标号。

若G[i][j]==1 -> 顶点i和j之间有边，若为0则没有。另外如果存在边权则令G[i][j]存放边权，而对于不存在的边就设边权为0,-1,或inf。

对于无向图来说，邻接矩阵是一个对称矩阵。

为了防止MLE，邻接矩阵只适用于顶点数目不太大(<=1000)的题目。

10.2.2 邻接表

设图G(V,E)的顶点编号从0到n-1，每个顶点都可能会有若干条出边，如果把同一个顶点的所有出边放到一个列表中，那么n个顶点就会有n个列表（没有出边则对应空表）。这n个列表被称为图G的邻接表，记作Adj[n]，其中Adj[i]存放顶点i的所有出边组成的列表。

这里我们使用vector来实现邻接表。

struct Node{
  int v; //边的终点编号
  int w; //边权
  Node(int _v,int _w):v(_v),w(_w){};
}
vector<Node> Adj[n];

然后如果我们这里想要添加从1号到达3号顶点的有向边，边权为4，就可以这样：

Adj[1].emplace_back(3,4);

如果想要添加一条无向边，可以这样设计一个函数

// 添加无向边 (u, v, w)
void addEdge(int u, int v, int w) {
    Adj[u].emplace_back(v, w);  // 在u的邻接表中添加边 (u, v, w)
    Adj[v].emplace_back(u, w);  // 在v的邻接表中添加边 (v, u, w)
}

这样，当添加无向边时，不仅将 (v, w) 添加到 Adj[u] 中，也会将 (u, w) 添加到 Adj[v] 中，保证图的双向性质。

10.3 图的遍历

10.3.1 采用深度优先搜索（DFS）法遍历图

首先介绍两个概念：

连通分量：在无向图中，如果两个顶点之间可以相互到达（可以是通过一定路径间接到达），那么就称这两个顶点连通。如果图G(V,E)的任意两个顶点均连通，则称图G为连通图，否则为非连通图，且称其中的极大连通子图为连通分量。
强连通分量：在有向图中，如果两个顶点可以各自通过一条有向路径到达另一个顶点，就称这两个顶点强连通。如果图G(V,E)的任意两个顶点都强连通，则称图G为强连通图；否则称为非强连通图，且称其中的极大强连通子图为强连通分量。

为了叙述上的方便下面把连通分量和强连通分量统称为连通块。

所以要遍历整个图就是要对所有连通块进行遍历。DFS遍历图的基本思路就是把以及访问过的顶点设置为已访问，在下次递归碰到这个顶点时就不再处理，直到整个图的顶点都被标记为已访问。

下面是一份DFS的伪代码

DFS(u){ //访问顶点u
vis[u]=true;
    for(从u出发能到达的所有顶点v){
        if(!vis[v]) DFS(v);
    }
    DFSTraveG{ //遍历图G
        for(G的所有顶点u){
            if(!vis[u]) DFS(u); //访问u所在的连通块
    }
}

在这份代码的基础上可以代入邻接矩阵和邻接表的代码，得到如下模板：

代码CPP · 25 行

//邻接矩阵版本
cosnt int maxv=1000; //最大顶点数
const int inf=0x3f3f3f3f;

int n,G[maxv][maxv];
bool vis[maxv]={false};

void dfs(int u,int depth){
    vis[u]=true;
    //如果需要对u进行一些操作可以在这里进行
    //下面对所有从u出发能到达的分支顶点进行枚举
    for(int v=0;v<n;v++){
        if(!vis[v]&&G[u][v]!=inf){
            dfs(v,depth+1); //访问v，深度++
        }
    }
}

void DFSTrave(){ //遍历图G
    for(int u=0;u<n;u++){
        if(!vis[u]){
            dfs(u+1);
        }
    }
}

代码CPP · 22 行

//邻接表版本
cosnt int maxv=1000; //最大顶点数
const int inf=0x3f3f3f3f;

vector<int> Adj[maxv];
int n; //顶点数
bool vis[maxv]={false};

void dfs(int u,int depth){
    vis[u]=true;
    //如果要对u进行一些操作可以在这里
    for(int i=0;i<(int)Adj[u].size();i++){
        int v=Adj[u][i];
        if(!vis[v]) dfs(v,depth+1);
    }
}

void DFSTrave(){
    for(int u=0;u<n;u++){
        if(!vis[u]) dfs(u,1);
    }
}

【PAT A1034】 Head of a gang

代码CPP · 69 行

#include<bits/stdc++.h>
using namespace std;

const int maxn=2010;
const int inf=0x3f3f3f3f;
int G[maxn][maxn];
int weight[maxn];
bool vis[maxn];
map<string,int> stringToInt;
map<int,string> intToString;
map<string,int> Gang;
int n,k;
int numPerson;

int change(string s){
    if(stringToInt.find(s)!=stringToInt.end()){
        return stringToInt[s];
    }
    else{
        stringToInt[s]=numPerson;
        intToString[numPerson]=s;
        return numPerson++;
    }
}

void dfs(int now,int &head,int &numMember,int &totalValue){
    vis[now]=true;
    numMember++;
    if(weight[now]>weight[head]) head=now;
    for(int v=0;v<numPerson;v++){
        if(!vis[v]&&G[now][v]!=0){
            totalValue+=G[now][v];
            dfs(v,head,numMember,totalValue);
        }
    }
}

void dfstrave(){
    for(int i=0;i<numPerson;i++){
        if(!vis[i]){
            int head=i,numMember=0,totalValue=0;
            dfs(i,head,numMember,totalValue);
            if(numMember>2&&totalValue>k){
                Gang[intToString[head]]=numMember;
            }
        }
    }
}

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        string s1,s2;
        int w;
        cin>>s1>>s2>>w;
        int id1=change(s1);
        int id2=change(s2);
        weight[id1]+=w;
        weight[id2]+=w;
        G[id1][id2]+=w;
        G[id2][id1]+=w;
    }
    dfstrave();
    cout<<Gang.size()<<"\n";
    for(auto &[x,y]:Gang){
        cout<<x<<" "<<y<<"\n";
    }
    return 0;
}

10.3.2 采用广度优先搜索（BFS）法遍历图

代码CPP · 28 行

//邻接矩阵版本
int n;
int G[maxv][maxv];
bool inq[maxv];

void bfs(int u){ //遍历顶点u所在的连通块
    queue<int> q;
    q.push(u);
    inq[u]=true;
    while(!q.empty()){
        int top=q.front();
        q.pop();
        for(int v=0;v<n;v++){
            if(!inq[v]&&G[top][v]!=0){
                q.push(v);
                inq[v]=true;
            }
        }
    }
}

void bfsTrave(){
    for(int i=0;i<n;i++){
        if(!inq[i]){
            bfs(i);
        }
    }
}

代码CPP · 28 行

//邻接表版本
vector<int> Adj[maxv];
int n;
bool inq[maxv];

void bfs(int u){
    queue<int> q;
    q.push(u);
    inq[u]=true;
    while(!q.empty()){
        int top=q.front();
        q.pop();
        for(int v:Adj[top]){
            if(!inq[v]){
                q.push(v);
                inq[v]=true;
            }
        }
    }
}

void bfsTrave(){
    for(int i=0;i<n;i++){
        if(!inq[i]){
            bfs(i);
        }
    }
}

如果需要记录每个结点的层次，可以使用结构体

代码CPP · 26 行

//邻接表版本
struct node{
    int v;
    int layer;
}Node;
vector<node> Adj[maxv];
int n;
bool inq[maxv];

void bfs(int s){ //s为起始顶点编号
    queue<node> q;
    Node.v=s;Node.layer=0;
    q.push(Node);
    inq[Node.v]=true;
    while(!q.empty()){
        node top=q.front();
        q.pop();
        for(node next:Adj[top.v]){
            next.layer=top.layer+1;
            if(!inq[next.v]){
                q.push(next);
                inq[next.v]=true;
            }
        }
    }
}

10.4 最短路径

这是一个很经典的问题：给定图G(V,E)，求一条从起点到终点的路径，使得这条路径上经过的所有边的边权之和最小。

10.4.1 Dijkstra算法

10.4.2 Bellman-Ford算法和SPFA算法

10.4.3 Floyd算法

10.5 最小生成树

10.5.1 最小生成树及其性质

10.5.2 prim算法

10.5.3 kruskal算法

10.6 拓扑排序

代码CPP · 44 行

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int n,m;
    cin>>n>>m;
    vector<vector<int>> g(n+1);
    vector<int> ind(n+1,0);
    vector<int> outd(n+1,0);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        ind[b]++;
        outd[a]++;
    }

    queue<int> q;
    for(int i=1;i<=n;i++){
        if(ind[i]==0){
            q.push(i);
        }
    }
	int num=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v:g[u]){
            ind[v]--;
            if(ind[v]==0){
                q.push(v);
            }
        }
        num++;
    }
	//num==m则为DAG，反之
    return 0;
}

10.6.1 有向无环图

10.6.2 拓扑排序

10.7 关键路径

10.7.1 AOV网和AOE网

10.7.2 最长路径

10.7.3 关键路径

第11章提高篇（5）——动态规划专题

11.1 动态规划的递归写法和递推写法

11.1.1 什么是动态规划

是用来解决一类最优化问题的算法思想。简单来说，动态规划将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。动态规划会将每个求解过的子问题的解记录下来。

一般可以使用递推或递归的写法来实现动态规划，其中递归写法又称记忆化搜索

11.1.2 动态规划的递归写法

使用记忆化搜索来计算斐波那契数列

int dp[maxn];
int F(int n){
    if(n<=1) return 1;
    if(dp[n]) return dp[n]; //已经计算过，直接返回结果
    else{
        dp[n]=F(n-1)+F(n-2);
        return dp[n];
    }
}

引出概念：如果一个问题可以被分解成若干子问题，而且这些子问题会重复出现，那么就称这个问题拥有重叠子问题

因此一个问题必须有重叠子问题才能用动态规划去解决

11.1.3 动态规划的递推写法

数塔问题

把一些数字排成数塔的形状，第i层有i个数字，现在要从第一层走到第n层，每次只能走向下一层连接的两个数字中的一个，问：最后将路径上所有数字相加后得到的和最大为多少？

按照题目的描述，使用一个二维数组f去存储存放在第i层的第j个数字，如果尝试去穷举所有路径，那么时间复杂度是$O(2^n)$,无法接受，这是因为会重复访问，解决方法是记录下来一个数字到底层所有路径可以产生的最大值，之后访问这个数的时候直接调用即可。不妨令dp[i][j]表示从第i行第j个数字出发到达底层的所有路径中能得到的最大和，在定义这个数组之后，dp[1][1]就是最终想要的答案，现在我们来求它。

注意到一个细节，如果要求dp[1][1]，就一定要先求出它的两个子问题dp[2][1]和dp[2][2]，即进行了一次决策，是走f[2][1]还是f[2][2]，于是dp[1][1]可以写成这个式子 $$ \mathrm{dp}[1][1]=max(\mathrm{dp[2][1],dp[2][2]})+\mathrm{f[1][1]} $$ 由此可以归纳得到这么一个信息：如果要求出d[i][j]，就一定要求出它的两个子问题d[i+1][j]和d[i+1][j+1]，即进行了一次决策，于是就有 $$ \mathrm{dp}[i][j]=max(\mathrm{dp[i+1][j],dp[i+1][j+1]})+\mathrm{f[i][j]} $$ 把d[i][j]称之为问题的状态，上面的式子称之为状态转移方程，把各状态转移为d[i+1][j]和d[i+1][j+1]。可以注意到状态d[i][j]只和第i+1层的状态有关，而与其他层的状态无关，这样层号为i的状态总是可以由层号为i+1的两个子状态得到。又注意到递归边界应该是数塔的最后一层的dp值总是等于元素本身，即dp[n][j]==f[n][j]，把这种可以直接确定结果的部分称之为边界，而动态规划的递推写法总是从这种边界出发，又通过状态转移方程扩散到整个dp数组。

这样就可以从底层各位置的dp值开始不断向上求，最后就可以得到dp[1][1]，即最后需要的答案。代码实现如下

代码CPP · 33 行

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int n,f[maxn][maxn],dp[maxn][maxn];

//状态转移方程的递归实现，调用时从初始状态调用
int P(int i,int j){
    if(dp[i][j]) return dp[i][j]; //记忆化存储
    if(i==n) return dp[i][j]=f[i][j];
    return dp[i][j]=max(P(i+1,j),P(i+1,j+1))+f[i][j];
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>f[i][j];
        }
    }
    //边界条件
    for(int i=1;i<=n;i++){
        dp[n][i]=f[n][i];
    }
    //从n-1层往上不断计算dp[i][j]
    for(int i=n-1;i>=1;i--){
        for(int j=1;j<=i;j++){
            //状态转移方程
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
        }
    }
    cout<<dp[1][1]<<endl;
    return 0;
}

用递归也可以实现类似的效果

使用递归写法的计算方式是自底而上，即从边界开始不断向上解决问题，直到解决目标问题

而使用递归写法是自顶向下，从目标问题开始将它分解成子问题的组合，直至分解至边界

从上面的问题再引申出一个概念：如果一个问题的最优解可以由其子问题的最优解构造而来，那么称这个问题具有最优子结构。最优子结构保证了动态规划问题中原问题的最优解可以由子问题的最优解推导而来，因此一个问题必须拥有最优子结构才能用动态规划去解决。

需要指出，一个问题必须拥有重叠子问题和最优子结构才能使用动态规划去解决，指出两个概念的区别

分治与动态规划。分治分解出的子问题是不重叠的，而动态规划解决的问题拥有重叠子问题。分治法解决的不一定是最优化问题，而动态规划解决的一定是最优化问题。
贪心与动态规划。都要求原问题有最优子结构。贪心类似于自顶而下，但是并不是等待子问题求解完毕之后再去选择使用哪一个，而是选择一个策略去直接解决一个子问题。而动态规划总是从边界开始得到。

11.2 最大连续子序列和

给定一个数字序列$A_1,A_2, \cdots A_n$，求i,j (1≤i≤j≤n)，使得$A_i+\cdots A_j$最大，输出这个最大和。

样例

-2 11 -4 13 -5 -2

如果暴力来做枚举i和j要$\mathrm{O(n^2)}$的复杂度，而计算a[i]+...+a[j]需要O(n)的复杂度，因此总共复杂度为$\mathrm{O(n^3)}$。如果采用前缀和的方法令s[i]=a[0]+a[1]+...+a[i]，这样a[i]+...+a[j]=s[j]-s[i-1]使得计算时间为O(1)，总复杂度还是$\mathrm{O(n^2)}$，无法接受。

下面介绍动态规划的做法，复杂度为O(n)。

令dp[i]表示以a[i]作为末尾的连续序列的最大和（这里说a[i]必须要作为连续序列的末尾）。

通过设置这么一个dp数组，那么我们无非就是要求从dp[0]到dp[n-1]中的最大值（因为以哪个元素作为结尾是未知的）。接下来想办法求解dp数组
做如下考虑：因为dp[i]必须是以a[i]结尾的连续序列，那么只有两种情况
1. 这个最大和的连续序列只有一个元素即以a[i]开始又以a[i]结束
2. 这个最大和的连续序列有多个元素，即从某处p开始(p<i)，一直到a[i]结尾。
第一种情况最大和就是a[i]本身。

第二种情况最大和是dp[i-1]+a[i]，即a[p]+...+a[i-1]+a[i]=dp[i-1]=a[i] (强行把i和i-1的情况拆开，得到状态方程的思路)

由于只有这两种情况，得到状态转移方程 $$ \mathrm{dp[i]}=max (\mathrm{a[i],dp[i-1]+a[i]}) $$ 这个式子只和i与i之前的元素有关，且边界为dp[0]=a[0]，于是枚举i即可解决问题。

无后效性

状态的无后效性指的是：当前状态记录了历史信息，一旦当前状态确定，就不会再改变，且未来的决策只能在已有的一个或若干个状态的基础上进行，历史信息只能通过已有的状态去影响未来的决策。

对于动态规划可解的问题来说，总会有很多设计状态的方式，但并不是所有状态都具有无后效性，因此必须要设计一个无后效性的状态以及相应的状态转移方程。

设计状态和状态转移方程是动态规划的核心。

11.3 最长不下降子序列（LIS）

在一个数字序列中，找到一个最长的子序列（可以不连续），使得这个序列是不下降的。

暴力法：每个元素有取和不取两种情况，对之进行判断，直到枚举完成，时间复杂度$\mathrm{O(2^n)}$。下面介绍动态规划法。

令dp[i]表示以a[i]结尾的最长不下降子序列长度（与最大连续子序列和问题一样，以a[i]结尾是强制的要求），这样对于a[i]就有两种可能：

如果存在a[i]之前的元素a[j] (j<i) 使得a[j]≤a[i]且dp[j]+1>dp[i]（即把a[i]跟在以a[j]结尾的LIS后面时能比当前以a[i]结尾的LIS长度更长），那么就把a[i]跟在以a[j]结尾的LIS后面，形成一条更长的不下降子列（令dp[i]=dp[j]+1）
如果a[i]之前的元素都比a[i]大，那么a[i]就只能自己形成一条长度为1的LIS

最后以a[i]结尾的LIS长度就是1,2中能形成的最大长度。

由此写出状态转移方程 $$ \mathrm{dp[i]}=max(\mathrm{1,dp[j]+1}) \ (j=1,2,\cdots.i-1&&a[j]<a[i]) \ 边界dp[i]=1（先假设每个元素自成一个子序列） $$ 一个代码实现的案例

int ans=-1; //记录最大的dp[i]
for(int i=1;i<=n;i++){
    dp[i]=1; //先假设每个元素自成一个子序列
    for(int j=1;j<i;j++){
        if(a[i]>=a[j]&&(dp[j]+1>dp[i])){
		dp[i]=dp[j]+1; //状态转移方程用以更新dp[i]
            //也可以是dp[i]=max(dp[i],dp[j]+1); 上面那个判断去掉
        }
    }
    ans=max(ans,dp[i]);
}

11.4 最长公共子序列（LCS）

给定两个字符串（或数字序列）a和b，求一个字符串，使得这个字符串是A和B的最长公共部分的长度（子序列可以不连续）

样例：

"sadstory"和"adminsorry"的最长公共子序列是"adsory"，长度为6。

令dp[i][j]表示字符串a的i号位和字符串b的j号位之前的LCS长度（下标从1开始），如dp[4][5]表示"sads"和"admin"的LCS长度。那么可以根据a[i]和b[j]的情况分为两种决策。

若a[i]==b[j]，则字符串a和字符串b的LCS增加了一位，即有dp[i][j]=dp[i-1][j-1]+1
如果a[i]!=b[j]，那么字符串a的i号位和字符串b的j号位之前的LCS无法延长，因此dp[i][j]将会继承dp[i-1][j]与dp[i][j-1]中的较大值，即有dp[i][j]=max{dp[i-1][j],dp[i][j-1]} （因为不相同，所以从这一位开始往前倒一位是不影响长度的，但是从哪一个维度倒一位就要分类，也就是取一个max）

由此得到状态转移方程 $$ \mathrm{dp[i][j]}= \begin{cases} \mathrm{dp[i-1][j-1]+1,a[i]==b[j]} \ max(\mathrm{dp[i-1][j],dp[i][j-1]}), \mathrm{a[i]!=b[j]} \end{cases} \ 边界：\mathrm{dp[i][0]=dp[j][0]=0} \ \mathrm{i和j从1遍历到各自字符串的长度} $$

11.5 最长回文子串

给出一个字符串s，求s的最长回文子串的长度。

例：

"PATZJUJZTACCBCC"的最长回文子串为"ATZJUJZTA"，长度为9

动态规划法，时间复杂度$\mathrm{O(n^2)}$

令bool dp[i][j]表示s[i]至s[j]所表示的子串是回文子串，这样根据s[i]是否等于s[j]可以把答案分成两类：

若s[i]==s[j]，则只要s[i+1]至s[j-1]是回文子串，s[i]至s[j]就是回文子串；反之。
如果s[i]!=s[j]，那么s[i]至s[j]就一定不是回文子串。

由此可以写出状态转移方程 $$ \mathrm{dp[i][j]=} \begin{cases} \mathrm{dp[i+1][j-1] ,s[i]==s[j]} \ \mathrm{false, s[i]!=s[j]} \end{cases} \ \mathrm{边界dp[i][i]=1， dp[i][i+1]=(s[i]==s[i+1]?true:false)} $$ 但是直接双重循环会无法保证计算过dp[i+1][j-1]，从而无法计算出dp[i+1][j-1]，解决方法如下：

根据递归写法从边界出发的原理：考虑按子串的长度和子串的初始位置进行枚举，即先枚举子串长度L，再枚举左端点i，这样右端点i+L-1也可以直接得到。

11.6 DAG最长路

11.7 背包问题

11.7.1 多阶段动态规划问题

这一类问题的特征是：可以描述成若干个有序的阶段，且每个阶段的状态只和上一个阶段的状态有关。只需从第一个问题开始按照阶段的顺序解决每个阶段中状态的计算，就可以得到最后一个阶段中状态的解。

11.7.2 01背包问题

有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包使得背包内物品的总价值最大。每件物品都只有一件。

dfs的方法时间复杂度为$O(2^n)$，显然不行，使用动态规划则为$O(nV)$

令dp[i][v]表示前i件物品(1≤i≤n,0≤v≤V)恰好（“恰好”指的是恰好把容量v填满）装入容量为v的背包所能获得的最大价值

考虑第i件物品的选择策略，有如下两种：

不放第i件物品，那么问题转化为dp[i-1][v]
放第i件物品，那么问题转化为前i-1件物品恰好装入容量为v-w[i]的背包所能获得的最大价值，也即dp[i-1][v-w[i]]+c[i]

则有 $$ \mathrm{dp[i][v]}=max{\mathrm{dp[i-1][v],dp[i-1][v-w[i]]+c[i]}} \ 1≤i≤n,w[i]≤v≤V $$ 上面就是状态转移方程。又注意到dp[i][v]只与之前的状态dp[i-1][]有关，所以可以枚举i从1到n，v从0到V，通过边界dp[0][v]=0*(0件物品价值当然是0)*就可以把整个dp数组递推出来，而由于dp[i][v]表示的是恰好为v的情况，所以需要枚举dp[n][v]，取其最大值即可。

代码如下

int ans=0;
for(int i=0;i<n;i++){
    for(int v=w[i];v<=V;v++){
        dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);

    }
}
for(int v=1;v<=V;v++){
    ans=max(ans,dp[n][v]);
}
cout<<ans;

时间复杂度和空间复杂度均为$O(nV)$，但是空间复杂度还可以继续优化

注意到每次计算dp[i][v]的时候只需要计算dp[i-1][v]左侧部分的数据（即从0到v的部分的数据），且计算dp[i+1][]的时候，dp[i-1][]部分的数据又没用了。所以开一个一维数组dp[v]，枚举方向i从1到n，v从V到0（逆序！），状态转移方程变为 $$ \mathrm{dp[v]}=max{\mathrm{dp[v],dp[v-w[i]]+c[i]}} \ 1≤i≤n,w[i]≤v≤V $$ 相当于每次计算出dp[i][v]的时候，就覆盖掉dp[i-1][v]，以节省空间

for(int i=0;i<n;i++){
    for(int v=V;v>=w[i];v--){
        dp[v]=max(dp[v],dp[v-w[i]+c[i]]);
    }
}
cout<<dp[V];

记得用一维数组存放时，v的枚举必须是逆序！

对于能够划分阶段的问题来说，都可以尝试把阶段作为状态的一维，这样使得我们更方便地得到满足无后效性的状态。如果当前设计的状态不满足无后效性，不妨把状态进行升维，增加一维或者若干维来表示相应的信息。

11.7.3 完全背包问题

有n种物品，每件物品的重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包使得背包内物品的总价值最大。每件物品都有无穷件。

同样令dp[i][v]表示前i件物品(1≤i≤n,0≤v≤V)恰好（“恰好”指的是恰好把容量v填满）装入容量为v的背包所能获得的最大价值

对于第i件物品来说

不放第i件物品则有dp[i][v]=dp[i-1][v]
放第i件物品转移到dp[i][v-w[i]]+c[i]这个状态，这是因为每件物品可以放任意件，放了第i件物品之后还可以放第i件物品

状态转移方程为 $$ \mathrm{dp[i][v]}=max{\mathrm{dp[i-1][v],dp[i][v-w[i]]+c[i]}} \ 1≤i≤n,w[i]≤v≤V \ 边界\ d[0][v]=0 $$ 也可以改写成一维模式 $$ \mathrm{dp[v]}=max{\mathrm{dp[v],dp[v-w[i]]+c[i]}} \ 1≤i≤n,w[i]≤v≤V \ 边界\ d[v]=0 $$ 这就和01背包问题完全一致了，唯一的区别在于这里的v必须是正向枚举

因为dp[i][v]可以直接覆盖dp[i-1][v]

11.8 总结

总结过的模型列举如下：

最大连续子序列和

令dp[i]表示以a[i]作为结尾的连续序列的最大和。
最长不下降子序列(LIS)

令dp[i]表示以a[i]结尾的最长不下降子序列长度
最长公共子序列(LCS)

令dp[i][j]表示字符串a的i号位和字符串b的j号位之前的LCS长度
最长回文子串

令bool dp[i][j]表示s[i]至s[j]所表示的子串是否是回文子串
数塔DP

令dp[i][j]表示从第i行第j个数字出发的到达最底层的所有路径上所能得到的最大和
DAG最长路

令dp[i]表示从i号顶点出发能获得的最长路径长度
01背包

令dp[i][v]表示前i件物品恰好装入容量为v的背包所能获得的最大价值
完全背包

令dp[i][v]表示前i件物品恰好装入容量为v的背包所能获得的最大价值

特别说明：一般来说“子序列”可以不连续，“子串”必须连续。

当题目与序列或字符串(记作a)有关时，可以考虑把状态设计成下面两种形式，然后根据端点特点去考虑状态转移方程。

令dp[i]表示以a[i]结尾（或开头）的xxx
令dp[i][j]表示a[i]至a[j]区间的xxx

其中xxx均为原问题的表述。

当题目中的问题设计几个维度时候，分析题目中的状态需要几维来表示，然后对其中的每一维采取下面的某一个表述：

恰好为i
前i

在每一维的的含义设置完毕之后，dp数组的含义就可以设置成"令dp数组表示恰好为i（或前i）、恰好为j（或前j）......的XXX"，其中xxx为原问题的表述，接下来通过端点的特点去考虑状态转移方程。

算法 > 笔记

#C++ #算法

德语学习经验分享会上一篇

测试文章下一篇

《算法笔记》学习笔记

第2章 C/C++快速入门

2.1 基本数据类型

2.1.2 变量类型

long long类型赋大于$2^{31}-1$的初值，需要在初值后面加LL，否则会CE

char：小写字母比大写字母的ASCII值大32

转义字符

字符串常量：由双引号标记的字符集，可以作为初值赋值给字符数组并使用%s的形式输出

布尔型

2.1.3 强制类型转换

2.1.4 符号常量和const常量

2.1.5 运算符

2.2 顺序结构

常见数据类型变量的scanf格式符

常见数据类型变量的printf格式符

三种实用的输出格式

2.2.3 使用getchar和putchar来输入/输出字符

2.2.4注释

2.2.5 typedef

2.2.6 常用math函数

2.3 选择结构

2.3.1 if语句

2.3.3 switch语句

2.4 循环结构

2.4.1 while语句

2.4.2 do...while语句

2.4.3 for语句

语法解析

与传统 for 循环的对比

传统 for 循环

范围-based for 循环

示例：遍历 std::set

注意事项

2.4.4 break和continue语句

2.5 数组

2.5.1 一维数组

2.5.2 冒泡排序

2.5.3 二维数组

2.5.4 memset——对数组中每一个元素赋相同的值

2.5.5 字符数组

字符数组的初始化

字符数组的输入输出

字符数组的存放方式

2.5.6 string.h头文件

1. 字典序比较规则

2. 示例说明

示例 1

示例 2

示例 3

3. C++ 中的字符串比较

输出

4. 字典序的应用

5. 注意事项

6. 总结

2.5.7 sscanf与sprintf

2.6 函数

2.6.1 函数的定义

2.6.2 再谈main函数

2.6.3 以数组作为函数参数

2.6.4 函数的嵌套调用

2.6.5 函数的递归调用

2.7 指针

2.7.2 指针变量

2.7.3 指针与数组

2.7.4 使用指针变量作为函数参数

2.7.5 引用

引用的含义

指针的引用

2.8 结构体的使用

2.8.1 结构体的定义

2.8.2 访问结构体内的元素

2.8.3 结构体的初始化

2.9 补充

2.9.1 cin和cout

语法

示例

解释

注意事项

总结

2.9.2 浮点数的比较

示例：遍历 `std::set`

第4章入门篇（2）——算法初步

第5章入门篇（3）——数学问题