文章目录
- 第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：二分查找 （代码繁琐）
- 解法3：map
- 解法4：set
- 例题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)C++：cin.getline()
- 3.例题
- 例题1：单词个数统计 （难度：中等）
- 例题2：浮点数加法 【高精度运算】（难度：Mid-Hard）
- 例题3：W的密码 （难度：困难）
- 4.习题
- 习题1：统计字符串中各类型字符的个数 （难度：入门）
- 习题2：大写字母个数统计 （难度：入门）
- 习题3：首字母大写 （难度：简单）
- 习题4：寻找变化前的01序列 【字符串替换】 (难度：简单)
- 习题5：大整数排序 （难度：简单）
- 习题6：单词替换 【字符串替换】(难度：中等)
- 习题7：skew数 【进制转换】(难度：)
- 习题8：复制、剪切、粘贴 (难度：)
第3章 排序与查找
(一) 排序
1.sort函数：sort(first,last,comp)
C++引入了基于快速排序的排序函数：sort()
1.sort(first,last,comp)函数的三个参数：
①first为待排序序列起始地址
②last为最后一个元素的后一个位置的地址 (尾后指针)
③comp为排序方式的函数名(任意起)，不填写默认为升序排序。
sort(arr,arr+6);
sort(arr,arr+6,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号元素的地址。arr+i是i号元素的地址。
③C语言数组的数组名，可以当地址/指针来使用。&arr[i] 和 arr+i 等价
头文件：
#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,arr+6); //数组名作为函数参数,退化为指针 : arr -> &arr[0]
vector<int> vec = {2,4,6,1,3,5};
sort(vec.begin(),vec.end());
sort(vec.begin(),vec.end(),compare);
return 0;
}
左闭右开 [arr,arr+n)，尾后
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 i=0;i<n;++i){
scanf("%d",&arr[i]);//&arr[i] 和 arr+i 等价
}
sort(arr,arr+n);//排序
for(int i=0;i<n;++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];
vector<int> vec1; //存奇数
vector<int> vec2; //存偶数
for(int i = 0 ; i < 10; ++i){
scanf("%d",&arr[i]); //arr+i
if(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());
vector<int>::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 <algorithm>
using 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);
vector<Student> 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.score==rhs.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.score==rhs.score && lhs.seq < rhs.seq) return true;
else return false;
}
int main() {
int N;
scanf("%d",&N);
int method;
scanf("%d",&method);
vector<Student> 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.score==rhs.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);
vector<Student> 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(order==0) 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,arr+n);
for(int i = 0; i < n-1; ++i){ //少输出一个最大值,只到n-1
printf("%d ",arr[i]);
}
if(n==1) 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);
vector<Mouse> 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);
vector<country> vec;
for(int i=0; i<N; ++i){
country cty;
scanf("%d %d %d",&cty.gold,&cty.medal,&cty.people);
vec.push_back(cty);
}
//统计需要排名的国家序号
vector<int> 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(begIt，endIt，x)
#include <algorithm> //头文件
vector<int>::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 <cstdio>
int 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 <cstdio>
int 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);
vector<int> 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 = (left+right)/2;
if(b == a[mid]){
printf("YES\n");
break;
}else if(b < a[mid]){
right = mid-1;
}else{
left = mid+1;
}
}
if(left > right) printf("NO\n");
}
return 0;
}
解法3：map
对map使用find()函数，查找的是键
#include <cstdio>
#include <map>
using namespace std;
int main(){
int n,a;
map<int,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;
}
解法4：set
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
int main() {
int n,x;
scanf("%d",&n);
set<int> 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);
multimap<char,int> mymap;
vector<char> seq; //记录每个字符出现的先顺序
for(int i = 0; i < strlen(str); ++i){ //str[i] != '\0'
if(find(seq.begin(),seq.end(),str[i]) == seq.end()){ //说明字符str[i]是第一次出现
seq.push_back(str[i]); //则加入seq中,即记录字符出现的顺序
}
mymap.insert({str[i],i});
}
vector<char>::iterator it; //it是字符出现顺序seq的迭代器
multimap<char,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,num+n,comp);
printf("%d %d\n",num[0].x,num[0].y);
return 0;
}
习题2：打印极值点下标 (难度：入门)
提交网址：https://www.acwing.com/problem/content/3440/
#include <cstdio>
int 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[i+1]) || (arr[i]<arr[i-1] && arr[i]<arr[i+1]) ){
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，运行次数为 1012>109
#include <cstdio>
int 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 <cstring>
char str[1000];
memset(str,0,sizeof(str));
3.输入
字符数组的输入可以省略&。因为数组名本身就是一个地址，不需要再取地址
scanf("%s",str);
4.输出
printf("%s\n",str);
5.字符数组转string：string 字符串名 = 字符数组名 ;
步骤：
①先声明字符数组
②字符数组操作，如输入
③转stringstring 字符串名 = 字符数组名 ;
④字符串操作
⑤输出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)，支持 +、=、==、<、<=、>、>=
②类似于 vector<char>，支持 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 对比 vector<char> 拓展了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(it=str.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,pos+1);
}
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(str1<str2) cout<<str1<<"<"<<str2<<endl;
else cout<<str1<<">="<<str2<<endl;
输出：a>=Z
ASCII码
原因：
①A的ASCII码为65，Z的ASCII码为90
②a的ASCII码为97，z的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){
cout<<"ch["<<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; //再转成string
2.输出
(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)C++：cin.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; //最后一个单词没有空格
map<char,int> mymap; //用 map<char,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[i+1] != ' '){
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; //字母出现次数的最大值
map<char,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){
//长度短的小数,补0
int 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.只有a
if(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.只有b
if(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,只有进位 carry=1
res.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;
}
例题3：W的密码 （难度：困难）
提交网址：https://www.acwing.com/problem/content/3408/
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void Partition(string str,vector<int> &vec1,vector<int> &vec2,vector<int> &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, vector<int> &vec, int offset){
vector<char> 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(k1==0 && k2==0 && k3==0) break;
cin >> str;
vector<int> 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的字母也要统计，所以本题不可用 map<char,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",'A'+i,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;
cout<<str[0];
//保持空白符不变
for(int i = 1; i < str.size(); i++){
if(str[i]==' ' || str[i]=='\t' || str[i]=='\r' || str[i]=='\n' ){
if(str[i+1]>='a' && str[i+1]<='z'){
str[i+1] -= 32; //空白符后的单词首字母大写
}
}
cout<<str[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(count==5){
count = 0;
continue; //不输出字符0,直接检查下一个字符
}
cout<<str[i];
count = 0;
}
}
cout << endl;
}
return 0;
}
解法2：replace()函数
# include <iostream>
using 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长度6
cout << s << '\n';
}
return 0;
}
习题5：大整数排序 （难度：简单）
提交网址：https://www.acwing.com/problem/content/3611/
思路：借用vector的自动排序功能，对sort函数添加上comp中按字符串长度升序排序，长度相等时按a<b字典序排序。关键在于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 a<b;
}
int main() {
int n;
cin >> n;
string s;
vector<string> vec;
for(int i = 0; i < n; i++){
cin >> s;
vec.push_back(s);
}
sort(vec.begin(),vec.end(),comp);
vector<string>::iterator it;
for(it = vec.begin(); it != vec.end(); ++it){
cout << *it << endl;
}
return 0;
}
习题6：单词替换 【字符串替换】(难度：中等)
提交网址：http://t.cn/Ai8Iycp6
字符串替换，用vector<string>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
//1.读入一整行
string s,a,b;
getline(cin,s);
cin >> a >> b;
//2.分割单词,存入vector
vector<string> 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.遍历输出
vector<string>::iterator it;
for(it = vec.begin(); it != vec.end(); ++it){
cout << *it << " ";
}
cout << endl;
return 0;
}
习题7：skew数 【进制转换】(难度：)
提交网址：http://t.cn/Ai8IALKI
习题8：复制、剪切、粘贴 (难度：)
提交网址：https://www.acwing.com/problem/content/3549/
