怎么建设电影网站,视频直播软件哪个好,扶贫网站开发的目的是什么,开封专业做网站公司文章目录 第3章 排序与查找(一) 排序1.sort函数#xff1a;sort(first,last,comp)2.自定义比较规则3.C函数重载#xff1a;同一个函数名#xff0c;有不同的参数列表4.机试考试最重要的事情#xff1a;能把你曾经做过的题目#xff0c;满分地做出来5.例题例题1#xff1a… 文章目录 第3章 排序与查找(一) 排序1.sort函数sort(first,last,comp)2.自定义比较规则3.C函数重载同一个函数名有不同的参数列表4.机试考试最重要的事情能把你曾经做过的题目满分地做出来5.例题例题1对n个数进行排序例题2整数奇偶排序 北京大学机试上机例题3成绩排序1清华大学复试上机题结构体 . 运算符 例题4成绩排序2例题5成绩排序3 6.习题习题1特殊排序习题2小白鼠排队习题3奥运排序问题 难度困难 (二) 查找1.顺序查找(Liner Search)(1)泛型函数 find()(2)顺序查找存在的问题(3)时间复杂度、空间复杂度 2.二分查找(Binary Search)3.使用map替代二分查找(1)指针迭代器 iterator 4.例题例题1找x例题2查找解法1顺序查找解法2二分查找 代码繁琐解法3map解法4set 例题3找位置 Mid-Hard 5.习题习题1找最小数习题2打印极值点下标 (难度入门)习题3差分计数 难度简单TLE问题处理大数据集的策略降低算法的时间复杂度 第4章 字符串1.C字符数组 char str[1000] 处理输入、输出(1)原理(2)基本操作(2)优势与劣势①C风格字符数组char str[100]②C字符串string 2.C 字符串string 处理更复杂问题(1)基本操作(2)增删改查遍历(3)子串操作(4)其他操作1.string和数值相互转换2.string的输入输出3.一次读入一行(1)C语言fgets()(2)Ccin.getline() 3.例题例题1单词个数统计 难度中等例题2浮点数加法 【高精度运算】难度Mid-Hard例题3W的密码 难度困难 4.习题习题1统计字符串中各类型字符的个数 难度入门习题2大写字母个数统计 难度入门习题3首字母大写 难度简单习题4寻找变化前的01序列 【字符串替换】 (难度简单)习题5大整数排序 难度简单习题6单词替换 【字符串替换】(难度中等)习题7skew数 【进制转换】(难度)习题8复制、剪切、粘贴 (难度) 第3章 排序与查找
(一) 排序
1.sort函数sort(first,last,comp)
C引入了基于快速排序的排序函数sort()
1.sort(first,last,comp)函数的三个参数 ①first为待排序序列起始地址 ②last为最后一个元素的后一个位置的地址 (尾后指针) ③comp为排序方式的函数名(任意起)不填写默认为升序排序。
sort(arr,arr6);
sort(arr,arr6,comp);sort(vec.beign(),vec.end());
sort(vec.beign(),vec.end(),comp);2.C语法数组名作为函数参数会退化为指针。 a r r → a r r [ 0 ] \rm arr→\arr[0] arr→arr[0] ①arr[i]是元素 ②arr是0号元素的地址。arri是i号元素的地址。 ③C语言数组的数组名可以当地址/指针来使用。arr[i] 和 arri 等价 头文件
#include algorithm
using namespace std;排序静态数组、动态数组
#include cstdio
#include algorithm
#include vector
using namespace std;bool compare(int lhs,int rhs){return lhs rhs; //降序排序
}int main() {int arr[6] {2,4,6,1,3,5};sort(arr,arr6); //数组名作为函数参数,退化为指针 : arr - arr[0]vectorint vec {2,4,6,1,3,5};sort(vec.begin(),vec.end());sort(vec.begin(),vec.end(),compare);return 0;
}左闭右开 [arr,arrn)尾后 2.自定义比较规则
①compare函数的返回类型是bool ②默认比较方式是 ③不发生交换返回真 3.C函数重载同一个函数名有不同的参数列表
比较的题目重点就是设计bool comp(int lhs,int rhs)函数。//不发生交换时为真 4.机试考试最重要的事情能把你曾经做过的题目满分地做出来
最重要的不是把所有题目都写了个差不多没用差一点就是零分。要么满分要么零分。 最重要的是把你曾经做过的题目满分地做出来。 泥鳅老师你就算是天纵奇才也不可能在机试的时候把你从来没做过的题目做出来。就是一个熟练度的问题。 5.例题
例题1对n个数进行排序 样例输入 4 1 4 3 2 样例输出 1 2 3 4 #include cstdio
#include algorithm
using namespace std;int main(){int n;int arr[101];scanf(%d,n);for(int i0;in;i){scanf(%d,arr[i]);//arr[i] 和 arri 等价}sort(arr,arrn);//排序for(int i0;in;i){printf(%d ,arr[i]);}printf(\n);
}例题2整数奇偶排序 北京大学机试上机
提交网址https://www.acwing.com/problem/content/3449/ 解法1奇偶分别排序
#include cstdio
#include algorithm
#include vector
using namespace std;bool compare(int lhs,int rhs){return lhs rhs;
}int main() {int arr[10];vectorint vec1; //存奇数vectorint vec2; //存偶数for(int i 0 ; i 10; i){scanf(%d,arr[i]); //arriif(arr[i]%2 0){vec2.push_back(arr[i]);}else{vec1.push_back(arr[i]);}}sort(vec1.begin(),vec1.end(),compare); //奇数降序sort(vec2.begin(),vec2.end());vectorint::iterator it;for(it vec1.begin(); it ! vec1.end(); it) printf(%d ,*it);for(it vec2.begin(); it ! vec2.end(); it) printf(%d ,*it);printf(\n);return 0;
}解法2整体排序重点在于构建 compare函数
#include stdio.h#include algorithmusing namespace std;bool compare(int lhs, int rhs) {if (lhs % 2 1 rhs % 2 0) {return true;}else if (lhs % 2 1 rhs % 2 1 lhs rhs) {return true;}else if (lhs % 2 0 rhs % 2 0 lhs rhs) {return true;}else {return false;}}int main() {int arr[10];for (int i 0; i 10; i) {scanf(%d, arr[i]); // arr i}sort(arr, arr 10, compare);for (int i 0; i 10; i) {printf(%d , arr[i]);}printf(\n);return 0;}例题3成绩排序1清华大学复试上机题
提交网址https://www.acwing.com/problem/content/3379/ https://www.nowcoder.com/share/jump/2891302591706172383452 结构体 . 运算符
解法1结构体 vector
#include cstdio
#include vector
#include algorithm
using namespace std;struct Student{int number;int score;
};bool comp(Student lhs,Student rhs){if(lhs.score rhs.score) return true;else if(lhs.score rhs.score lhs.number rhs.number) return true;else return false;
}int main(){int N,p,q;scanf(%d,N);vectorStudent stu(N);for(int i 0 ; i N; i){scanf(%d%d,stu[i].number,stu[i].score);}sort(stu.begin(),stu.end(),comp);for(int i 0; i N; i){printf(%d %d\n,stu[i].number,stu[i].score);}return 0;
}解法2结构体 数组
#include cstdio
#include algorithm
using namespace std;struct Student {int num;int grade;
};//类的分号不要省略bool comp(Student lhs, Student rhs) {//不发生交换为真if (lhs.grade rhs.grade) {return true;} else if (lhs.grade rhs.grade lhs.num rhs.num) {return true;} else {return false;}
}int main() {int n;Student arr[100];scanf(%d, n);for (int i 0; i n; i) {scanf(%d%d, arr[i].num, arr[i].grade);}sort(arr, arr n, comp);for (int i 0; i n; i) {printf(%d %d\n, arr[i].num, arr[i].grade);}
}例题4成绩排序2
提交网址https://www.acwing.com/problem/content/3378/ #include cstdio
#include algorithm
#include vector
using namespace std;struct Student{char name[20];int score;int seq; //序号成员,实现稳定排序
};bool compare0(Student lhs,Student rhs){ //0表示降序if(lhs.score rhs.score) return true;else if(lhs.scorerhs.score lhs.seq rhs.seq) return true;else return false;
}bool compare1(Student lhs,Student rhs){ //1表示升序if(lhs.score rhs.score) return true;else if(lhs.scorerhs.score lhs.seq rhs.seq) return true;else return false;
}int main() {int N;scanf(%d,N);int method;scanf(%d,method);vectorStudent vec(N);for(int i 0; i N; i){scanf(%s%d,vec[i].name,vec[i].score);vec[i].seq i;}if(method 0) sort(vec.begin(),vec.end(),compare0);else sort(vec.begin(),vec.end(),compare1);for(int i 0; i N; i){printf(%s %d\n,vec[i].name,vec[i].score);}return 0;
}纠错 纠错1 要么上边声明的时候加上长度 要么下边初始化一个Student用Pushback 你这样声明的vec长度为0当然不能直接赋值
纠错2 稳定性等号的问题注意
纠错3 不要忘了对seq赋值vec[i].seq i; 例题5成绩排序3
提交网址http://t.cn/E9gyHM1
#include cstdio
#include algorithm
#include vector
using namespace std;struct Student{char name[20];int score;int seq; //为了保证稳定性
};bool comp0(Student lhs,Student rhs){ //0表示降序if(lhs.score rhs.score) return true;else if(lhs.scorerhs.score lhs.seq rhs.seq) return true;else return false;
}bool comp1(Student lhs,Student rhs){ //1表示升序if(lhs.score rhs.score) return lhs.seq rhs.seq;else return lhs.score rhs.score;
}int main(){int n;while(scanf(%d,n) ! EOF){int order;scanf(%d,order);vectorStudent vec;for(int i 0; i n; i){Student stu;scanf(%s%d,stu.name,stu.score);vec.push_back(stu);vec[i].seq i;}if(order0) sort(vec.begin(),vec.end(),comp0);else sort(vec.begin(),vec.end(),comp1);for(int i 0; i n; i){printf(%s %d\n,vec[i].name,vec[i].score);}}return 0;
}6.习题
习题1特殊排序
提交网址http://t.cn/E9gio39 #include cstdio
#include algorithm
using namespace std;int main() {int n;scanf(%d,n);int arr[1010];int max 0;for(int i 0; i n; i){scanf(%d,arr[i]);if(arr[i] max) max arr[i];}printf(%d\n,max);sort(arr,arrn);for(int i 0; i n-1; i){ //少输出一个最大值,只到n-1printf(%d ,arr[i]);}if(n1) printf(-1\n);return 0;
}习题2小白鼠排队
提交网址http://t.cn/E9gXh9Z #include cstdio
#include algorithm
#include vector
using namespace std;struct Mouse{int weight;char color[20];
};bool comp(Mouse lhs,Mouse rhs){return lhs.weight rhs.weight;
}int main() {int n;scanf(%d,n);vectorMouse vec(n);for(int i 0; i n; i){Mouse mouse;scanf(%d%s,vec[i].weight,vec[i].color);}sort(vec.begin(),vec.end(),comp);for(int i 0; i n; i){printf(%s\n,vec[i].color);}return 0;
}习题3奥运排序问题 难度困难
提交网址http://t.cn/E9gYpyl #include cstdio
#include algorithm
#include vector
using namespace std;struct country{int gold; //金牌int medal; //奖牌int people; //人口(百万)double gold_people gold/people; //金牌人口比例double medal_people medal/people; //奖牌人口比例
};bool compare1(country lhs,country rhs){ //按金牌总数 降序排名return lhs.gold rhs.gold;
}
bool compare2(country lhs,country rhs){ //按奖牌总数 降序排名return lhs.medal rhs.medal;
}
bool compare3(country lhs,country rhs){ //按金牌人口比例 降序排名return lhs.gold_people rhs.gold_people;
}
bool compare4(country lhs,country rhs){ //按奖牌人口比例 降序排名return lhs.medal_people rhs.medal_people;
}int main() {int N,M; //N为总国家数,M为需要给出排名的国家数
// while(scanf(%d,N) ! EOF){scanf(%d,N);scanf(%d,M);vectorcountry vec;for(int i0; iN; i){country cty;scanf(%d %d %d,cty.gold,cty.medal,cty.people);vec.push_back(cty);}//统计需要排名的国家序号vectorint need_sort;int x;for(int i 0; i M; i){scanf(%d,x);need_sort.push_back(x);}//对M个国家进行排名// }return 0;
}(二) 查找
1.顺序查找(Liner Search)
顺序查找的问题效率不够高。 n个元素顺序查找时间复杂度为O(n²)。若数据量规模n在105则会OJ超时。需要采取一些策略降低时间复杂度。 (1)泛型函数 find()
find(begItendItx)
#include algorithm //头文件vectorint::iterator it;
it find(vec.vegin(),vec.end(),x);
if(it vec.end()){printf(-1\n);
}else{pirntf(%d\n,it - vec.begin()); //偏移量,即数组下标
}(2)顺序查找存在的问题
①顺序查找O(N) ②二分查找O(logN)但需要 排序 ③哈希查找O(1)但需要 额外空间 (3)时间复杂度、空间复杂度
0.O()计数法忽略常系数、忽略低阶项 1.时间复杂度指令执行次数 2.空间复杂度额外内存空间 2.二分查找(Binary Search)
1.二分查找(折半查找)只能在有序的数据结构中使用需要先排序。
2.基于比较的排序时间复杂度最好为O(nlogn)
3.N的元素查找M次的时间复杂度O(NlogN M×logN) 二分查找(需要排序)适用于给定一份数据要查很多次。 若每查一次数据都改那就用顺序查找不需要排序。
mid (left right)/2;
left mid 1; /收缩区间注意 1 -1避免二分查找死循环。
right mid - 1;3.使用map替代二分查找 map空间换时间。如果程序对空间要求不高可以用map代替二分查找。若空间卡的比较死则还是得用二分查找。(二分查找的代码比较容易写错) ①二分查找查找的时间复杂度O(logN)不需要空间。代码较长繁琐易出错。 ②map查找的时间复杂度O(logN)需要一定的空间。底层是红黑树。 ③unordered_map查找的时间复杂度O(1)需要更多的空间。底层是哈希表。 map的底层二叉搜索树(BST)。 ①在Windows下会进一步优化为平衡二叉树(AVL树) ②在Linux下会进一步优化为红黑树 (1)指针迭代器 iterator
findIndex.begin()第一个元素的指针 findIndex.end()最后一个元素的后面一个位置的指针尾后指针 findIndex.find()查找某个元素的指针
if(findIndex.find(findNum) findIndex.end()) //说明没有找到4.例题
例题1找x
提交网址http://t.cn/E9gHFnS #include cstdioint main() {int n;scanf(%d,n);int arr[210];for(int i 0; i n; i){scanf(%d,arr[i]);}int x;bool flag false;scanf(%d,x);for(int i 0; i n; i){if(arr[i] x){printf(%d\n,i);flag true;break;}}if(flag false) printf(-1\n);return 0;
}例题2查找
提交网址https://www.acwing.com/problem/content/3545/ 解法1顺序查找
#include cstdioint main() {int n,m,a[110],b[110];scanf(%d,n);for(int i 0; i n; i){scanf(%d,a[i]);}scanf(%d,m);for(int i 0; i m; i){scanf(%d,b[i]);}for(int j 0; j m; j){bool flag false;for(int i 0; i n; i){if(a[i] b[j]){printf(YES\n);flag true;break; //两层for循环时,break只能跳出一层循环}}if(flag false) printf(NO\n);}return 0;
}解法2二分查找 代码繁琐
#include cstdio
#include vector
#include algorithm
using namespace std;int main() {int n;scanf(%d,n);vectorint a(n);for(int i 0; i n; i){scanf(%d,a[i]);}sort(a.begin(),a.end());int m,b;scanf(%d,m);for(int i 0; i m; i){scanf(%d,b);//二分查找int left 0, right n-1;while(left right){int mid (leftright)/2;if(b a[mid]){printf(YES\n);break;}else if(b a[mid]){right mid-1;}else{left mid1;}}if(left right) printf(NO\n);}return 0;
}解法3map
对map使用find()函数查找的是键
#include cstdio
#include map
using namespace std;int main(){int n,a;mapint,int mymap;scanf(%d,n);for(int i 0; i n; i){scanf(%d,a);mymap.insert({a,i}); //key:元素的值,value:元素的位置}int m,b;scanf(%d,m);for(int i 0; i m; i){scanf(%d,b); 对map使用find(),查找的是键if(mymap.find(b) ! mymap.end()) printf(YES\n);else printf(NO\n);}return 0;
}解法4set
#include cstdio
#include vector
#include set
using namespace std;int main() {int n,x;scanf(%d,n);setint a;for(int i 0; i n; i){scanf(%d,x);a.insert(x);}int m,b;scanf(%d,m);for(int i 0; i m; i){scanf(%d,b);if(a.find(b) ! a.end()) printf(YES\n);else printf(NO\n);}return 0;
}例题3找位置 Mid-Hard
提交网址https://www.acwing.com/problem/content/3613/ #include cstdio
#include vector
#include map
#include cstring
#include algorithm
using namespace std;int main() {char str[110] {0};scanf(%s,str);multimapchar,int mymap;vectorchar seq; //记录每个字符出现的先顺序for(int i 0; i strlen(str); i){ //str[i] ! \0if(find(seq.begin(),seq.end(),str[i]) seq.end()){ //说明字符str[i]是第一次出现seq.push_back(str[i]); //则加入seq中,即记录字符出现的顺序}mymap.insert({str[i],i});}vectorchar::iterator it; //it是字符出现顺序seq的迭代器multimapchar,int::iterator it1;for(it seq.begin(); it ! seq.end(); it){if(mymap.count(*it) 1){ //该字符在mymap中重复出现bool isFirst true; //引入isFirst,为了去掉每行结尾的逗号for(it1 mymap.begin(); it1 ! mymap.end(); it1){if(it1-first *it){ //seq中的字符和mymap中的键 相匹配时if(isFirst false){printf(,);}printf(%c:%d,it1-first,it1-second);isFirst false;}}printf(\n);}}return 0;
}5.习题
习题1找最小数
提交网址http://t.cn/E9gekWa 结构体数组
#include cstdio
#include algorithm
using namespace std;struct NUM{int x;int y;
};bool comp(NUM lhs,NUM rhs){if(lhs.x rhs.x){return lhs.y rhs.y;}else{return lhs.x rhs.x;}
}int main(){int n;scanf(%d,n);NUM num[1010]; //结构体数组int x,y;for(int i 0; i n; i){scanf(%d%d,num[i].x,num[i].y);}sort(num,numn,comp);printf(%d %d\n,num[0].x,num[0].y);return 0;
}习题2打印极值点下标 (难度入门)
提交网址https://www.acwing.com/problem/content/3440/ #include cstdioint main() {int n;scanf(%d,n);int arr[110];for(int i 0; i n; i){scanf(%d,arr[i]);}//判断左端点if(arr[0] ! arr[1]) printf(0 );//判断中间for(int i 1 ; i n-1; i){if( (arr[i]arr[i-1] arr[i]arr[i1]) || (arr[i]arr[i-1] arr[i]arr[i1]) ){printf(%d ,i);}}//判断右端点if(arr[n-1] ! arr[n-2]) printf(%d\n,n-1);return 0;
}习题3差分计数 难度简单
提交网址https://www.acwing.com/problem/content/5080/ 解1暴力求解数组 两层for循环枚举结果TLE。时间复杂度O(n²)n为106运行次数为 1012109
#include cstdioint arr[1000010]; //申请全局数组,若在main函数内申请如此大的数组 会爆栈,即栈溢出(Segementation fault)int main() {int n,x;scanf(%d,n);scanf(%d,x);for(int i 0; i n; i){scanf(%d,arr[i]);}int count 0;for(int i 0; i n; i){for(int j 0; j n; j){if(arr[i]-arr[j] x) count;}}printf(%d\n,count);return 0;
}解2优化为用哈希表 unordered_map存储时间复杂度O(n)
在这里插入代码片TLE问题处理大数据集的策略降低算法的时间复杂度
①TLE (Time Limit Exceeded时间超过)的限制是运行次数不超过 1 0 9 10^9 109。 而对于数据规模n达到 1 0 6 10^6 106级别时间复杂度最高只能为 O ( n l o g n ) O(nlogn) O(nlogn)若为 O ( n 2 ) O(n²) O(n2)则超时运行了 1 0 12 10^{12} 1012次。 ②若申请动态数组还是 TLE则只能优化算法不能暴力求解如m层for循环枚举的时间复杂度为 O ( n m ) O(n^m) O(nm)。 应当思考如何优化算法 以降低算法的时间复杂度减少 不必要的计算 或 重复计算如 缩小搜索范围、用数组存储会重复使用到的数值。 第4章 字符串
1.C字符数组 char str[1000] 处理输入、输出
(1)原理
1.char的C风格字符数组每个单元只能存储1个字符
2.C风格字符串要多一个字节存储 终止符 \0 区分 ①可打印字符 0 ②终止符 0 或 \0 (2)基本操作
1.声明 char 字符数组名[大小];
2.初始化直接赋值0或用memset
char str[1000] {0};#include cstringchar str[1000];
memset(str,0,sizeof(str));3.输入 字符数组的输入可以省略。因为数组名本身就是一个地址不需要再取地址
scanf(%s,str);4.输出
printf(%s\n,str);5.字符数组转stringstring 字符串名 字符数组名 ; 步骤 ①先声明字符数组 ②字符数组操作如输入 ③转string string 字符串名 字符数组名 ; ④字符串操作 ⑤输出 printf(%s,字符串名.c_str()); 注意只有%s的时候输出string需要加 .c_str()转换。而%c的时候可以直接输出str[i] #include cstdio
#include string
using namespace std;int main(){char buf[100];scanf(%s,buf);//%s不用加string str buf;//C风格字符数组 → C风格字符串直接赋值printf(%s\n,str.c_str());//C风格字符串→C风格字符数组:.c_str()return 0;
}6.读取一整行 fgets(字符数组名,sizeof(字符数组名),stdin)
fgets最后会读入换行符\n 占一个空间字符数组转string后考虑用pop_back()干掉回车
7.getchar() 吃掉回车 (2)优势与劣势
①C风格字符数组char str[100]
1.C风格字符数组的优势可以直接使用scanf和printf
2.C风格字符数组的劣势 ①不支持 赋值、相等判断、比大小 ②不支持 提取子串、字符串匹配 ③C风格字符串不能作为map和set的参数 ④内存管理麻烦 (数组与指针的转换) ②C字符串string
1.string的优势 ①像内置类型 (int/long/float/double)支持 、、、、、、
②类似于 vectorchar支持 push_back()、insert、erase、clear、迭代器、方括号运算符
③支持子串操作求子串 substr()、字符串匹配 2.string的缺陷 string不能直接和printf、scanf交互 2.C 字符串string 处理更复杂问题
(1)基本操作
1.头文件
#include string
using namespace std;2.初始化支持 赋值操作
string str1 hello;
string str2 str1;3.求长度 ①.length(); ②.size();
printf(length of str %u\n,str.size());(2)增删改查遍历
1.遍历 (1)方括号运算符 下标访问元素str[i]i从0开始
for(unsigned int i 0;i str.size(); i){printf(%c\n,str[i]);
}(2)迭代器
for(string::iterator it str.beign(); it ! str.end(); it){//it 更改迭代器的指向到下一个元素printf(%c\n, *it); // 取地址, *取内容。*it 通过地址访问元素
}string 对比 vectorchar 拓展了insert 和 erase 的用法可以一次操作多个字符 2.插入 (1)末尾插入push_back(n)
(2)指定位置插入
insert(it,A); //迭代器插入
insert(0,xyz); //指定下标插入,可以一次操作插入多个字符3.删除 (1)删除最后一个字符pop_back()
(2)字符串清空 clear()
str.clear();(3)指定位置删除erase(下标)
str.erase(str.size()-1); //删除最后一个元素即\n
str.erase(it); //迭代器指定位置①删除position处的一个字符(position是个string类型的迭代器) erase(position);
②删除从pos开始的n个字符比如erase(0,1)就是删除第一个字符 erase(pos,n);
string str abcdef;
str.erase(1,2); //从下标1开始,删除2个,应该删除bc③删除从first到last之间的字符first和last都是迭代器 erase(first,last); (4)按照元素删除删除指定字符 如删除字符串a中的的逗号
string str;
string::iterator it;
for(itstr.begin();it!str.end();it){if(*it ,){str.erase(it);}
}4.查找字符串匹配 find(字符串内容) find(字符串内容,起始下标)
返回值是第一次匹配成功的下标。若查找失败则返回string::npos即-1
int pos str.find(do); //查找匹配字符串do,不写起始下标,默认为从开始
if(pos string::npos) printf(do is not found!\n);查找 查询字符或字符子串的下标 .find(内容) ①find(字符串) ②find(变量名) 用string的find函数进行字符串匹配的例题CPP33 统计字符串中子串出现的次数 #include iostream
#include cstring
#include string
using namespace std;int main() {char str[100] { 0 };char substr[100] { 0 };cin.getline(str, sizeof(str));cin.getline(substr, sizeof(substr));int count 0;// write your code here......string str1 str;string str2 substr;int pos str1.find(str2);while(pos ! string::npos){count;pos str1.find(str2,pos1);}cout count endl;return 0;
}(3)子串操作
1.从C风格字符串转到C风格字符串str1.c_str() 2.判断相等支持
bool isSame false;
isSame (str1 hello);3.连接 (只针对C风格字符串string类型C风格字符数组禁止相加)
string str buf;
str str world;4.string比较大小从最高位比ASCII码字典序
string str1 a;
string str2 Z;
if(str1str2) coutstr1str2endl;
else coutstr1str2endl;输出aZ ASCII码 原因 ①A的ASCII码为65Z的ASCII码为90 ②a的ASCII码为97z的ASCII码为122 ③大写字母 32 小写字母 小写字母 -32 大写字母
if(arr[i]A arr[i]Z) arr[i] 32; //大写转小写
if(str[i]a str[i]z) str[i] - 32; //小写转大写5.string支持方括号运算符支持下标访问
#include iostream
#include string
#include cstring
using namespace std;int main() {string str abcdef;char ch[26];for(int i 0; i str.size(); i){ch[i] str[i];}for(int i 0; i strlen(ch); i){coutch[i] ch[i]endl;}return 0;
}输出: ch[0] a ch[1] b ch[2] c ch[3] d ch[4] e ch[5] f 6.取子串 (1)从起始下标到字符串结尾 substr(起始下标)
(2)从指定下标开始截取指定长度 substr(起始下标截取的长度)
string str2 str1.substr(0,3); //从0开始,长度为3 (4)其他操作
1.string和数值相互转换 int i 1234;
string str1 to_string(i);float f 3.14;
string str2 to_string(f);string str1 3.1415;
f stof(str1);string str2 31415;
i stoi(str2);2.string的输入输出
1.输入
char arr[100];
scanf(%s,arr); //先读到字符数组
string str arr; //再转成string2.输出 (1)printf 的 c_str() (2)cin 和 cout cin 和 cout不能和 scanf、printf 混用 3.一次读入一行
(1)C语言fgets()
1.C语言用fgets()读入一整行的内容包括换行符 \n
2.fgets(字符数组首地址,申请内存的长度,stdin);
fgets(arr,200,stdin);(2)Ccin.getline()
char str[100] { 0 };
char substr[100] { 0 };cin.getline(str, sizeof(str));
cin.getline(substr, sizeof(substr));3.例题
例题1单词个数统计 难度中等
提交网址https://www.acwing.com/problem/content/3618/ #include iostream
#include string
#include map
using namespace std;int main(){string s;getline(cin,s);int count_letter 0,count_word 1; //最后一个单词没有空格mapchar,int mymap; //用 mapchar,int 统计字母出现次数for(int i 0; i s.size(); i){//1.统计字母个数if((s[i]a s[i]z) || (s[i]A s[i]Z) ){count_letter;}//2.统计单词个数if(s[i] s[i1] ! ){count_word;}//3.统计出现次数最多的字母 (不区分大小写,全部以小写为主)if((s[i]a s[i]z) || (s[i]A s[i]Z) ){if(s[i]A s[i]Z){s[i] s[i]32; //大写转小写}mymap[s[i]];}}cout count_letter endl count_word endl;int max 0; //字母出现次数的最大值mapchar,int::iterator it;for(it mymap.begin(); it ! mymap.end(); it){if(it-second max) max it-second;}for(it mymap.begin(); it ! mymap.end(); it){if(it-second max){cout it-first ;}}cout endl max endl;return 0;
}例题2浮点数加法 【高精度运算】难度Mid-Hard
提交网址http://t.cn/Ai8I4v0j
高精度运算用字符串模拟竖式运算
王道《上机指南》 2024炉灰老师的解法这是我做过的代码最多的一道题93行。当然整数相加部分的if、else if有很多近似重复代码
#include iostream
#include string
using namespace std;//获取整数部分
string GetInterger(string a){return a.substr(0,a.find(.));
}//获取小数部分
string GetFraction(string a){return a.substr(a.find(.)1);
}//小数部分相加
void FractionPlus(string res,int carry,string fa,string fb){//长度短的小数,补0int size max(fa.size(),fb.size());while(fa.size() size){fa.push_back(0);}while(fb.size() size){fb.push_back(0);}
// cout fa fa endl fb fb endl;res.resize(size); //给res申请内存空间for(int i size-1; i 0; --i){ //从右向左遍历if(fa[i] fb[i] carry - 0 9){res[i] fa[i] fb[i] carry - 0 - 10;carry 1;}else{res[i] fa[i] fb[i] carry - 0;carry 0;}}
// cout fres res endl carry carry endl;
}//整数部分相加
void IntegerPlus(string res, int carry,string ia,string ib){res.clear();for(int i ia.size()-1,j ib.size()-1; i 0 || j 0 || carry 1; --i,--j){if(i 0 j 0){ //1.a和b都有if(ia[i] ib[j] carry - 0 9){res.insert(res.begin(),ia[i] ib[j] carry - 0 - 10);carry 1;}else{res.insert(res.begin(),ia[i] ib[j] carry - 0);carry 0;}}else if(i 0 j 0){ //2.只有aif(ia[i] carry 9){res.insert(res.begin(),ia[i] carry - 10);carry 1;}else{res.insert(res.begin(),ia[i] carry);carry 0;}}else if(i 0 j 0){ //3.只有bif(ib[j] carry 9){res.insert(res.begin(),ib[j] carry - 10);carry 1;}else{res.insert(res.begin(),ib[j] carry);carry 0;}}else{ //4.既没有a,也没有b,只有进位 carry1res.insert(res.begin(),1);carry 0;}}
// cout ires res endl carry carry endl;
}int main() {string a,b;cin a b;
// a 12345.6789;
// b 333.33333;string ia,fa,ib,fb;ia GetInterger(a);fa GetFraction(a);ib GetInterger(b);fb GetFraction(b);
// cout ia ia endl fa fa endl ib ib endl fb fb endl endl;string fres;int carry 0;FractionPlus(fres,carry,fa,fb);string ires;IntegerPlus(ires,carry,ia,ib);cout ires . fres endl;return 0;
}例题3W的密码 难度困难
提交网址https://www.acwing.com/problem/content/3408/ #include iostream
#include string
#include vector
using namespace std;void Partition(string str,vectorint vec1,vectorint vec2,vectorint vec3){int i;for(i 0; i str.size(); i){if(str[i] a str[i] i){vec1.push_back(i);}else if(str[i] j str[i] r){vec2.push_back(i);}else{vec3.push_back(i);}}
}//右旋
void RightRotate(string str, vectorint vec, int offset){vectorchar tmp;if (vec.size() ! 0 offset vec.size()) {offset offset % vec.size();}for(int i vec.size() - offset; i vec.size(); i){tmp.push_back(str[vec[i]]);}for(int i vec.size() - offset - 1; i 0; --i){str[vec[i offset]] str[vec[i]];}for(int i 0; i tmp.size(); i){str[vec[i]] tmp[i];}
}int main() {
// string str _icuo_bfnwhoq_kxert;
// int k1 2, k2 3, k3 1;string str;int k1,k2,k3;while(cin k1 k2 k3){if(k10 k20 k30) break;cin str;vectorint vec1, vec2, vec3;Partition(str,vec1,vec2,vec3);RightRotate(str,vec1,k1);RightRotate(str,vec2,k2);RightRotate(str,vec3,k3);cout str endl;}return 0;
}4.习题
习题1统计字符串中各类型字符的个数 难度入门
提交网址https://www.nowcoder.com/share/jump/2891302591707795122907 #include iostream
#include cstring
using namespace std;int main() {int letter 0;int digit 0;int space 0;int other 0;char buf[1024] {0};cin.getline(buf, sizeof(buf));// write your code here......for(int i 0; buf[i] ! \0; i){if((buf[i]A buf[i]Z) || (buf[i]a buf[i]z)) letter;else if( buf[i]0 buf[i]9 ) digit;else if(buf[i] ) space;else other;} //end cout letter: letter digit: digit space: space other: other endl;return 0;
}习题2大写字母个数统计 难度入门
提交网址http://t.cn/Ai8VB72e 次数为0的字母也要统计所以本题不可用 mapchar,int可以用一个int数组统计各字母出现的次数
#include iostream
#include string
using namespace std;int main() {string str;getline(cin,str);int count[26] {0};for(int i 0; i str.size(); i){if(str[i]A str[i]Z){count[str[i]-A];}}for(int i 0; i 26; i){printf(%c:%d\n,Ai,count[i]);}return 0;
}习题3首字母大写 难度简单
提交网址https://www.nowcoder.com/share/jump/2891302591707807598497 用getline(cin,str)读入一行。用空白符分割单词判断是否为单词的首字母
#include iostream
#include string
using namespace std;int main(){string str;while(getline(cin,str)){//首字母小写转大写if(str[0]a str[0]z) str[0] str[0]- 32;coutstr[0];//保持空白符不变for(int i 1; i str.size(); i){if(str[i] || str[i]\t || str[i]\r || str[i]\n ){if(str[i1]a str[i1]z){str[i1] - 32; //空白符后的单词首字母大写} }coutstr[i];}}return 0;
}习题4寻找变化前的01序列 【字符串替换】 (难度简单)
提交网址https://www.acwing.com/problem/content/3547/ 解法1 用count统计连续出现的1的个数当count为5时就屏蔽输出下一个字符(一定是0)
#include iostream
#include string
using namespace std;int main() {int n;cin n;while(n--){string str;cin str;int count 0;for(int i 0; i str.size(); i){if(str[i] 1){count;cout str[i];}else{if(count5){count 0;continue; //不输出字符0,直接检查下一个字符}coutstr[i];count 0;}}cout endl;}return 0;
}解法2replace()函数
# include iostreamusing namespace std;
int T;
string s;
const string find_one 111110;
const string change_one 11111;
int main()
{//cin.sync_with_stdio(false);cin T;for(size_t _ 0; _ ! T; _){cin s;size_t place 0;place s.find(find_one , place);for(; place ! string::npos place s.length(); s.replace(place , 6 , change_one) , place 5 , place s.find(find_one , place)) ;// 111110长度6cout s \n;}return 0;
}习题5大整数排序 难度简单
提交网址https://www.acwing.com/problem/content/3611/ 思路借用vector的自动排序功能对sort函数添加上comp中按字符串长度升序排序长度相等时按ab字典序排序。关键在于comp函数的构建
#include iostream
#include string
#include vector
#include algorithm
using namespace std;bool comp(string a,string b){if(a.size() b.size()) return true;else if(a.size() b.size()) return false;else return ab;
}int main() {int n;cin n;string s;vectorstring vec;for(int i 0; i n; i){cin s;vec.push_back(s);}sort(vec.begin(),vec.end(),comp);vectorstring::iterator it;for(it vec.begin(); it ! vec.end(); it){cout *it endl;}return 0;
}习题6单词替换 【字符串替换】(难度中等)
提交网址http://t.cn/Ai8Iycp6 字符串替换用vectorstring
#include iostream
#include string
#include vector
using namespace std;int main(){//1.读入一整行string s,a,b;getline(cin,s); cin a b;//2.分割单词,存入vectorvectorstring vec;string sub ; //子串,初始为空for(int i 0 ; i s.size(); i){if(s[i] ! ){sub sub s[i];}else{vec.push_back(sub);sub.clear();}if(i s.size()-1){ //存入最后一个单词vec.push_back(sub);sub.clear();}}//3.替换for(int i 0; i vec.size(); i){if(vec[i] a){vec[i] b;}}//4.遍历输出vectorstring::iterator it;for(it vec.begin(); it ! vec.end(); it){cout *it ;}cout endl;return 0;
}习题7skew数 【进制转换】(难度)
提交网址http://t.cn/Ai8IALKI 习题8复制、剪切、粘贴 (难度)
提交网址https://www.acwing.com/problem/content/3549/
