笔试强训每日一题(二)

排序子序列

题目链接

题目描述

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

首先我们要理解非递减和非递增：

非递减就是a[i]<=a[i+1]，递减就是a[i]>a[i+1]

非递增就是a[i]>=a[i+1]，递增就是a[i]<a[i+1]

题目解析

1. 本题依次比较整个数组
2. a[i+1]>a[i]，则进入非递减序列判断，直到遍历到下一个值不大于等于为止count++，然后进行下一位置的判断
3. a[i+1]<a[i]，则进入非递增序列判断，直到遍历到下一个值不小于等于为止count++，然后进行下一位置的判断
4. a[i+1] == a[i]不进行操作，++i进行下一位置遍历，因为相等既可以属于非递增序列，也可以属于非递减序列。
5. 本题需要注意的是开始比较a[i+1]与a[i]进行比较，为了避免越界，数组定义为n+1个，同时给a[n] = 0

解题代码

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> a;
    a.resize(n+1);
    for(int i = 0;i<a.size()-1;i++)
    {
        cin>>a[i];
    }
    a[n] = 0;
    //数组当中已经存在数字
    // 1 2 3 3 4 5 
    int i = 0;
    int count = 0;
    while(i<n)
    {
        if(a[i] < a[i+1])
        {
            //进入非递减序列
            //注意i的值要注意不能一直加
            //当序列是1 2 3时，这里会有越界，但是牛客网的测试用例有问题，这个代码竟然能过
            while(i < n && a[i] <= a[i+1])
            {
                //在非递减序列中
            	i++; 
            }
            //这里出来说明一个非递减序列，count++
            count++;
            i++;
        }
        else if(a[i] == a[i+1])
        {
            i++;
        }
        else
        {
            //进入非递增序列
            //注意i的值要注意不能一直加
            while(i < n && a[i] >= a[i+1])
            {
                //在非递增序列中
            	i++; 
            }
            //这里出来说明一个非递增序列，count++
            count++;
            i++;
        }
    }
    cout<< count <<endl;
}

倒置字符串

题目链接

题目描述

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

输入描述:
每个测试输入包含1个测试用例: I like beijing.输入用例长度不超过100
输出描述:
依次输出倒置之后的字符串，以空格分割

题目解析

1. 空格是单词的结束标志
2. 遇到空格逆置单词：i ekil .gnijieb
3. 逆置全部：beijing. like i

解题代码

#include<string>
#include<iostream>
using namespace std;
//将一句话的单词进行倒置，标点不倒置
//空格是单词的标志
void reverse(string &str,int begin,int end)
{
    while(begin<end)
    {
        char temp = str[begin];
        str[begin] = str[end];
        str[end] = temp;
        begin++;
        end--;
    }
}
void reverse_word(string &str)
{
    //1.遇到空格逆置单词
    //i ekil .gnijieb
    //2.逆置全部
    //beijing. like i
    int i = 0;//记录逆置单词的起始
    int j = 0;//找单词的结尾
    for(int j = 0;j <= str.size();j++)
    {
        if(str[j] == ' '||str[j] == '\0')
        {
            reverse(str,i,j-1);
            i = j + 1;
        }
    }
    reverse(str,0,str.size()-1);
}
int main()
{
    string str;
    getline(cin,str);
    //1.遇到空格逆置单词
    //i ekil .gnijieb
    //2.逆置全部
    //beijing. like i
    reverse_word(str);
   	cout<<str<<endl;
}