GESP 四级冲刺训练营(1)：字符串

一、基本常识

1. 功能函数

2. 注意事项

• insert() 在下标之前做插入操作；
• tolower() 和 toupper() 只能传入字符，不能传入字符串；
• reverse() 传入的两个参数是迭代器，不是下标；
• reverse() 使用前需要导入 algorithm 头文件。

3. 输入输出

前情提要：请在所有操作之前确保导入 string 头文件。

3.1 输入

// 无空格输入
string s;
cin >> s;// 有空格输入
string s;
getline(cin, s);

3.2 输出

cout << s;

二、字符串算法

1. 基础字符串

1.1 回文字符串

题目描述

输入一个字符串，输出该字符串是否回文。回文是指顺读和倒读都一样的字符串。

输入格式

输入一行字符串，长度小于 $100$。

输出格式

如果字符串是回文，输出 yes；否则，输出 no。

样例 #1

样例输入 #1

abcdedcba

样例输出 #1

yes

参考答案

方法①：函数求解

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;string s;
string olds;int main()
{cin >> s;olds = s;reverse(s.begin(), s.end());if (olds == s){cout << "yes";}else{cout << "no";}return 0;
}

方法②：逻辑求解

#include <iostream>
#include <string>
using namespace std;string s;
int len;int main()
{cin >> s;len = s.length();for (int i = 0; i <= len/2; i++){if (s[i] != s[len-i-1]){cout << "no";return 0;}}cout << "yes";return 0;
}

1.2 亲朋字符串

题目描述

亲朋字符串定义如下：给定字符串 $s$ 的第一个字符的 ASCII 值加第二个字符的 ASCII 值，得到第一个亲朋字符；$s$ 的第二个字符加第三个字符得到第二个亲朋字符；依此类推。注意：亲朋字符串的最后一个字符由 $s$ 的最后一个字符 ASCII 值加 $s$ 的第一个字符的 ASCII 值。

输入格式

输入一行，一个长度大于等于 $2$，小于等于 $100$ 的字符串。

输出格式

输出一行，为变换后的亲朋字符串。输入保证变换后的字符串只有一行。

样例 #1

样例输入 #1

1234

样例输出 #1

cege

参考答案

#include <iostream>
#include <string>
using namespace std;string s;
int len;
string news;int main()
{cin >> s;len = s.length();for (int i = 0; i < len; i++){news += s[i]+s[(i+1)%len];}cout << news;return 0;
}

2. 尺取法求解

2.1 尺取法公式

尺取法一般的定义是：
l: 左指针
r: 右指针
s: 字符串
n: 字符串长度

while (l < n)
{if ((s[r]...) && r < n){r++;}else{ans = max(l-r or l-r-1);l = r+1;r++;}
}

2.2 最长小写子串

题目描述

给定一个由若干大写小写字符组成的字符串 str，现在请你求出 str 中最长的小写子串的长度。如果没有，则输出 $0$ 。

输入描述

$1$ 行，包含一个字符串 str。

输出描述

$1$ 行，包含最长小写子串的长度。

样例1

输入

abcdeACzxc
1

输出

5
1

提示

当串 a 中连续包含串 b 的所有元素时，
串 a 是串 b 的父串；
串 b 是串 a 的子串。
例如 abcdefg 是 cde 的子串。

参考答案

#include <iostream>
#include <string>
using namespace std;string s;
int l, r;
int len;
int ans;int main()
{cin >> s;len = s.length();while (l < len){if ((s[r] >= 'a' && s[r] <= 'z') && r < len){r++;}else{ans = max(ans, r-l);l = r + 1;r++;}}cout << ans;return 0;
}

2.3 尺取法易错

• 注意问题的起始位置和结束位置的解决范围
• 更新结果到底是 r-l 还是 r-l-1 要分清楚
• 需要特别处理边界条件
• 要及时更新指针状态

三、拓展习题

1. 相似字符串

题目描述

对于两个字符串 $A$ 和 $B$，如果 $A$ 可以通过删除一个字符，或插入一个字符，或修改一个字符变成 $B$，那么我们说 $A$ 和 $B$ 是相似的。
比如 $\text{apple}$ 可以通过插入一个字符变成 $\text{applee}$，可以通过删除一个字符变成 $\text{appe}$，也可以通过修改一个字符变成 $\text{bpple}$。因此 $\text{apple}$ 和 $\text{applee}$、$\text{appe}$、$\text{bpple}$ 都是相似的。但 $\text{applee}$ 并不能 通过任意一个操作变成 $\text{bpple}$，因此它们并不相似。
特别地，两个完全相同的字符串也是相似的。
给定 $T$ 组 $A,B$，请你分别判断它们是否相似。

输入格式

第一行一个正整数 $T$。
接下来 $T$ 行，每行两个用空格隔开的字符串 $A$ 和 $B$。

输出格式

对组 $A,B$，如果他们相似，输出 similar，否则输出 not similar。

样例 #1

样例输入 #1

5
apple applee
apple appe
apple bpple
applee bpple
apple apple

样例输出 #1

similar
similar
similar
not similar
similar

提示

对全部的测试数据，保证 $1\le T\le 100$，$A$ 和 $B$ 的长度不超过 $50$，仅含小写字母。

参考答案

#include <iostream>
#include <string>
#include <cmath>
using namespace std;int T;
string A, B;bool isSimilar(string A, string B)
{// 两者完全相同if (A == B) return true;// 初始化int m = A.length();int n = B.length();int cnt = 0; // 记录变化字符数量int l = 0, r = 0; // 记录插入、删除的位置// 长度差大于1if (abs(m-n) > 1) return false;// 两者长度相等，判断是否只修改了一个字符else if (m - n == 0){for (int i = 0; i < m; i++){if (A[i] != B[i]) cnt++;if (cnt > 1) return false;}}// 两者长度相差1else{// B比A多一个字符，判断是否插入一个字符if (m - n == -1){int i = 0, j = 0;while (i < m){if (A[i] != B[j]){// 记录插入的位置l = i;r = j;// 直接比较后面的字符是否相等while (i < m && j < n){if (A[i] != B[j+1]) return false;i++;j++;}// 如果后面的字符都相等，则必须是A的剩余字符都相等if (i < m) return false;break;}else{i++;j++;}}}// A比B多一个字符，判断是否删除一个字符else{int i = 0, j = 0;while (i < m){if (A[i] != B[j]){// 记录删除的位置l = j;r = i;// 直接比较后面的字符是否相等while (i < m && j < n){if (A[i+1] != B[j]) return false;i++;j++;}// 如果后面的字符都相等，则必须是B的剩余字符都相等if (j < n) return false;break;}else{i++;j++;}}}}return true;
}int main()
{cin >> T;while (T--){cin >> A >> B;cout << (isSimilar(A, B) ? "similar\n" : "not similar\n");}return 0;
}

2. 两数之和

题目描述

给定一个长度为 $N$ 的整数数组 $nums$，以及一个目标值 $target$。你需要在数组中找到两个数，使得它们的和等于目标值，并返回这两个数的索引（索引从 $1$ 开始）。你可以假设只有一组答案。

输入格式

第一行包含两个整数 $N$ 和 $target$，表示数组的长度和目标值。
第二行包含 $N$ 个整数 $num{s}_1,num{s}_2,...,num{s}_N$，表示数组的元素。

输出格式

输出两个整数 $i$ 和 $j$，表示两个数的索引（$1\le i,j\le N$，$i\ne j$）。

样例 #1

样例输入 #1

4 9
2 7 11 15

样例输出 #1

1 2

提示

对于所有的测试数据，保证 $2\le N\le 10^4,-10^9\le num{s}_i\le 10^9,-10^9\le target\le 10^9$。

参考答案

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;vector<int> findTwoSum(vector<int>& nums, int target)
{int l = 0;int r = nums.size() - 1;while (left < right){int sum = nums[l] + nums[r];if (sum == target){return {l+1, r+1};}else if (sum < target){l++;}else{r--;}}return {};
}int main()
{int N, target;cin >> N >> target;vector<int> nums(N);for (int i = 0; i < N; i++){cin >> nums[i];}sort(nums.begin(), nums.end());vector<int> result = findTwoSum(nums, target);cout << result[0] << " " << result[1];   return 0;
}