当前位置：网站首页>排序子序列与倒置字符串

排序子序列与倒置字符串

2022-07-18 00:34:00 【InfoQ】

️排序子序列️

题目详情

牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为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最少划分为多少段排序子序列

输入

6
1 2 3 2 2 1

输出

解题思路

基本思路：

模拟+遍历

解题思路：

非递增序列：一段不递增的数组，如

10 8 6 6 6 2 2

。非递减序列：一段不递减的数组，如

1 1 2 3 4 5 5 6 8

。

题目给我们一个大小为

n

的数组，我们需要去求这段子序列中非递增或非递减的

连续

子序列。

我们先不考虑

n=1

的情况，我们可以从数组第二个元素开始，求这个元素

arr[i]

与前面一个元素

arr[i-1]

的差值，不妨记这个差值为

dif

，子序列个数为

ans

，那么有三种情况：

，即表示后面的元素比前面的元素大，此时我们循环遍历，直到找到前面元素比后面元素大的情况或遍历完数组为止，那刚才遍历完的一段子序列就是一段非递减连续子序列，
ans
加
1
，验证后续序列。

，即表示后面的元素比前面的元素小，此时我们循环遍历，直到找到前面元素比后面元素小的情况或遍历完数组为止，那刚才遍历完的一段子序列就是一段非递增连续子序列，
ans
加
1
，验证后续序列。

，即表示两个元素是相等的，此时该序列后面为非递增的序列和为非递减的序列均可以，因此不用去处理，直接接着去验证后续序列即可。

但是，有一种情况忽略了，我们来看一个栗子:

1 2 1 2 1 2 1

，此时

n=7

。

经过上图分析，我们发现漏了数组末尾的一个单元素子序列，此时退出循环时

i=n

。

为了解决漏掉数组末尾单元素子序列的情况，我们可以判断退出循环时i的值是

n

还是

n+1

，如果满足

i-1==n-1

，即

i==n

，则表示我们漏掉了一个单元素的子序列，这种情况也包含数组只有一个元素的情况，即

n=1

的情况。

为什么说退出循环后，

i==n

就表示有漏数数组末尾的单元素序列呢？如果数组末尾没有单元素的子序列，则在内部循环找完整的序列的时候，退出内部循环的条件是

i<n

，那么此时

i==n

，最外层循环最后还会执行

i++

，因此退出外层循环时

i=n+1

，所以说如果没有漏子序列的情况退出循环,i会等于

n+1

，同理通过分析如果漏了数组末尾最后一个单序列，退出循环后，

i

会等于

n

，因此我们可以通过最后

i==n

来确定是否漏掉子序列，如果漏了，我们要将

ans++

。

通过以上分析，如果退出子序列查找循环后

i==n

，表示数组末尾的单元素子序列漏数了，需要将

ans

加

1

，这样也解决了

n=1

时的特殊情况。

源代码

import java.util.*;

public class Main {
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 
 int n = sc.nextInt();
 int[] arr = new int[n];
 for (int i = 0; i < n; i++) {
 arr[i] = sc.nextInt();
 }
 int ans = 0;
 int i = 0;
 for (i = 1; i < n; i++) {
 int dif = arr[i] - arr[i - 1];
 if (dif < 0) {
 while (i < n && arr[i] - arr[i - 1] <= 0) {
 i++;
 }
 ans++;
 } else if (dif > 0) {
 while (i < n && arr[i] - arr[i - 1] >= 0) {
 i++;
 }
 ans++;
 }
 }
 if (i == n) {
 ans++;
 }
 System.out.println(ans);
 }
}

总结

这道以本质上是一个模拟遍历题，最重要的就是能够分清楚情况，知道每种情况该怎么处理。

️倒置字符串️

题目详情

描述

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

输入描述：

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

输出描述：

依次输出倒置之后的字符串,以空格分割

示例1

输入：

I like beijing.

输出：

beijing. like I

解题思路

基本思路：

拆解+逆置

解题思路：

第一步，将字符串依据空格拆分，得到一个字符串数组。第二步，对这一个字符串数组进行逆置，即将字符串元素进行首尾交换。第三步，遍历逆置的字符串数组，在每个字符串元素后加上空格构造结果字符串，遍历完成后，最终的结果字符串就是按照题目意思逆置的字符串。

例如字符串

I am JMUer

，分析过程如下：

源代码

import java.util.*;

public class Main {
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 
 String ss = sc.nextLine();
 //将字符串依据空格，将字符串分开
 String[] spss = ss.split(&quot; &quot;);
 //首尾交换
 int left = 0;
 int rigth = spss.length - 1;
 while (left < rigth) {
 String tmp = spss[left];
 spss[left++] = spss[rigth];
 spss[rigth--] = tmp;
 }
 //加上原有的空格，将字符串数组转换成字符串
 StringBuilder ans = new StringBuilder();
 for (String x : spss) {
 ans.append(x);
 ans.append(&quot; &quot;);
 }
 System.out.println(ans);
 }
}