描述

题目描述

对字符串中的所有单词进行倒排。

输入描述：

输入一行以空格来分隔的句子

输出描述：

输出句子的逆序

示例

输入：
I am a student
输出：
student a am I

知识点：双指针、模拟

难度：⭐⭐⭐

题解

方法一：左右双指针

图解：

解题思路：

对于处理字符串问题，通过可以借助双指针思想，逆序处理每个字符

算法流程：

维护两个指针的，用于从右到左分别定位单词的首尾位置
从右往左找到第一个是单词字符的位置left，并赋值给 right 指针，作为单词的有边界
接着 left 指针再从当前位置开始，从右往左找到该单词的左边界
每次找到单词的左右边界后，截取字符串

Java 版本代码如下：

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int len = s.length();
        int left = len - 1, right = len - 1;
        StringBuilder res = new StringBuilder();
        while(left >= 0) {
            // 从右往左找到第一个是单词字符的位置left
            while(left >= 0 && !Character.isLetter(s.charAt(left))) {
                left--;
            }
            // 新单词的右边界
            right = left;
            // 从右往左找到该单词的左边界
            while(left >= 0 && Character.isLetter(s.charAt(left))) {
                left--;
            }
            res.append(s.substring(left + 1, right + 1) + " ");
        }
        System.out.println(res.toString());
    }
}

复杂度分析：

时间复杂度： $O (N)$ ，左指针 left 只需要从字符串尾字符遍历到首字符即可

空间复杂度： $O (N)$ ，需要额外空间用于保存结果字符串

方法二：字符匹配

解题思路：

明显的字符匹配问题，可以采用正则表达式

算法流程：

通过正则表达式切分字符串, 根据非字母进行切割为数组
采用的正则表达式筛选非字母进行切分：[^A-Za-z]，即筛选出不是 A-Z 和 a-z 的字符
逆序填充结果，最后处理掉首位空格

Java 版本代码如下：

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(solve(s));
    }
    
    public static String solve(String s) {
        // 正则表达式切分字符串, 根据非字母进行切割为数组
        String[] arr = s.split("[^A-Za-z]");
        StringBuilder res = new StringBuilder();
        // 逆序填充结果
        for(int i = arr.length - 1; i >= 0; i--) {
            res.append(arr[i] + " ");
        }
        // 去掉头尾空格
        return res.toString().trim();

    }
}

复杂度分析：

时间复杂度： $O (N)$ ，需要对字符串的每个字符进行遍历匹配

空间复杂度： $O (N)$ ，字符串数组空间用于保存切分后的字符串，还需要保存结果字符串

题解 | #丢棋子问题#

描述

题解

方法一：左右双指针

方法二：字符匹配