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

2024-05-24 20:36

本文主要是介绍GESP 四级冲刺训练营(1):字符串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

GESP 四级冲刺训练营:字符串

  • 一、基本常识
    • 1. 功能函数
    • 2. 注意事项
    • 3. 输入输出
      • 3.1 输入
      • 3.2 输出
  • 二、字符串算法
    • 1. 基础字符串
      • 1.1 回文字符串
      • 1.2 亲朋字符串
    • 2. 尺取法求解
      • 2.1 尺取法公式
      • 2.2 最长小写子串
    • 2.3 尺取法易错
  • 三、拓展习题
    • 1. 相似字符串
    • 2. 两数之和

一、基本常识

1. 功能函数

函数格式返回值功能
lengths.length()字符串的长度返回 s 的长度
finds1.find(s2, pos)第一个字符的下标或者 string::npos找到 s2s1 中第一个字符的下标
inserts1.insert(pos, s2)s1pos 下标位置前插入 s2
erases.erase(pos, len)删除 spos 下标位置开始往后的 len 个字符
replaces1.replace(pos, len, s2)替换 s1pos 下标位置开始往后的 len 个字符替换为 s2
tolowertolower(c)对应小写字符c 变为对应的小写字符
touppertoupper(c)对应大写字符c 变为对应的大写字符
substrs.substr(pos, len)截取的子字符串截取 s1pos 下标开始往后的 len 个字符为子字符串
reverses.reverse(it1, it2)sit1it2 进行翻转

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 100 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 s s 的第一个字符的 ASCII 值加第二个字符的 ASCII 值,得到第一个亲朋字符; s s s 的第二个字符加第三个字符得到第二个亲朋字符;依此类推。注意:亲朋字符串的最后一个字符由 s s s 的最后一个字符 ASCII 值加 s s s 的第一个字符的 ASCII 值。

输入格式

输入一行,一个长度大于等于 2 2 2,小于等于 100 100 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 0 0

输入描述

1 1 1 行,包含一个字符串 str

输出描述

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

样例1

输入

abcdeACzxc
1

输出

5
1

提示

当串 a 中连续包含串 b 的所有元素时,
a 是串 b 的父串;
b 是串 a 的子串。
例如 abcdefgcde 的子串。

参考答案

#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 A A B B B,如果 A A A 可以通过删除一个字符,插入一个字符,修改一个字符变成 B B B,那么我们说 A A A B B B 是相似的。
比如 apple \texttt{apple} apple 可以通过插入一个字符变成 applee \texttt{applee} applee,可以通过删除一个字符变成 appe \texttt{appe} appe,也可以通过修改一个字符变成 bpple \texttt{bpple} bpple。因此 apple \texttt{apple} apple applee \texttt{applee} applee appe \texttt{appe} appe bpple \texttt{bpple} bpple 都是相似的。但 applee \texttt{applee} applee 并不能 通过任意一个操作变成 bpple \texttt{bpple} bpple,因此它们并不相似。
特别地,两个完全相同的字符串也是相似的。
给定 T T T A , B A,B A,B,请你分别判断它们是否相似。

输入格式

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

输出格式

对组 A , B 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 ≤ T ≤ 100 1 \leq T \leq 100 1T100 A A A B B B 的长度不超过 50 50 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 N N 的整数数组 n u m s nums nums,以及一个目标值 t a r g e t target target。你需要在数组中找到两个数,使得它们的和等于目标值,并返回这两个数的索引(索引从 1 1 1 开始)。你可以假设只有一组答案。

输入格式

第一行包含两个整数 N N N t a r g e t target target,表示数组的长度和目标值。
第二行包含 N N N 个整数 n u m s 1 , n u m s 2 , . . . , n u m s N nums_1, nums_2, ..., nums_N nums1,nums2,...,numsN,表示数组的元素。

输出格式

输出两个整数 i i i j j j,表示两个数的索引( 1 ≤ i , j ≤ N 1 \leq i, j \leq N 1i,jN i ≠ j i \neq j i=j)。

样例 #1

样例输入 #1

4 9
2 7 11 15

样例输出 #1

1 2

提示

对于所有的测试数据,保证 2 ≤ N ≤ 1 0 4 , − 1 0 9 ≤ n u m s i ≤ 1 0 9 , − 1 0 9 ≤ t a r g e t ≤ 1 0 9 2 \leq N \leq 10^4,-10^9 \leq nums_i \leq 10^9,-10^9 \leq target \leq 10^9 2N104,109numsi109,109target109

参考答案

#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;
}

这篇关于GESP 四级冲刺训练营(1):字符串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/999468

相关文章

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字

Java对象和JSON字符串之间的转换方法(全网最清晰)

《Java对象和JSON字符串之间的转换方法(全网最清晰)》:本文主要介绍如何在Java中使用Jackson库将对象转换为JSON字符串,并提供了一个简单的工具类示例,该工具类支持基本的转换功能,... 目录前言1. 引入 Jackson 依赖2. 创建 jsON 工具类3. 使用示例转换 Java 对象为

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

Java中String字符串使用避坑指南

《Java中String字符串使用避坑指南》Java中的String字符串是我们日常编程中用得最多的类之一,看似简单的String使用,却隐藏着不少“坑”,如果不注意,可能会导致性能问题、意外的错误容... 目录8个避坑点如下:1. 字符串的不可变性:每次修改都创建新对象2. 使用 == 比较字符串,陷阱满

IDEA编译报错“java: 常量字符串过长”的原因及解决方法

《IDEA编译报错“java:常量字符串过长”的原因及解决方法》今天在开发过程中,由于尝试将一个文件的Base64字符串设置为常量,结果导致IDEA编译的时候出现了如下报错java:常量字符串过长,... 目录一、问题描述二、问题原因2.1 理论角度2.2 源码角度三、解决方案解决方案①:StringBui

C#从XmlDocument提取完整字符串的方法

《C#从XmlDocument提取完整字符串的方法》文章介绍了两种生成格式化XML字符串的方法,方法一使用`XmlDocument`的`OuterXml`属性,但输出的XML字符串不带格式,可读性差,... 方法1:通过XMLDocument的OuterXml属性,见XmlDocument类该方法获得的xm

JSON字符串转成java的Map对象详细步骤

《JSON字符串转成java的Map对象详细步骤》:本文主要介绍如何将JSON字符串转换为Java对象的步骤,包括定义Element类、使用Jackson库解析JSON和添加依赖,文中通过代码介绍... 目录步骤 1: 定义 Element 类步骤 2: 使用 Jackson 库解析 jsON步骤 3: 添

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

python修改字符串值的三种方法

《python修改字符串值的三种方法》本文主要介绍了python修改字符串值的三种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录第一种方法:第二种方法:第三种方法:在python中,字符串对象是不可变类型,所以我们没办法直接