笔试强训2

题目1：

倒置字符串_牛客题霸_牛客网

 

 我们先写出代码：

#include
#include
using namespace std;
int main()
{
	string s;
	getline(cin, s);
	reverse(s.begin(), s.end());
	auto start = s.begin();
	while (start != s.end())
	{
		auto end = start;
		while (end != s.end() && *end != ' ')
		{
			end++;
		}
		if (end != s.end())
		{
			reverse(start, end);
			start = end + 1;
		}
		else
		{
			reverse(start, end);
			start = end;
		}
	}
	cout << s << endl;
	return 0;
}

我们先说思路：我们可以先将整个的字符串进行倒置，然后再把每一个单词进行导致，实现我们的要求

我们先创建一个string对象，使用getline函数，目的是防止让‘ ’变为有效字符，而不是多组输入的标志，然后我们使用reserve函数，对s.begin()到s.end()进行逆置，逆置后的图像是这样的：

接下来，我们的思路是这样的：我们设置两个指针，第一个指针start指向对象的第一个字符的位置，第二个指针end也指向第一个字符的位置，然后让第二个指针end遍历对象来进行判断，假如对应的数组元素为' '时，我们先调用reverse函数把start和end之间的单词进行交换，然后把end+1赋值给start，继续遍历下一个单词。

注意：这个循环有两处停滞点，第一处是当end遭遇\0时，第二处是当end到s.end()位置时，对于第一个，我们先调用reverse函数进行逆置，然后把end+1赋给start即可。对于第二个，我们先调用reverse函数进行逆置，然后把end赋给start即可。 

我们的循环的结束条件是当start和s.end()指向同一个位置时，循环结束。

#include
#include
#include
using namespace std;
int main()
{
	string s;
	getline(cin, s);
	reverse(s.begin(), s.end());
	auto start = s.begin();
	auto end = start;
	while (start != s.end())
	{
		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;
}

题目2：

#include
#include
#include
#include
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int> a;
	a.resize(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	int i = 0;
	int count = 0;
	while (i < n)
	{
		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
		{
			while (i < n&&a[i] >= a[i + 1])
			{
				i++;
			}
			count++;
			i++;
		}
	}
	cout << count << endl;
}

 我们对题目进行分析：我们要先理解非递增和非递减的意义：非递增包括递减和相等，转换为代码的形式就是这样：a[i]>=a[i+1]

 我们首先要创建变量n，输入n值，这个n就是我们数组元素的个数，然后我们创建n个空间的数组a，使用resize函数，开辟n个空间供我们数组使用。

接下来，我们使用for循环，输入元素到数组中，接下来，我们就开始查找排序子序列的个数。

我们的思路如下：

 i是数组首元素的下标，让i和i+1的下标对应的元素进行比较，a[i]<=a[i+1]，表示我们接下来的序列是非递减序列，我们继续遍历，2和3也满足非递减序列，继续遍历，a[i]>a[i+1]，不满足非递减序列，表示接下来的序列是非递增序列，我们之前的非递减序列已经结束，我们设置count来继续序列的次数，这时候count+1，我们继续往后遍历，2与2满足非递增序列，我们继续遍历，2和1满足非递增序列，这时候，我们已经遍历完全部的数组元素，我们再让count++，返回count即可。

我们来结合代码分析：

 i是数组元素的下标，所以不能越界，让其小于n

当i下标对应的元素小于i+1下标对应的元素，表示我们是非递减序列，我们进入非递减序列的处理方法，非递减序列可能是很长的序列，所以我们需要使用while循环，首先为了防止while循环内部越界，我们首先让i

当while循环结束时，表示我们不再满足递减序列或者遍历数组完毕，我们让count++，i++

 当i对应的元素和i+1对应的元素相等时，同时满足非递减序列和非递增序列，我们不需要进行处理，只需要让i++即可。

 当a[i]>a[i+1]，表示我们满足非递增序列，非递增序列可能会很长，所以我们需要while循环来继续宁遍历，为了防止循环内越界，我们要让i

然后我们打印数组即可。

但是我们这里依旧有越界的存在：

当i=n-1时，a[i+1]就会造成越界访问吗，针对这个问题，我们可以这样处理：

 我们可以多申请一个空间，这样我们进行访问就不会造成越界访问。