[programming training 2] sorting subsequence + inverted string

1. Sort subsequence -> link

【 title 】：

This problem requires to solve the sorting subsequence , The sorting subsequence is non increasing or non decreasing , Many students are in this non incremental 、 The non decreasing problem is very tangled ,
Be careful ： Non decreasing is a[i]<=a[i+1], Decreasing is a[i]>a[i+1], Non incremental is a[i]>=a[i+1], Increment is a[i]<a[i+1].

【 Their thinking 】：

1. Compare the whole array in turn
2. a[i+1]>a[i] , Then enter the non decreasing sequence to judge , Until the next value is not greater than or equal count++, Then proceed to the next position
   The judgment of the
3. a[i+1]<a[i], Then enter the non increasing sequence to judge , Until the next value is not less than or equal count++, Then proceed to the next position
   The judgment of the
4. a[i+1] == a[i] No operation ,++i Next position traversal , Because equality can belong to a non increasing sequence , It can also belong to non decreasing order
   Column .

【 Pay attention to 】：

Start of this topic a[i+1] And a[i] Compare , To avoid crossing the border , Array is defined as n+1 individual , At the same time a[n] = 0;
a[n] = 0 The impact , We divided the discussion into three situations ：

1. If the a[n-1] The last set of is a non decreasing sequence , When i= =n-1,a[i] >a[i+1], Because the previous numbers are greater than 0 Of , This input condition has been explained ( Go to the title and enter the condition description ), The cycle inside ends ,i++,count++,i==n, The outer cycle ends .
2. If the a[n-1] The last set of is a non increasing sequence , When i= =n-1,a[i] >a[i+1], Because the previous numbers are greater than 0 Of , This input bar It has been explained in ( Go to the title and enter the condition description ), Cycle again ,i++, i== n, The cycle inside ends ,i++,
   count++,i==n+1, The outer cycle ends .
3. The third case 1 2 1 2 1 The last number is a separate case , Fill in the back 0, The sequence becomes 1 2 1 2 1 0, When you finish the comprehensive sequence i==n-1 when ,a[i] > a[i+1], Enter and judge a non increasing sequence ,count++,i++, The loop ends .

In other words, add one more at the last position of the array 0, Will not affect the second 1、2 Judgment of the situation , Mainly to help the third party 3 Correct judgment of the situation .

Code implementation ：

#include<iostream>
#include<vector>
using namespace std;
//  The test cases of this topic are incomplete , At least the following two groups of test cases should be added 
//  Input ：
// 4
// 1 3 2 3
//  Output ：2
//  Input ：
// 6
// 3 2 1 1 2 3
//  Output ：2
int main()
{
    
int n;
cin >> n;
//  Notice that an extra value is given here , It's a comparison of dealing with cross-border situations , For details, please refer to the above problem-solving ideas 
vector<int> a;
a.resize(n + 1);// There's a pit here , This question is out of bounds, but I can't find it , to n, And don't write a[n] = 0; No mistake. , But it's best to write 
a[n] = 0;
// Read in array 
int i = 0;
for (i = 0; i < n; ++i)
cin >> a[i];
i = 0;
int count = 0;
while (i < n)
{
    
//  Non decreasing subsequence 
if (a[i] < a[i + 1])
{
    
while (i < n && a[i] <= a[i + 1])
i++;
count++;
i++;
} 
else if (a[i] == a[i + 1])
{
    
i++;
} else //  Non increasing subsequence 
{
    
while (i < n && a[i] >= a[i + 1])
i++;
count++;
i++;
}
} 
cout << count << endl;
return 0;

2. Inverted string -> link

【 title 】：
The meaning of this question is very simple , Is to exchange words before and after a string , Reverse by word .

【 Their thinking 1】：

First invert the whole string , And then traverse the string , Find each word , Reverse word . Here we use stl In the algorithm reverse, So here we use iterators to traverse string

Code implementation ：

include <iostream>
include <string>
include <algorithm>
using namespace std;
int main()
{
    
string s;
//  Pay attention to the use of getline,cin>>s Receiving ends when a space is encountered 
getline(cin, s);
//  Flip the whole sentence 
reverse(s.begin(), s.end());
//  Flip Words 
auto start = s.begin();
while (start != s.end())
{
    
auto end = start;
while (end != s.end() && *end != ' ')
end++;
reverse(start, end);
if (end != s.end())
start = end + 1;
else{
    
start = end;
} 
cout << s << endl;
return 0;
}