⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【排序子序列】和【倒置字符串】，展示语言java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创！
📆首发时间：🌴2022年7月31日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《数据结构与算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

⭐️排序子序列⭐️

🔐题目详情

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

输出

2

💡解题思路

基本思路： 模拟+遍历

解题思路：
非递增序列：一段不递增的数组，如 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，那么有三种情况：

• $dif > 0$，即表示后面的元素比前面的元素大，此时我们循环遍历，直到找到前面元素比后面元素大的情况或遍历完数组为止，那刚才遍历完的一段子序列就是一段非递减连续子序列，ans加1，验证后续序列。
• $dif < 0$，即表示后面的元素比前面的元素小，此时我们循环遍历，直到找到前面元素比后面元素小的情况或遍历完数组为止，那刚才遍历完的一段子序列就是一段非递增连续子序列，ans加1，验证后续序列。
• $dif == 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. 反转字符串