C++每日一练——排序子序列&&各种翻转字符串

文章目录

🍁排序子序列

🍑题目要求

牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是

非递增

或者

非递减

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

🍑思路分析

首先子序列是非递增或是非递减的：
递增：1 2 3 4 5 6
递减：6 5 4 3 2 1

非递增

：6 5 5 4 3 (前后两数可能相等）

非递减

：1 2 2 3 4 （前后两数可能相等）

//对数组a而言，就可以分为一下三种情况：if(a[i]> a[i+1])//即将进入非递增序列if(a[i]== a[i+1]//相等时if(a[i]< a[i+1])//即将进入非递减序列

首先定义一个vector存放这些子序列，再定义一个计数器count初始化为0，遍历vector通过以上三种情况可以判断count最后为多大

#include<iostream>#include<vector>usingnamespace std;intmain(){int n;
    cin >> n;
    vector<int> v;//开n个空间
    v.resize(n);for(int i =0; i < n; i++){
        cin >> v[i];}int i =0, count =0;while(i < n){//非递减子序列if(v[i]< v[i +1]){//i始终小于nwhile(i < n && v[i]<= v[i +1]){++i;}++i;++count;}//相等时count不用++elseif(v[i]== v[i +1]){++i;}//非递增子序列else{while(i < n && v[i]>= v[i +1]){++i;}++i;++count;}}
    cout << count << endl;return0;}

但当我们运行时发现报错了，显示访问vector越界了

🍑C++代码

#include<iostream>#include<vector>usingnamespace std;intmain(){int n;
    cin >> n;
    vector<int> v;
    v.resize(n+1);//默认为0for(int i =0; i < n; i++){
        cin >> v[i];}int i =0, count =0;while(i < n){//非递减子序列if(v[i]< v[i +1]){while(i < n && v[i]<= v[i +1]){++i;}++i;++count;}elseif(v[i]== v[i +1]){++i;}//非递增子序列else{while(i < n && v[i]>= v[i +1]){++i;}++i;++count;}}
    cout << count << endl;return0;}

🍁倒置字符串

🍑题目要求

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

🍑思路分析

直接整体逆序，然后逐个单词逆序

逐个单词逆序时，首先需要一个first和一个last区间定位一个单词，last寻找空格或’\0’，定位一个单词结尾

🍑C++代码

#include<iostream>#include<string>#include<algorithm>usingnamespace std;intmain(){    
    string s;getline(cin, s);//先整体逆序reverse(s.begin(), s.end());
    string::iterator first = s.begin();while(first != s.end()){
        string::iterator last = first;//寻找空格while(last != s.end()&&*last !=' '){++last;}//逐个单词逆序reverse(first, last);//判断循环终止原因if(last == s.end())
            first = last;elseif(*last ==' '){
            first = last +1;}}
    cout << s << endl;return0;}

🍁翻转字符串中的单词

Leetcode第557题也和上面的类似，单纯的单词的逆序

classSolution{public:
    string reverseWords(string s){
        string::iterator first = s.begin();while(first != s.end()){
           string::iterator last=first;while(last != s.end()&&*last !=' '){++last;}reverse(first, last);if(last == s.end()){
                first =last;}elseif(*last ==' '){
                first = last +1;}}return s;}};

🍁反转字符串

LeetCode第541题
实际上就是每隔k个字符翻转k隔字符，然后不足k个的全部翻转

classSolution{public:
    string reverseStr(string s,int k){
        size_t size=s.size();
        string::iterator it=s.begin();for(size_t i=0; i<size; i+=2*k){if(i+k <=size){reverse(it+i, it+k+i);}//不足k个的剩余部分全部翻转else{reverse(it+i, s.end());}}return s;}};

以上就是今天的题目了，希望我的文章对你有所帮助，欢迎👍点赞 ，📝评论，🌟关注，⭐️收藏