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

相关文章

两个月冲刺软考——访问位与修改位的题型(淘汰哪一页);内聚的类型;关于码制的知识点;地址映射的相关内容

1.访问位与修改位的题型(淘汰哪一页) 访问位:为1时表示在内存期间被访问过,为0时表示未被访问;修改位:为1时表示该页面自从被装入内存后被修改过,为0时表示未修改过。 置换页面时,最先置换访问位和修改位为00的,其次是01(没被访问但被修改过)的,之后是10(被访问了但没被修改过),最后是11。 2.内聚的类型 功能内聚:完成一个单一功能,各个部分协同工作,缺一不可。 顺序内聚:

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

C和指针:字符串

字符串、字符和字节 字符串基础 字符串就是一串零个或多个字符,并且以一个位模式为全0的NUL字节结尾。 字符串长度就是字符串中字符数。 size_t strlen( char const *string ); string为指针常量(const修饰string),指向的string是常量不能修改。size_t是无符号数,定义在stddef.h。 #include <stddef.h>

PHP字符串全排列

方法一: $str = 'abc';$a =str_split($str);perm($a, 0, count($a)-1);function perm(&$ar, $k, $m) {if($k == $m){ echo join('',$ar), PHP_EOL;}else {for($i=$k; $i<=$m; $i++) {swap($ar[$k], $ar[$i]);perm($ar

PHP7扩展开发之字符串处理

前言 这次,我们来看看字符串在PHP扩展里面如何处理。 示例代码如下: <?phpfunction str_concat($prefix, $string) {$len = strlen($prefix);$substr = substr($string, 0, $len);if ($substr != $prefix) {return $prefix." ".$string;} else

十一、C语言:字符串函数

目录 一、strlen 二、strcpy 三、strcat  四、strcmp 五、strstr 六、strtok 七、strerror 一、strlen 注意:strlen()函数的返回值是size_t,两个size_t相减仍为无符号数 int main(){char arr[10] = "abc";char brr[10] = "abc123";if (strl

代码训练营 Day26 | 47.排序II | 51. N-皇后 |

47.排序II 1.跟46题一样只不过加一个树层去重 class Solution(object):def backtracking(self,nums,path,result,used):# recursion stopif len(path) == len(nums):# collect our setresult.append(path[:])return for i in range(

NC 把数字翻译成字符串

系列文章目录 文章目录 系列文章目录前言 前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去分享给你的码吧。 描述 有一种将字母编码成数字的方式:‘a’->1, ‘b->2’, … , ‘z->26’。 现在给一串数字,返回有多少种可能的译码结果 import java.u

C语言进阶【1】--字符函数和字符串函数【1】

本章概述 字符分类函数字符转换函数strlen的使用和模拟实现strcpy的使用和模拟实现strcat的使用和模拟实现strcmp的使用和模拟实现彩蛋时刻!!! 字符分类函数 字符: 这个概念,我们在以前的文章中讲过了。我们键盘输入的信息都是字符。字符大体可以分为两类——单个字符,字符串。而单个字符又可以进行分类——字母字符,数字字符,特殊字符和不可见字符。进行思维图展示: 在日

nyoj 685 查找字符串

当初一开始没做出来。 后来,学习过一段时间之后,在返回来做这道题,忽然发现,map类容器可以做。 PS:需要注意的是:此题如果用c++的输入输出的话,会超时。 O(time):gets()<  scanf() < cin。   附上代码: #include<stdio.h>#include<map>#include<string>#include<string.h>usin