算法笔记之蓝桥杯&pat系统备考(1)
文章目录
- 五、数学问题
- 5.2最大公约数和最小公倍数
- 5.2.1最大公约数
- 5.2.2最小公倍数
- 5.3分数的四则运算
- 5.3.1分数的表示与化简
- 5.3.2分数的四则运算
- 5.3.3分数的输出
- 5.4素数(质数)
- 5.4.1[素数的判断](https://blog.csdn.net/Moliay/article/details/132828386?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522170981514616800197021234%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=170981514616800197021234&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-132828386-null-null.nonecase&utm_term=%E7%B4%A0%E6%95%B0&spm=1018.2226.3001.4450)
- 5.4.2素数表的获取
- 5.5质因子分解
- 5.6大整数运算
- 5.6.1大整数的存储
- 5.6.2大整数的四则运算
- 高精度加法
- 高精度减法
- 高精度与低精度的乘法
- 高精度与低精度的除法
- 六、c++标准模板库(STL)
- 6.1vector变长数组
- vector定义
- vector容器内元素的访问
- 1.通过下标访问
- 2.通过迭代器访问
- vector常用函数
- vector常见用途
- 6.2set(升序、去重)
- set定义
- set容器内元素的访问
- set常用函数
- set常见用途
- 6.3string字符串
- string定义
- string中内容的访问
- string常用函数
- 6.4map键值对
- map定义
- map中内容的访问
- map常见函数
- map常见用途
- 6.8pair
- pair定义
- pair中元素的访问
- pair常用函数
- pair常见用途
- 6.9 algorithm头文件下的常用函数
- 6.9.1 max(), min()和 abs()
- 6.9.6sort()
- sort()使用
- 实现比较函数
- (1)基本数据类型数组的排序
- (2)结构体数组的排序
- (3)容器的排序
- 6.9.7 lower_bound() 大于等于 && upper_bound() 大于
五、数学问题
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质因子分解
- 质因子分解:把一个正整数写为若干个质数相乘的形式
- 109 内整数本质不同质因数不会超过十个
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定义并初始化:
- 定义并用n个val来初始化的vector
vector<typename> name(n, val);
vector<int> vi(10, 1);//用10个1来初始化vector
- 定义并用迭代器区间来初始化的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
- 除了上述两种,还有三种
//一共有这五种初始化方式(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常见用途
- 作为数组使用,尤其是元素个数不确定的场合;当需要输出部分数据且中间用空格隔开而末尾不能有多余空格时,可以先用vector记录所有需要输出的数据,再一次性输出
- 用邻接表存储图
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中内容的访问
- 通过下标访问
一般而言,可以直接像字符数组那样去访问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;
}
- 通过迭代器访问
一般情况下用下标进行访问即可,但有些函数比如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,返回值和上个函数相同
- str.find(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;
}