网站的积分系统怎么做,网站域名空间续费合同,医院网站建设方案青岛卓信,广东华星建设集团网站算法笔记之蓝桥杯pat系统备考#xff08;1#xff09; 文章目录 五、数学问题5.2最大公约数和最小公倍数5.2.1最大公约数5.2.2最小公倍数 5.3分数的四则运算5.3.1分数的表示与化简5.3.2分数的四则运算5.3.3分数的输出 5.4素数#xff08;质数#xff09;5.4.1[素数的…算法笔记之蓝桥杯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%257Drequest_id170981514616800197021234biz_id0utm_mediumdistribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-132828386-null-null.nonecaseutm_term%E7%B4%A0%E6%95%B0spm1018.2226.3001.4450)5.4.2素数表的获取 5.5质因子分解5.6大整数运算5.6.1大整数的存储5.6.2大整数的四则运算高精度加法高精度减法高精度与低精度的乘法高精度与低精度的除法 六、c标准模板库STL6.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.8pairpair定义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的所有公约数中最大的那个公约数
#includestdio.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);//若为真分数则直接原样输出
}简单应用
#includestdio.h
#includemath.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若对任意的正整数 a1an都有n%a ! 0成立则a时素数合数除了1和本身外还存在至少一个能被整除的数。例如4还能被2整除则为合数1既不是素数也不是合数
5.4.1素数的判断
5.4.2素数表的获取
素数筛法时间复杂度O(nloglogn)
#includeiostream
#includevector
using namespace std;
const int maxN 101;
int main(){vectorint 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)。 简单应用
#includeiostream
#includemap
typedef long long LL;
using namespace std;
int main(){mapLL, 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(mapLL, 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;
}简单应用
#includestdio.h
#includestring.hstruct 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[i1]--;}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需要添加
#includevector
using namespace std;vector定义
其中typename可以说任意基本类型也可以是STL标准容器例如vector、set、queue等。注意当typename也是STL容器时定义时要在符号之间加上空格。 因为一些使用C11之前标准的编译器会把它视为移位操作导致编译错误。 vectortypename name;vectordouble name;
vectornode name;//node是结构体的类型//二维vector数组可以理解为两个维都可变长的二维数组
vectorvectorint name;//之间记得加空格vector数组的定义 其中Arrayname[0]~Arrayname[arraySize - 1]中每一个都是一个vector容器 。与vectorvector typename name区别在于该种写法的一维长度已经固定为arraySize另一维才是变长的。
vectortypename Arrayname[arraySize];vectorint vi[100];以上定义的为空vector vector定义并初始化
定义并用n个val来初始化的vector
vectortypename name(n, val);vectorint vi(10, 1);//用10个1来初始化vector定义并用迭代器区间来初始化的vector
vectorint vi1(vi.begin(), vi.end());//用vi的迭代器区间来初始化vi1
string s(you are so pretty);
vectorchar v(s.begin(), s.end());//用s的迭代器区间来初始化v除了上述两种还有三种 //一共有这五种初始化方式(1) vectorint a(10); //定义了10个整型元素的向量尖括号中为元素类型名它可以是任何合法的数据类型但没有给出初值其值是不确定的。2vectorint a(10,1); //定义了10个整型元素的向量,且给出每个元素的初值为13vectorint a(b); //用b向量来创建a向量整体复制性赋值4vectorint a(b.begin(),b.begin3); //定义了a值为b中第0个到第2个共3个元素5int b[7]{1,2,3,4,5,9,8};vectorint a(b,b7); //从数组中获得初值vector容器内元素的访问
1.通过下标访问
类似于普通数组对于一个定义为vector typename vi的vector容器而言直接访问vi[index]即可其中下标index范围为[0, vi.size()-1] 注意下面这种做法以及类似的做法都是错误的。下标只能用于获取已存在的元素而现在的vi[i]还是空的对象
2.通过迭代器访问
所谓迭代器iterator可理解为类似指针的东东 其中it是一个vector typename::iterator型的变量
vectortypename::iterator it;vi.begin()函数取vector容器vi的首元素地址vi.end()函数取vector容器vi的尾元素地址的下一个地址 老外习惯左闭右开 #includestdio.h
#includevector
using namespace std;
int main(){vectorint vi;for(int i 1; i 6; i)vi.push_back(i);vectorint::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(vectorint::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)c11新加可以理解为实现更优雅的push_back() pop_back() : 删除vector的尾元素时间复杂度为O(1)
#includestdio.h
#includevector
using namespace std;
int main(){vectorint 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)内的所有元素
#includestdio.h
#includevector
using namespace std;
int main(){vectorint 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需要添加
#includeset
using namespace std;整体和vector容器非常相似下述简化描述
set定义
settypename name;setint name;
setnode name;set数组定义
settypename Arrayname[arraySize];setint a[100];set容器内元素的访问
set只能通过迭代器(iterator)访问元素
settypename::iterator it;#includestdio.h
#includeset
using namespace std;
int main(){setint st;st.insert(5);st.insert(3);st.insert(4);st.insert(3);st.insert(1);//除了vector和string之外的STL容器都不支持*(it i)的访问方式则只能按照如下方式枚举 for(setint::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内元素的个数
#includestdio.h
#includeset
using namespace std;
int main(){setint st;st.insert(5);//set(x)把元素x插入到set容器中且自动实现增序和去重 st.insert(3);st.insert(4);st.insert(3);st.insert(1);for(setint::iterator it st.begin(); it ! st.end(); it){printf(%d , *it);}setint::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(setint::iterator it st.begin(); it ! st.end(); it){printf(%d , *it);}//erase(value) 其中value是要删除元素的值 st.erase(4);//删除set中值为4的元素 printf(\n);for(setint::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(setint::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,需要添加
#includestring
using namespace std;string定义
定义string的方式跟基本数据类型相同直接在string后跟变量名即可
string str;若初始化可以直接给string类型的变量进行赋值
string str harder;string中内容的访问
通过下标访问 一般而言可以直接像字符数组那样去访问string
#includestdio.h
#includestring
using namespace std;
int main(){string str fighting!;for(int i 0; i str.length(); i){printf(%c , str[i]);}return 0;
} 读入和输出整个字符串
#includeiostream
#includestring
using namespace std;
int main(){string str;cinstr;coutstr;printf(\n%s, str.c_str());return 0;
} 通过迭代器访问 一般情况下用下标进行访问即可但有些函数比如insert()和erase()要求以迭代器为参数需要了解string迭代器的用法
string::iterator it;#includestdio.h
#includestring
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直接拼接起来
#includeiostream
#includestring
using namespace std;
int main(){string str1 fighting,, str2 blue!;str1 str2;//fighting,blue!str2 str2;//blue!blue!coutstr1endl;printf(%s, str2.c_str());return 0;
} 比较操作、!、、、、 : 比较规则是字典序
#includeiostream
#includestring
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号位置上插入字符串stringpos从0开始
#includeiostream
#includestring
using namespace std;
int main(){string str 123456;str.insert(3, abc);coutstr;return 0;
}insert()续 insert(it, it1, it2) 串[ it1, it2)将会插在it的位置上
#includeiostream
#includestring
using namespace std;
int main(){string str 123456, str1 abcdef;str.insert(str.begin() 3, str1.begin(), str1.begin() 3);coutstr;return 0;
}erase() erase(it) : 用于删除单个元素其中it是需要删除的元素的迭代器erase(first, last) : 删除区间[first, last)内的所有元素erase(pos, length) : 删除从pos开始,length个字符
#includeiostream
#includestring
using namespace std;
int main(){string str 123456, str1 abcdef;//erase(it) 删除单个元素 str.erase(str.begin() 1); //13456 即删除1号位置的元素位置从0开始 coutstrendl;//erase(first, last) 删除区间[first, last)内的所有元素 str.erase(str.end() - 3, str.end());//13 coutstrendl;//erase(pos, length) 删除从pos开始的length个字符 str1.erase(3, 3);//abc 即删除从3号位开始的3个字符 coutstr1;return 0;
}clear() 清空string中的数据substr(pos, len) : 返回从pos位置开始长度为len的子串时间复杂度为O(len)
#includeiostream
#includestring
using namespace std;
int main(){string str1 abcdef123, str2;str2 str1.substr(6, 3);coutstr2endl;//123str1.clear();coutstr1.size();//0return 0;
}string::npos 是一个常数本身的值是-1但由于是unsigned_int类型则也可以认为是unsigned_int类型的最大值。string::pos是find()函数失配时的返回值。
#includeiostream
#includestring
using namespace std;
int main(){
// unsigned int n -1;
// coutnendl;if(string::npos -1) coutstring::npos 1为真endl;
// if(string::npos n) printf(string::npos %u为真, n);
// else couterr;//[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,返回值和上个函数相同
#includeiostream
#includestring
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 coutearly;return 0;
}replace() 时间复杂度为O(str.length()) str.replace(pos, len, str1) : str从pos号位开始、长度为len的子串替换为str1str.replace(it1, it2, str1) : 把str的迭代器[it1, it2)范围的子串替换为str1
#includeiostream
#includestring
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使用需要添加
#includemap
using namespace std;map可以把任何基本类型包括STL容器映射到任何基本类型包括STL容器
map定义
定义一个map,其中前类型为key类型后类型为value类型
maptypename1, typename2 mp;当int型映射到int型也就相当于普通的int型数组了。 注意当字符串到整型的映射时必须使用string而不能使用char数组。 因为char数组作为数组是不能被作为键值的。若想用字符串做映射必须用string。
mapstring, int mp;mapsetint, string mp;//map的键和值也可以是STL容器map中内容的访问
通过下标进行访问 和普通数组的访问同理例如对一个定义为mapchar, int mp的map来说就可以直接使用mp[‘c’]的方式来访问它对应的整数。注意map中的键是唯一的。
#includeiostream
#includemap
using namespace std;
int main(){mapchar, int mp;mp[a] 1;mp[a] 2;//更新,因为键是唯一的 printf(%d, mp[a]);//2return 0;
} 通过迭代器访问 map可使用it-first来访问键使用it-second来访问值。map会以键从小到大的顺序自动排序 因为map内部使用红黑树实现set也是在建立映射的过程中会自动实现从小到大的排序功能 maptypename1, typename2::iterator it;#includeiostream
#includemap
using namespace std;
int main(){mapchar, int mp;mp[c] 4;mp[a] 2;mp[b] 5;for(mapchar, int::iterator it mp.begin(); it ! mp.end(); it){printf(%c : %d\n, it-first, it-second);}return 0;
}map常见函数
find(key) : 返回键为key的映射的迭代器
#includeiostream
#includemap
using namespace std;
int main(){mapchar, int mp;mp[b] 4;mp[a] 1;mp[c] 3;//find(key)返回键为key的映射的迭代器//小复习map可以使用it - first访问键 it - second访问值 mapchar, 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是要删除的区间的末尾迭代器的下一个地址。
#includeiostream
#includemap
using namespace std;
int main(){mapchar, 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(mapchar, int::iterator it mp.begin(); it ! mp.end(); it){printf(%c %d, , it - first, it - second);} printf(\n);mapchar, 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(mapchar, 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中元素的个数
#includeiostream
#includemap
#includestring
using namespace std;
int main(){mapstring, int mp;mp[are] 1;mp[you] 3;mp[ok] 2;for(mapstring, 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,需添加
#includemap
using namespace std;或
#includeutility
using namespace std;由于map的内部实现中设计pair则添加mao头文件会自动添加utility头文件故可以直接偷懒用map头文件来代替utility头文件好记~ pair定义
pair有俩参数分别对应first和second的数据类型它们可以是任意基本数据类型或容器
pairtypename1, typename2 name;pairstring, int p;若在定义pair时进行初始化只需跟上一个小括号里面填写两个想要初始化的元素即可
pairstring, int p(harder, 1);若想要在代码中临时构建一个pair有如下两种方法
把类型定义写在前面后面用小括号内两个元素的方式
pairstring, int(blue, 2)使用自带的make_pair函数
make_pair(first, 1)pair中元素的访问
pair中只有两个元素分别是first和second只需要按正常结构体的方式去访问即可
#includeiostream
#includemap
using namespace std;
int main(){pairstring, int p;p.first fighting;p.second 1;cout p.first p.second endl;p pairstring, 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的大小
#includeiostream
#includemap
using namespace std;
int main(){pairint, int p1(3, 1);pairint, int p2(3, 2);pairint, 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键值对来进行插入
#includeiostream
#includemap
#includestring
using namespace std;
int main(){mapstring, int mp;//mp.insert(that, 4);报错 mp.insert(pairstring, int(this, 2));mp.insert(make_pair(it, 3));for(mapstring, 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的绝对值
#includeiostream
#includealgorithm
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;
}#includeiostream
#includealgorithm
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)之间的元素或容器的迭代器在该范围内反转
#includeiostream
#includealgorithm
#includestring
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语句是为了输出最有一组序列后再退出。
#includeiostream
#includealgorithm
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
#includeiostream
#includevector
#includealgorithm
using namespace std;
int main(){vectorint 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()使用
需要加#includealgorithm和using namespace std;
sort(首元素地址尾元素地址的下一个地址 比较函数选填);若比较函数不填默认从小到大序列元素一定要有可比性对于char型数组默认为字典序对于结构体这种本身没有大小关系需要手动制定比较规则。 ①整型数组
#includecstdio
#includealgorithm
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型数组
#includecstdio
#includealgorithm
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基本数据类型数组的排序
从大到小ab ①整型数组
#includecstdio
#includealgorithm
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;
}②字符型数组
#includecstdio
#includealgorithm
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(){vectorint 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)coutstr[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)coutstr[i]endl; //a better personreturn 0;
} 简单应用
#includeiostream
#includevector
#includestring
#includealgorithm
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(){vectorint vi;vi.push_back(2);vi.push_back(-1);vi.push_back(1);sort(vi.begin(), vi.end(), cmp1);for(vectorint::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元素的数组位置或容器迭代器
#includeiostream
#includevector
#includealgorithm
using namespace std;
int main(){vectorint 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;
}
