【笔试强训day02】倒置字符串排序子序列

news/2024/10/18 6:07:36/

在这里插入图片描述

👻内容专栏：笔试强训集锦
🐨本文概括：C++笔试强训day02。
🐼本文作者：阿四啊
🐸发布时间：2023.10.1

二、day02

1.倒置字符串

题目描述：

将一句话的单词进行倒置，标点不倒置。比如 I like beijing. 经过函数后变为：beijing. like I

输入描述：

每个测试输入包含1个测试用例： I like beijing. 输入用例长度不超过100

示例1：

输入：

I like beijing.

输出：

beijing. like I

基本思想：

1.整体逆置

2.每个单词进行逆置

注意：遇到空格或者 ‘\0’ 结束，进行辨别一个单词，注意分界，到 ‘\0’ 之后便不能再进行逆置

代码实现：

#include <iostream>
#include <algorithm>
using namespace std;int main() {string s;getline(cin,s);//整体逆置字符串.gnijieb ekil Ireverse(s.begin(),s.end());//对每个单词进行逆置auto end = s.begin();while(end != s.end()){auto start = end;//寻找空格或者字符串的end位置('\0')while(end != s.end() && *end != ' ') end++;reverse(start, end);//end指向空格后往后跳一个，如果end指向为'\0'，则不需要++if(*end == ' ') end++;}cout << s;return 0;
}

2.排序子序列

题目描述：

牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个数组分为几段排序子序列.
如样例所示,牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列,至少需要划分为2个排序子序列,所以输出2

输入描述：

输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)
第二行包括n个整数A_i(1 ≤ A_i ≤ 10^9),表示数组A的每个数字。

输出描述：

输出一个整数表示牛牛可以将A最少划分为多少段排序子序列。

基本思想：

这一题关键得弄清楚非递增与非递减子序列

递增子序列：1 2 3 4 5

递减子序列：9 8 7 6 5

非递增子序列：9 7 6 6 5 3 2 1

非递减子序列：1 2 3 3 4 5 8 8

画图演示：

在这里插入图片描述

注意：i在子序列中遍历时，必须得小于数组的大小n，否则可能会出现越界情况。另外，这样也不能保证i + 1 < n，即访问a[i + 1]时也会出现越界访问，此时我们可以在开辟数组时，根据给出的数组大小n，我们多开辟一个字节的空间即n + 1，将最后一个元素值改为0

代码实现：

#include <iostream>
#include <vector>
using namespace std;int main() {int n;//输入整数cin >> n;vector<int> a;a.resize(n + 1);a[n] = 0;//输入数组a中元素for(int i = 0;i < n;i++){cin >> a[i];}//遍历一次数组aint i = 0;int count = 0; //计算一共需要划分多少段子序列while(i < n){//可能即将进入非递减子序列if(a[i] < a[i + 1]){//注意i的值必须小于n，否则会出现越界情况while(i < n && a[i] < a[i + 1]){i++;}//走完一组非递减子序列count++count++;}else if(a[i] == a[i + 1]){i++; }else{//注意i的值必须小于n，否则会出现越界情况while(i < n && a[i] > a[i + 1]){i++;}//走完一组非递增子序列count++count++;}//i++往后遍历i++;}cout << count;}