排序子序列与倒置字符串

2022 年 7 月 17 日
本文字数：2303 字
阅读完需：约 8 分钟

⭐️排序子序列⭐️

🔐题目详情

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

复制代码

输入

61 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，那么有三种情况：

$d i f > 0$ ，即表示后面的元素比前面的元素大，此时我们循环遍历，直到找到前面元素比后面元素大的情况或遍历完数组为止，那刚才遍历完的一段子序列就是一段非递减连续子序列，ans加1，验证后续序列。
$d i f < 0$ ，即表示后面的元素比前面的元素小，此时我们循环遍历，直到找到前面元素比后面元素小的情况或遍历完数组为止，那刚才遍历完的一段子序列就是一段非递增连续子序列，ans加1，验证后续序列。
$d i f = = 0$ ，即表示两个元素是相等的，此时该序列后面为非递增的序列和为非递减的序列均可以，因此不用去处理，直接接着去验证后续序列即可。

但是，有一种情况忽略了，我们来看一个栗子: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(" ");        //首尾交换        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(" ");        }        System.out.println(ans);    }}

复制代码

🌱总结

本质上就是字符串逆置问题，使用首尾交换即可解决。类似题：344. 反转字符串

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/679fc564d27d2760a236d1204】。文章转载请联系作者。

未见花闻

关注

坚持+努力=诗+远方 2021.11.15 加入

一位热爱技术热爱分享的大学生！

发布

暂无评论

创作场景

排序子序列与倒置字符串

⭐️排序子序列⭐️

🔐题目详情

💡解题思路

🔑源代码

🌱总结

⭐️倒置字符串⭐️

🔐题目详情

💡解题思路

🔑源代码

🌱总结

未见花闻

评论