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

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

二、day02

1.倒置字符串

题目描述：

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

输入描述：

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

示例1：

输入：

I like beijing.
1

输出：

beijing. like I
1

基本思想：

1.整体逆置

2.每个单词进行逆置

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

代码实现：

#include 
#include 
using namespace std;

int main() {
     string s;
     getline(cin,s);

     //整体逆置字符串.gnijieb ekil I
     reverse(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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

    //遍历一次数组a
    int 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;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55