算法笔记之蓝桥杯pat系统备考（2）

算法笔记之蓝桥杯&pat系统备考（1）

五、数学问题

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

5.2.1最大公约数

• 约数，又称因数：整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。
• 正整数a与b的最大公约数：a和b的所有公约数中最大的那个公约数

#include<stdio.h>
int gcd(int a, int b){//求解最大公约数常用辗转相除法 if(b == 0) return a;return gcd(b, a % b);
}
int main(){int m, n;scanf("%d%d", &m, &n);printf("%d", gcd(m, n));return 0;
}

5.2.2最小公倍数

• 正整数a和b的最小公倍数：a和b的所有公倍数中最小的那个公倍数

a和b的最小公倍数=ab/gcd(a, b)=a/(gcd(a,b))*b
即最小公倍数的计算在最大公约数的基础上进行。最小公倍数等于a和b的乘积除以a和b的最大公约数。其中ab在实际计算时可能会溢出，则进一步优化：先让其中之一除以最大公约数，再乘另一个数。

5.3分数的四则运算

分数的四则运算：给定两个分数的分子和分母，求它们加减乘除的结果。

5.3.1分数的表示与化简

假分数形式最简洁，用结构体来存储这种只有分子和分母的分数

• 表示规范：
  • 分母down为非负数。若分数为负，则另分子up为负即可
  • 若分数为0，则分子up为0，分母down为1
  • 分子和分母没有除了1之外的公约数

struct Fraction{//分数int up, down;//分别表示分子、分母
}

为了满足上述的三个规范，可能需要化简来实现

• 分数化简
  • 若分母down为负数，则另分子up和分母down都变为相反数（符号位在分子）
  • 若分子up为0，则林分母down为1
  • 约分：求出分子绝对值和分母绝对值的最大公约数d，再另分子分母同时除以最大公约数d

Fraction reduction(Fraction result){//化简分数 if(result.down < 0){//符号位在分子 result.down *= -1;result.up *= -1;}if(result.up == 0){//0约定为分子为0，分母为1 result.down = 1;} else{//分子不为0，进行约分 int d = gcd(abs(result.down), abs(result.up));result.down /= d;result.up /= d;} return result;
}

5.3.2分数的四则运算

Fraction add(Fraction a, Fraction b){//分数相加 Fraction c;c.down = a.down * b.down;c.up = a.up*b.down + b.up*a.down;return reduction(c);
} Fraction minu(Fraction a, Fraction b){//分数相加 Fraction c;c.down = a.down * b.down;c.up = a.up*b.down - b.up*a.down;return reduction(c);
} Fraction multi(Fraction a, Fraction b){//分数相乘 Fraction c;c.down = a.down * b.down;c.up = a.up * b.up;return reduction(c); 
}//除法中注意，先判断除数是否为0：
//①除数为0，按照题目要求输出（例如error、inf等）
//②除数非0时，再进入下述函数
Fraction divide(Fraction a, Fraction b){//分数相除 Fraction c;c.down = a.down * b.up;c.up = a.up * b.down;return reduction(c);
}

5.3.3分数的输出

• 注意：
  • 输出分数前，先对其进行化简
  • 若分数的分母为1，说明该分数为整数，一般来说题目会要求直接输出分子
  • 若分数r的分子up大于分母down，则为假分数。需要按带分数的形式输出，即整数部分为r.up / r.down,分子部分为abs(r.up) % r.down
  • 以上均不满足时，则为真分数，按原样输出即可

void showResult(Fraction f){//输出分数f f = reduction(f);if(f.down == 1) printf("%lld", f.up);//若为整数，则直接输出分子else if(f.down < abs(f.up) printf("%d %d/%d", f.up/f.down, abs(f.up) % f.down, f.down);//若为假分数，则按带分数形式输出 else printf("%d/%d", f.up, f.down);//若为真分数，则直接原样输出 
}

简单应用

#include<stdio.h>
#include<math.h>
struct Fraction{//分数表示 int down, up;
};int gcd(int a, int b){//求最大公约数 if(b == 0) return a;else return gcd(b, a%b);
}Fraction reduction(Fraction f){//分数化简 if(f.down < 0){//若分母为负，则把负号调到分子上 f.down *= -1;f.up *= -1;}if(f.up == 0) f.down = 1;//0约定表示为分子为0，分母为1else{int d = gcd(abs(f.up), abs(f.down));f.up /= d;f.down /= d;} return f;
}Fraction add(Fraction a, Fraction b){//分数相加 Fraction c;c.down = a.down * b.down;c.up = a.up*b.down + b.up*a.down;return reduction(c);
} Fraction minu(Fraction a, Fraction b){//分数相加 Fraction c;c.down = a.down * b.down;c.up = a.up*b.down - b.up*a.down;return reduction(c);
} Fraction multi(Fraction a, Fraction b){//分数相乘 Fraction c;c.down = a.down * b.down;c.up = a.up * b.up;return reduction(c); 
}Fraction divide(Fraction a, Fraction b){//分数相除 Fraction c;c.down = a.down * b.up;c.up = a.up * b.down;return reduction(c);
}void showResult(Fraction f){//输出分数f f = reduction(f);if(f.down == 1) printf("%lld", f.up);//若为整数，则直接输出分子else if(f.down < abs(f.up)) printf("%d %d/%d", f.up/f.down, abs(f.up) % f.down, f.down);//若为假分数，则按带分数形式输出 else printf("%d/%d", f.up, f.down);//若为真分数，则直接原样输出 
}int main(){Fraction f1, f2;scanf("%d%d%d%d", &f1.up, &f1.down, &f2.up, &f2.down);showResult(f1);printf("\nf2 : ");showResult(f2);printf("\nf1 + f2 : ");showResult(add(f1, f2));printf("\nf1 - f2 : ");showResult(minu(f1, f2));printf("\nf1 * f2 : ");showResult(multi(f1, f2));printf("\nf1 / f2 : ");showResult(divide(f1, f2));return 0;
} 

5.4素数（质数）

• 素数（质数）：除了1和本身外，不能被其他数整除的数。换言之，对给定的正整数n，若对任意的正整数 a（1<a<n），都有n%a != 0成立，则a时素数
• 合数：除了1和本身外，还存在至少一个能被整除的数。例如4，还能被2整除，则为合数
• 1既不是素数，也不是合数

5.4.1素数的判断

5.4.2素数表的获取

素数筛法，时间复杂度O(nloglogn)

#include<iostream>
#include<vector>
using namespace std;
const int maxN = 101;
int main(){vector<int> primes(maxN, 1), p; for(int i = 2; i < maxN; i++){//打印100以内的素数表 if(primes[i]){p.push_back(i);for(int j = i * i; j < maxN; j += i){primes[j] = 0;}}}for(int i = 0; i < p.size(); i++){printf("%d ", p[i]);}return 0;
}

5.5质因子分解

• 质因子分解：把一个正整数写为若干个质数相乘的形式
• 10⁹ 内整数本质不同质因数不会超过十个

23571113171923*29超过了int范围

• 对于一个正整数n而言，若它存在1和本身之外的因子，则一定是在sqrt(n)左右成对出现。
  对于一个正整数n来说，若它存在[2, n]范围内的质因子，要么这些质因子全部小于等于sqrt(n)，要么只存在一个大于sqrt(n)的质因子，而其余质因子全部小于等于sqrt(n)。
  简单应用：

#include<iostream>
#include<map>
typedef long long LL;
using namespace std;
int main(){map<LL, int> mp;LL n, t;int i = 1;scanf("%lld", &n);t = n;for(int i = 2; i * i <= t; i++){if(t % i == 0){while(t % i == 0){mp[i]++;t /= i;}}}if(t > 1) mp[t]++;printf("%lld=", n);if(mp.size() != 0){for(map<LL, int>::iterator it = mp.begin(); it != mp.end(); it++, i++){if(it -> second == 1) printf("%lld", it -> first);else printf("%lld^%lld", it -> first, it -> second);if(i != mp.size()) printf("*");}}else printf("%lld", n);return 0;
} 

5.6大整数运算

5.6.1大整数的存储

借助数组存储，一般逆序存储，即数组中的每一位对应整数中的每一位，其中整数的低位存储在数组的低位
为了方便获取大整数的长度，一般会定义一个int型变量记录长度和d数组组合为结构体

struct bign{int d[1000];int len;bign(){//构造函数进行初始化结构体；每次定义结构体变量时，都会自动对该变量进行初始化memset(d, 0, sizeof(d));len = 0;}
}

输入大整数时，一般都是先用字符串读入，再把字符串另存到bign结构体

bign change(char str[]){//输入大整数bign b;b.len = strlen(str);int l = strlen(str);for(int i = 0; i < l; i++){b.d[i] = str[l - i - 1] - '0';//逆序存储}return b;
} 

比较两个大整数的大小：
首先位数多的大
位数相同时，从高位至低位进行比较，同位数 数值大的更大
全部位数相同，则相等

int compare(bign b1, bign b2){//大整数变量比较大小if(b1.len < b2.len) return -1;//b1小else if(b1.len > b2.len) return 1;//b2小else{for(int i = b1.len - 1; i >= 0; i--){if(b1.d[i] < b2.d[i]) return -1;else if(b1.d[i] > b2.d[i]) return 1;}		} return 0;//相等 
}

5.6.2大整数的四则运算

高精度加法

bign add(bign b1, bign b2){bign b;int carry = 0, i;//进位 for(i = 0; i < b1.len || i < b2.len; i++){b.d[i] = (b1.d[i] + b2.d[i]) % 10 + carry;carry = (b1.d[i] + b2.d[i]) / 10;}if(carry == 1) {b.d[i] = 1;b.len = i + 1;}else b.len = i;return b; 
}

高精度减法

使用sub函数前，需要先比较b1和b2的大小，确保b1 >= b2.换言之，当b1 < b2时，则输出负号，再交换b1,b2

bign sub(bign b1, bign b2){bign b;for(int i = 0; i < b1.len; i++){//确保b1 >= b2，以较长的为界限if(b1.d[i] < b2.d[i]){//不足则借位 b1.d[i] += 10;b1.d[i + 1]--; } b.d[b.len++] = b1.d[i] - b2.d[i];}while(b.len > 1 && b.d[i - 1] == 0){//去掉高位多余的0（有至少两位的时候才需要考虑该问题 ）；数组从0开始 b.len --;}return b; 
}

高精度与低精度的乘法

如果两个乘数异号，则先记录负号，再用其绝对值带入函数

bign multi(bign b, int n){//高精度和低精度的乘法 bign ans;int carry = 0, t;//进位 for(int i = 0; i < b.len; i++){t = b.d[i] * n + carry;ans.d[ans.len++] = t % 10;carry = t / 10;} while(carry){//乘法进位可能不止一位 ans.d[ans.len++] = carry % 10;carry /= 10; }return ans;
}

高精度与低精度的除法

bign divide(bign b, int n, int &r){//高精度和低精度的除法，r为余数（初始为0） bign ans;ans.len = b.len;for(int i = b.len - 1; i >= 0; i--){//从高位开始 r = r*10 + b.d[i];//当前位数值+上一位的余数*10 if(r < n){//不够除，商0（注意够不够除，比较的是除数n） ans.d[i] = 0;}else{//够除 ans.d[i] = r / n;//商（注意比较的是除数n） r = r % n;//新的余数 } }while(ans.len > 1 && ans.d[ans.len - 1] == 0){//当位数至少为2位时，考虑高位是否有多余的0 ans.len--;}	return ans; 
}

简单应用

#include<stdio.h>
#include<string.h>struct bign{int d[1000];int len;bign(){memset(d, 0, sizeof(d));len = 0;}
};bign change(char str[]){//输入 bign b;b.len = strlen(str);int l = strlen(str);for(int i = 0; i < l; i++){b.d[i] = str[l - i - 1] - '0';}return b;
} int compare(bign b1, bign b2){//比较 if(b1.len < b2.len) return -1;//b1小else if(b1.len > b2.len) return 1;//b2小else{for(int i = b1.len - 1; i >= 0; i--){if(b1.d[i] < b2.d[i]) return -1;else if(b1.d[i] > b2.d[i]) return 1;}		} return 0;//相等 
}bign add(bign b1, bign b2){//相加 bign b;int carry = 0, i;//进位 for(i = 0; i < b1.len || i < b2.len; i++){b.d[i] = (b1.d[i] + b2.d[i]) % 10 + carry;carry = (b1.d[i] + b2.d[i]) / 10;}if(carry == 1) {b.d[i] = 1;b.len = i + 1;}else b.len = i;return b; 
}bign sub(bign b1, bign b2){//b1 >= b2bign b;for(int i = 0; i < b1.len; i++){//以较长的为界限 if(b1.d[i] < b2.d[i]){//不够减 b1.d[i] += 10;b1.d[i+1]--;}b.d[b.len++] = b1.d[i] - b2.d[i];}while(b.len > 1 && b.d[b.len-1] == 0) b.len--; return b;
}bign multi(bign b, int n){//高精度和低精度的乘法 bign ans;int carry = 0, t;//进位 for(int i = 0; i < b.len; i++){t = b.d[i] * n + carry;ans.d[ans.len++] = t % 10;carry = t / 10;} while(carry){//乘法进位可能不止一位 ans.d[ans.len++] = carry % 10;carry /= 10; }return ans;
}bign divide(bign b, int n, int &r){//高精度和低精度的除法，r为余数（初始为0） bign ans;ans.len = b.len;for(int i = b.len - 1; i >= 0; i--){//从高位开始 r = r*10 + b.d[i];//当前位数值+上一位的余数*10 if(r < n){//不够除，商0（注意够不够除，比较的是除数n） ans.d[i] = 0;}else{//够除 ans.d[i] = r / n;//商（注意比较的是除数n） r = r % n;//新的余数 } }while(ans.len > 1 && ans.d[ans.len - 1] == 0){//当位数至少为2位时，考虑高位是否有多余的0 ans.len--;}	return ans; 
}int main(){char str1[1000], str2[1000];int n, r = 0;scanf("%s%s%d", str1, str2, &n);bign b1 = change(str1);bign b2 = change(str2);bign b = add(b1, b2);for(int i = b.len - 1; i >= 0; i--){printf("%d", b.d[i]);}printf("\n");bign subN;if(compare(b1, b2) < 0){printf("-");subN = sub(b2, b1);}else subN = sub(b1, b2);for(int i = subN.len - 1; i >= 0; i--){printf("%d", subN.d[i]);}printf("\n");bign m = multi(b1, n);for(int i = m.len - 1; i >= 0; i--){printf("%d", m.d[i]);}printf("\n");bign d = divide(b1, n, r);for(int i = d.len - 1; i >= 0; i--){printf("%d", d.d[i]);}return 0;
}

六、c++标准模板库（STL）

Standard Template Library STL标准模板库

6.1vector变长数组

使用vector需要添加：

#include<vector>
using namespace std;

vector定义

其中typename可以说任意基本类型，也可以是STL标准容器，例如vector、set、queue等。注意，当typename也是STL容器时，定义时要在>>符号之间加上空格。

因为一些使用C++11之前标准的编译器会把它视为移位操作，导致编译错误。

vector<typename> name;

vector<double> name;
vector<node> name;//node是结构体的类型//二维vector数组，可以理解为两个维都可变长的二维数组
vector<vector<int> > name;//>>之间记得加空格

vector数组的定义
其中Arrayname[0]~Arrayname[arraySize - 1]中每一个都是一个vector容器
。与vector<vector < typename> > name区别在于，该种写法的一维长度已经固定为arraySize，另一维才是变长的。

vector<typename> Arrayname[arraySize];

vector<int> vi[100];

以上定义的为空vector
vector定义并初始化：

1. 定义并用n个val来初始化的vector

vector<typename> name(n, val);

vector<int> vi(10, 1);//用10个1来初始化vector

2. 定义并用迭代器区间来初始化的vector

vector<int> vi1(vi.begin(), vi.end());//用vi的迭代器区间来初始化vi1
string s("you are so pretty");
vector<char> v(s.begin(), s.end());//用s的迭代器区间来初始化v

3. 除了上述两种，还有三种

	//一共有这五种初始化方式(1) vector<int> a(10); //定义了10个整型元素的向量（尖括号中为元素类型名，它可以是任何合法的数据类型），但没有给出初值，其值是不确定的。（2）vector<int> a(10,1); //定义了10个整型元素的向量,且给出每个元素的初值为1（3）vector<int> a(b); //用b向量来创建a向量，整体复制性赋值（4）vector<int> a(b.begin(),b.begin+3); //定义了a值为b中第0个到第2个（共3个）元素（5）int b[7]={1,2,3,4,5,9,8};vector<int> a(b,b+7); //从数组中获得初值

vector容器内元素的访问

1.通过下标访问

类似于普通数组，对于一个定义为vector< typename> vi的vector容器而言，直接访问vi[index]即可，其中下标index范围为[0, vi.size()-1]
注意，下面这种做法以及类似的做法都是错误的。下标只能用于获取已存在的元素，而现在的vi[i]还是空的对象

2.通过迭代器访问

所谓迭代器iterator可理解为类似指针的东东
其中，it是一个vector< typename>::iterator型的变量

vector<typename>::iterator it;

• vi.begin()函数：取vector容器vi的首元素地址
• vi.end()函数：取vector容器vi的尾元素地址的下一个地址

老外习惯：左闭右开

#include<stdio.h>
#include<vector>
using namespace std;
int main(){vector<int> vi;for(int i = 1; i < 6; i++)vi.push_back(i);vector<int>::iterator it = vi.begin();for(int i = 0; i < vi.size(); i++)printf("%d ", *(it + i));printf("\n");for(int i = 0; i < vi.size(); i++)printf("%d ", *(vi.begin() + i));printf("\n");//vector的迭代器不支持it < vi.end()写法，则循环条件只能用it != vi.end()//在常用STL容器中，只有vector和string中，才允许使用vi.begin()+n这种迭代器加上整数的写法 for(vector<int>::iterator i = vi.begin(); i != vi.end(); i++){//迭代器实现了自加自减操作(it++或++it) printf("%d ", *i);// }printf("\n");for(int i = 0; i < vi.size(); i++)printf("%d ", vi[i]);//通过下标访问 return 0;
}

vector常用函数

• push_back(x) : 在vector后面添加一个元素x，时间复杂度为O(1)
  • emplace_back(x)c++11新加，可以理解为实现更优雅的push_back()
• pop_back() : 删除vector的尾元素，时间复杂度为O(1)

#include<stdio.h>
#include<vector>
using namespace std;
int main(){vector<int> vi;for(int i = 1; i < 6; i++)vi.push_back(i);//在vector后面插入元素ifor(int i = 0; i < vi.size(); i++)printf("%d ", vi[i]);vi.pop_back();//删除vector尾元素printf("\n");for(int i = 0; i < vi.size(); i++)printf("%d ", vi[i]);	 return 0;
}

• size() : 获得vector中元素的个数，时间复杂度为O(1)。size()返回的是unsigned类型，不过用%d一般木得问题，该点适用于所有STL容器。
• clear() ： 清空vector中的所有元素，时间复杂度为O(N),其中N为vector中元素的个数
• insert(it, x) : 向vector中的任意迭代器it处插入一个元素x，时间复杂度为O(1)
• erase
  • erase(it)删除迭代器为it处的元素
  • erase(first, last)删除[first, last)内的所有元素

#include<stdio.h>
#include<vector>
using namespace std;
int main(){vector<int> vi;for(int i = 1; i < 6; i++)vi.push_back(i);printf("vi长度：%d", vi.size());vi.insert(vi.begin() + 3, 0);//把元素0插入到vi[3]的位置    printf("\n");for(int i = 0; i < vi.size(); i++)printf("%d ", vi[i]);	 vi.erase(vi.begin() + 1);//删除vi[1]处的元素printf("\n");for(int i = 0; i < vi.size(); i++)printf("%d ", vi[i]);vi.erase(vi.begin(), vi.begin() + 2);//删除vi[0]到vi[1]的所有元素 printf("\n");for(int i = 0; i < vi.size(); i++)printf("%d ", vi[i]);vi.clear();//清除所有元素 printf("\n%d", vi.size()); //0 return 0;
}

vector常见用途

1. 作为数组使用，尤其是元素个数不确定的场合；当需要输出部分数据且中间用空格隔开而末尾不能有多余空格时，可以先用vector记录所有需要输出的数据，再一次性输出
2. 用邻接表存储图

6.2set（升序、去重）

若使用set，需要添加：

#include<set>
using namespace std;

整体和vector容器非常相似，下述简化描述

set定义

set<typename> name;

set<int> name;
set<node> name;

set数组定义

set<typename> Arrayname[arraySize];

set<int> a[100];

set容器内元素的访问

set只能通过迭代器(iterator)访问元素

set<typename>::iterator it;

#include<stdio.h>
#include<set>
using namespace std;
int main(){set<int> st;st.insert(5);st.insert(3);st.insert(4);st.insert(3);st.insert(1);//除了vector和string之外的STL容器都不支持*(it + i)的访问方式，则只能按照如下方式枚举 for(set<int>::iterator it = st.begin(); it != st.end(); it++){//同vector，不支持it < st.end()的写法 printf("%d ", *it);}return 0;
} 

set常用函数

• insert(x) : 把x插入set容器中，且自动增序和去重，时间复杂度O(logN)，其中N是set内的元素个数
• find(value) : 返回set中对应值为value的迭代器，时间复杂度为O(logN)，N为set内的元素个数
• erase()
  • erase(it) ： it是所需要删除元素的迭代器，时间复杂度为O(1)。可以结合find()函数来使用
  • erase(value) : value是所需要删除的元素的值，时间复杂度为O(logN)，N为set内的元素个数
  • erase(first, last)删除区间[ first, last)内的所有元素，时间复杂度为O(last - first)
• size() : 获得set内的元素个数，时间复杂度为O(1)
• clear() : 清空set中的所有元素，时间复杂度为O(N)，其中N为set内元素的个数

#include<stdio.h>
#include<set>
using namespace std;
int main(){set<int> st;st.insert(5);//set(x)把元素x插入到set容器中，且自动实现增序和去重 st.insert(3);st.insert(4);st.insert(3);st.insert(1);for(set<int>::iterator it = st.begin(); it != st.end(); it++){printf("%d ", *it);}set<int>::iterator it = st.find(3);//find(value) 返回set中对应值为value的迭代器 printf("\n%d\n", *it); //3//erase(it) 其中it是要删除元素的迭代器 st.erase(it);//先利用find()函数找到3，再用erase()删除for(set<int>::iterator it = st.begin(); it != st.end(); it++){printf("%d ", *it);}//erase(value) 其中value是要删除元素的值 st.erase(4);//删除set中值为4的元素 printf("\n");for(set<int>::iterator it = st.begin(); it != st.end(); it++){printf("%d ", *it);}//erase(first, last)删除区间[ first, last)内的所有元素 st.erase(st.find(5), st.end());//删除元素5到set末尾之间的所有元素 printf("\n");for(set<int>::iterator it = st.begin(); it != st.end(); it++){printf("%d ", *it);}//size() 返回set内的元素个数 printf("\nset长度：%d", st.size());//clear() 清空set中的所有元素st.clear();printf("\n清空后的set长度：%d", st.size());return 0;
} 

set常见用途

set最主要的作用就是自动去重且按升序排序

6.3string字符串

使用string,需要添加：

#include<string>
using namespace std;

string定义

定义string的方式跟基本数据类型相同，直接在string后跟变量名即可

string str;

若初始化，可以直接给string类型的变量进行赋值

string str = "harder";

string中内容的访问

1. 通过下标访问
   一般而言，可以直接像字符数组那样去访问string

#include<stdio.h>
#include<string>
using namespace std;
int main(){string str = "fighting!";for(int i = 0; i < str.length(); i++){printf("%c ", str[i]);}return 0;
} 

读入和输出整个字符串

#include<iostream>
#include<string>
using namespace std;
int main(){string str;cin>>str;cout<<str;printf("\n%s", str.c_str());return 0;
} 

2. 通过迭代器访问
   一般情况下用下标进行访问即可，但有些函数比如insert()和erase()要求以迭代器为参数，需要了解string迭代器的用法

string::iterator it;

#include<stdio.h>
#include<string>
using namespace std;
int main(){string str = "fighting!";for(string::iterator it = str.begin(); it != str.end(); it++){printf("%c ", *it);}printf("\n");for(int i = 0; i < str.length(); i++){//string和vector一样，支持直接对迭代器进行加减某个数字 printf("%c ", *(str.begin() + i));}return 0;
}

string常用函数

• += ：把两个string直接拼接起来

#include<iostream>
#include<string>
using namespace std;
int main(){string str1 = "fighting,", str2 = "blue!";str1 += str2;//fighting,blue!str2 += str2;//blue!blue!cout<<str1<<endl;printf("%s", str2.c_str());return 0;
} 

• 比较操作==、!=、<、<=、>、>= : 比较规则是字典序

#include<iostream>
#include<string>
using namespace std;
int main(){string str1 = "aa", str2 = "ab", str3 = "aaa", str4 = "yz";if(str1 < str2) printf("%s小于%s\n", str1.c_str(), str2.c_str());if(str1 < str3) printf("%s小于%s\n", str1.c_str(), str3.c_str());if(str1 < str4) printf("%s小于%s\n", str1.c_str(), str4.c_str());return 0;
}

• length()/size() ： 返回string的长度
• insert()
  • insert(pos, string) 在pos号位置上插入字符串string（pos从0开始

#include<iostream>
#include<string>
using namespace std;
int main(){string str = "123456";str.insert(3, "abc");cout<<str;return 0;
}

• insert()续
  • insert(it, it1, it2) ： 串[ it1, it2)将会插在it的位置上

#include<iostream>
#include<string>
using namespace std;
int main(){string str = "123456", str1 = "abcdef";str.insert(str.begin() + 3, str1.begin(), str1.begin() + 3);cout<<str;return 0;
}

• erase()
  • erase(it) : 用于删除单个元素，其中it是需要删除的元素的迭代器
  • erase(first, last) : 删除区间[first, last)内的所有元素
  • erase(pos, length) : 删除从pos开始,length个字符

#include<iostream>
#include<string>
using namespace std;
int main(){string str = "123456", str1 = "abcdef";//erase(it) 删除单个元素 str.erase(str.begin() + 1);	//13456	即删除1号位置的元素（位置从0开始） cout<<str<<endl;//erase(first, last) 删除区间[first, last)内的所有元素 str.erase(str.end() - 3, str.end());//13 cout<<str<<endl;//erase(pos, length) 删除从pos开始的length个字符 str1.erase(3, 3);//abc 即删除从3号位开始的3个字符 cout<<str1;return 0;
}

• clear() ： 清空string中的数据
• substr(pos, len) : 返回从pos位置开始，长度为len的子串，时间复杂度为O(len)

#include<iostream>
#include<string>
using namespace std;
int main(){string str1 = "abcdef123", str2;str2 = str1.substr(6, 3);cout<<str2<<endl;//123str1.clear();cout<<str1.size();//0return 0;
}

• string::npos 是一个常数，本身的值是-1，但由于是unsigned_int类型，则也可以认为是unsigned_int类型的最大值。string::pos是find()函数失配时的返回值。

#include<iostream>
#include<string>
using namespace std;
int main(){
//	unsigned int n = -1;
//	cout<<n<<endl;if(string::npos == -1) cout<<"string::npos == 1为真"<<endl;
//	if(string::npos == n) printf("string::npos == %u为真", n);
//	else cout<<"err";//[Warning] this decimal constant is unsigned only in ISO C90if(string::npos == 4294967295) printf("string::npos == 4294967295为真");return 0;
}

• find()
  • str.find(str1) :
    • 当str1是str的子串时，返回其在str中第一次出现的位置；
    • 当str1不是str的子串时，返回string::npos
  • str.find(str1, pos) ： 从str的pos号位开始匹配str1,返回值和上个函数相同

#include<iostream>
#include<string>
using namespace std;
int main(){string str1 = "fighting, blue!", str2 = "ing", str3 = "give up";if(str1.find(str2) != string::npos) cout << str1.find(str2) << endl;if(str1.find(str3) != string::npos) cout << str1.find(str3) << endl;else printf("no words:%s\n", str3.c_str());if(str1.find(str2, 6) != string::npos) cout << str1.find(str2, 6) << endl;else cout<<"early";return 0;
}

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

#include<iostream>
#include<string>
using namespace std;
int main(){string str = "1234567890", str1 = "abc", str2 = "DEF";cout << str.replace(3, 3, str1) << endl;//123abc7890cout << str.replace(str.begin() + 6, str.begin() + 7, str2);//123abcDEF890 位置不够也会把str2替换 return 0;
}

6.4map键值对

若map使用，需要添加：

#include<map>
using namespace std;

map可以把任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器）

map定义

定义一个map,其中前类型为key类型，后类型为value类型

map<typename1, typename2> mp;

当int型映射到int型，也就相当于普通的int型数组了。
注意当字符串到整型的映射时，必须使用string而不能使用char数组。
因为char数组作为数组，是不能被作为键值的。若想用字符串做映射，必须用string。

map<string, int> mp;

map<set<int>, string>  mp;//map的键和值也可以是STL容器

map中内容的访问

• 通过下标进行访问
  和普通数组的访问同理，例如对一个定义为map<char, int> mp的map来说，就可以直接使用mp[‘c’]的方式来访问它对应的整数。注意，map中的键是唯一的。

#include<iostream>
#include<map>
using namespace std;
int main(){map<char, int> mp;mp['a'] = 1;mp['a'] = 2;//更新,因为键是唯一的 printf("%d", mp['a']);//2return 0;
} 

• 通过迭代器访问
  map可使用it->first来访问键，使用it->second来访问值。map会以键从小到大的顺序自动排序

因为map内部使用红黑树实现（set也是），在建立映射的过程中会自动实现从小到大的排序功能

map<typename1, typename2>::iterator it;

#include<iostream>
#include<map>
using namespace std;
int main(){map<char, int> mp;mp['c'] = 4;mp['a'] = 2;mp['b'] = 5;for(map<char, int>::iterator it = mp.begin(); it != mp.end(); it++){printf("%c : %d\n", it->first, it->second);}return 0;
}

map常见函数

• find(key) : 返回键为key的映射的迭代器

#include<iostream>
#include<map>
using namespace std;
int main(){map<char, int> mp;mp['b'] = 4;mp['a'] = 1;mp['c'] = 3;//find(key)返回键为key的映射的迭代器//小复习：map可以使用it -> first访问键， it -> second访问值 map<char, int>::iterator it = mp.find('a');printf("%c %d", it -> first, it -> second);//a 1 return 0;
}

• erase()
  • erase(it) : it是要删除元素的迭代器，时间复杂度为O(1)
  • erase(key) : key是要删除的映射的键，时间复杂度为O(logN)
  • erase(first, last) : 删除区间[ first, last)内的元素。其中first是要删除区间的起始迭代器，last是要删除的区间的末尾迭代器的下一个地址。

#include<iostream>
#include<map>
using namespace std;
int main(){map<char, int> mp;mp['b'] = 4;mp['a'] = 1;mp['c'] = 3;mp['d'] = 2;mp['y'] = 4;mp['x'] = 1;mp['z'] = 3;mp['o'] = 2;for(map<char, int>::iterator it = mp.begin(); it != mp.end(); it++){printf("%c %d, ", it -> first, it -> second);} printf("\n");map<char, int>::iterator it = mp.find('a');//mp.erase(it) it是要删除元素的迭代器 mp.erase(it);mp.erase(mp.find('d'));//mp.erase(key) key是要删除的映射的键 mp.erase('c');//mp.erase(first, last)删除区间[first, last)区间内的元素 //注意，这里的迭代器不能用mp.begin()或者mp.end()加整数//string和vector才支持对迭代器进行加减某个数字，例如str.begin()+3 mp.erase(mp.find('x'), mp.end());for(map<char, int>::iterator it = mp.begin(); it != mp.end(); it++){printf("%c %d, ", it -> first, it -> second);} printf("\n"); return 0;
}

• size() ： 返回的是map中映射的对数，时间复杂度O(1)
• clear() : 清空map中的所有元素，复杂度为O(n)，其中N为map中元素的个数

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){map<string, int> mp;mp["are"] = 1;mp["you"] = 3;mp["ok"] = 2;for(map<string, int>::iterator it = mp.begin(); it != mp.end(); it++)printf("%s %d\n", it -> first.c_str(), it -> second);//mp.clear() 清空mp中的所有元素 mp.clear();//mp.size() 返回mp中的映射对数 printf("%d", mp.size());return 0;
}

map常见用途

• 需要建立字符（字符串）与整数之间映射的题目，可以使用map减少代码量
• 判断大整数或者其他类型数据是否存在的题目，可以把map当bool数组用
• 字符串和字符串的映射也有可能会遇到

6.8pair

若用pair,需添加

#include<map>
using namespace std;

或

#include<utility>
using namespace std;

由于map的内部实现中设计pair，则添加mao头文件会自动添加utility头文件，故可以直接偷懒用map头文件来代替utility头文件，好记~

pair定义

pair有俩参数，分别对应first和second的数据类型，它们可以是任意基本数据类型或容器

pair<typename1, typename2> name;

pair<string, int> p;

若在定义pair时进行初始化，只需跟上一个小括号，里面填写两个想要初始化的元素即可

pair<string, int> p("harder", 1);

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

• 把类型定义写在前面，后面用小括号内两个元素的方式

pair<string, int>("blue", 2)

• 使用自带的make_pair函数

make_pair("first", 1)

pair中元素的访问

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

#include<iostream>
#include<map>
using namespace std;
int main(){pair<string, int> p;p.first = "fighting";p.second = 1;cout << p.first << " " << p.second << endl;p = pair<string, int>("coming", 1);cout << p.first << " " << p.second << endl;p = make_pair("harder", 111);cout << p.first << " " << p.second;return 0;
}

pair常用函数

两个pair类型数据可以直接使用== , !=, < , <= , >, >=比较大小。

• 比较规则：先以first的大小作为标准，只有当first相等时才去判别second的大小

#include<iostream>
#include<map>
using namespace std;
int main(){pair<int, int> p1(3, 1);pair<int, int> p2(3, 2);pair<int, int> p3(2, 3);if(p1 < p2) cout << p1.first << " " << p1.second << "小于" << p2.first << " " << p2.second << endl;if(p1 > p3) cout << p1.first << " " << p1.second << "大于" << p3.first << " " << p3.second;return 0;
}

pair常见用途

• 用来替代二元结构体及其构造函数，可以节省编码时间
• 作为map键值对来进行插入

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){map<string, int> mp;//mp.insert("that", 4);报错 mp.insert(pair<string, int>("this", 2));mp.insert(make_pair("it", 3));for(map<string, int>::iterator it = mp.begin(); it != mp.end(); it++){cout << it->first << " " << it->second << endl;}return 0;
}

6.9 algorithm头文件下的常用函数

若使用algorithm头文件，需要在头文件下添加

using namespace std;

6.9.1 max(), min()和 abs()

• max(x, y) 返回x和y中的最大值（且参数必须是两个，可以是浮点数）
• min(x, y) 返回x和y中的最小值
• abs(x) 返回x的绝对值

#include<iostream>
#include<algorithm>
using namespace std;
int main(){int x, y, z;cin >> x >> y >> z;cout << max(x, y) << endl;cout << max(x, max(y, z)) << endl;cout << min(x, y) << endl;cout << abs(x) << endl;cout << fabs(x);return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
//	int x, y, z;double x = -1, y = -3, z = -2;
//	cin >> x >> y >> z;cout << max(x, y) << endl;cout << max(x, max(y, z)) << endl;cout << min(x, y) << endl;cout << abs(x) << endl;cout << fabs(x);return 0;
}

• swap(x, y) 交换x和y的值
• reverse(it1, it2) 把[ it1, it2)之间的元素或容器的迭代器在该范围内反转

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){string str = "abcdefg";int a[10] = {1, 2, 3, 4, 5};swap(a[0], a[1]);reverse(a + 2, a + 5);for(int i = 0; i < 5; i++){printf("%d ", a[i]);}reverse(str.begin(), str.begin() + 4);cout << endl << str;return 0;
}

• next_permutation(first, last) : 给出一个序列在[first, last]范围内全排列中的下一个序列
  
  next_permutation在已经到达全排列的最后一个时会返回false。使用do…while语句是为了输出最有一组序列后再退出。

#include<iostream>
#include<algorithm>
using namespace std;
int main(){int a[5] = {3, 2, 1}, b[5] = {1, 2, 3};do{printf("逆序：%d %d %d\n", a[0], a[1], a[2]);}while(next_permutation(a, a + 3));do{printf("正序：%d %d %d\n", b[0], b[1], b[2]);}while(next_permutation(b, b + 3));return 0;
}

• fill(first, last, value) : 把[first, last]区间内皆赋值为value

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){vector<int> vi;for(int i = 1; i < 6; i++)vi.push_back(i);fill(vi.begin(), vi.end(), 6);for(int i = 0; i < 5; i++)cout << vi[i] << " ";return 0;
}

6.9.6sort()

sort()使用

• 需要加#include<algorithm>和using namespace std;

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

若比较函数不填，默认从小到大（序列元素一定要有可比性）（对于char型数组默认为字典序）对于结构体这种本身没有大小关系，需要手动制定比较规则。
①整型数组

#include<cstdio>
#include<algorithm>
using namespace std;
int main(){int a[6] = {9, 4, 2, 5, 6, -1};sort(a, a + 4);//默认从小到大 for(int i = 0; i < 6; i++){printf("%d ", a[i]);//2 4 5 9 6 -1} printf("\n");sort(a, a + 6);for(int i = 0; i < 6; i++){printf("%d ", a[i]);//-1 2 4 5 6 9}return 0;
}

②char型数组

#include<cstdio>
#include<algorithm>
using namespace std;
int main(){char c[] = "harder";sort(c, c + 6);for(int i = 0; i < 6; i++) printf("%c ", c[i]);return 0;
}

实现比较函数

（1）基本数据类型数组的排序

从大到小a>b
①整型数组

#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp(int a, int b){return a > b;
}
int main(){int a[6] = {9, 4, 2, 5, 6, -1};sort(a, a + 4, cmp);//默认从小到大 for(int i = 0; i < 6; i++){printf("%d ", a[i]);//9 5 4 2 6 -1} printf("\n");sort(a, a + 6, cmp);for(int i = 0; i < 6; i++){printf("%d ", a[i]);//9 6 5 4 2 -1}return 0;
}

②字符型数组

#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp(char a, char b){return a > b;
}
int main(){char c[] = "harder";sort(c, c + 6, cmp);for(int i = 0; i < 6; i++) printf("%c ", c[i]);//r r h e d areturn 0;
}

（2）结构体数组的排序

以该结构体为例：

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

• 一级排序
  以ssd数组按照x从大到小排序

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

• 二级排序
  以ssd数组先按x从大到小排序；当x相等时，按照y从小到大排序

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

（3）容器的排序

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

对于像set,map这种容器是用红黑树实现的，元素本身有序，则不运行使用sort排序

//以vector为例
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(int a, int b){//vector中的元素为int型，则仍然是int的比较 return a > b;
}
int main(){vector<int > vi;vi.push_back(3);vi.push_back(2);vi.push_back(4);sort(vi.begin(), vi.end(), cmp);//对整个vector排序for(int i = 0; i < 3; i++)printf("%d ", vi[i]);//4 3 2 return 0;
}

//以string按字典序从小到大输出为例
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){string str[3] = {"better", "a", "person"};sort(str, str + 3);//把string型数组按照字典序从小到大输出for(int i = 0; i < 3; i++)cout<<str[i]<<endl; //a better personreturn 0;
} 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool cmp(string str1, string str2){return str1.length() < str2.length();//按string的长度从小到大排序	
}
int main(){string str[3] = {"better", "a", "person"};sort(str, str + 3, cmp);//把string型数组按照字典序从小到大输出for(int i = 0; i < 3; i++)cout<<str[i]<<endl; //a better personreturn 0;
} 

简单应用

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
bool cmp1(int a, int b){return a > b;
}bool cmp2(string s1, string s2){return s1.length() < s2.length();
}
int main(){vector<int> vi;vi.push_back(2);vi.push_back(-1);vi.push_back(1);sort(vi.begin(), vi.end(), cmp1);for(vector<int>::iterator it = vi.begin(); it != vi.end(); it++)cout << *it << " ";string str[5] = {"dd", "dad", "a", "baab"};sort(str, str + 5, cmp2);for(int i = 0; i < 5; i++)cout << str[i] << endl;return 0;
}

6.9.7 lower_bound() 大于等于 && upper_bound() 大于

• lower_bound(first, last, val) : 返回在数组或容器中的[first, last)范围内第一个值大于等于val元素的数组位置或容器迭代器
• upper_bound(first, last, val) : 返回在数组或容器中的[ first, last)范围内第一个值大于val元素的数组位置或容器迭代器

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){vector<int> vi;for(int i = 1; i < 10; i++)vi.push_back(i);for(int i = 0; i < vi.size(); i++)printf("%d ", vi[i]);printf("\n");vi.erase(vi.begin() + 4);for(int i = 0; i < vi.size(); i++)printf("%d ", vi[i]);printf("\n");printf("%d %d", *lower_bound(vi.begin(), vi.begin() + 10, 5), *upper_bound(vi.begin(), vi.begin() + 10, 5));printf("\n");printf("%d %d", *lower_bound(vi.begin(), vi.begin() + 9, 6), *upper_bound(vi.begin(), vi.begin() + 9, 6));return 0;
}