【双指针】【打卡73天】《剑指Offer》2刷:JZ73 翻转单词序列

1、题目描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

数据范围：
进阶：空间复杂度  ，时间复杂度  ，保证没有只包含空格的字符串。

 2、算法分析

知识补充：

split("")：字符串的分割，以分隔符作为分割点，分割字符串的每一个以分隔符分割的元素，返回的是一个String[]类似的数组。

 trim()：trim() 方法用于删除字符串的头尾空白符。

本题共有2种解题方法：

第一种：

        直接字符串的分割，以“ ”空格进行分割，split(" ")进行分割，返回的是String[]数组。

倒叙存储数组中的每一个元素，使用StringBuilder返回结果。

第二种：

        先对整体的字符串进行翻转，然后对每一个单词进行翻转。

具体看代码：

3、代码实现

第一种方法：使用split()方法分割元素

public class Solution {
    public String ReverseSentence(String str) {
        if(str == null || str.length() == 0){
            return str;
        }
        StringBuilder strs = new StringBuilder();
        // 以" "分割每一个数组元素
        String[] a = str.split(" ");
        for(int i = a.length-1;i >= 0;i--){
            strs.append(a[i] + " ");
        }
        // 去掉字符串开头和结尾的空格
        return strs.toString().trim();
    }
}

第二种方法：先对整体进行翻转，然后再对每一个单词翻转。

public class Solution {
    public String ReverseSentence(String str) {
       if(str == null || str.length() == 0){
          return str;
        }
        // 将字符串转换为字符串数组
        char[] arr = str.toCharArray();
        //先对整个语句部分全部反转一次
        reverse(arr,0,arr.length - 1);
        // 定义两个标记类似指针
        //定义指向单词的第一个字母，这个是初始值，不用管它
        int start = 0;
        //指向单词的最后一个字母，这个是初始值，不用管它
        int end = 0;
        while(start < arr.length){
          // 如果开始的是指向的空格，就继续往下走，因为目的是反转单词，空格不需要反转
          if(arr[start] == ' '){
            start++;
            end++;
            // 指针开始的部分指向的是指向的是单词，因为单词中间的字母是没有空格的，现在看单词的结尾
          }else if(end == arr.length || arr[end] == ' '){
            //对于结尾end只有两种情况，一种是指向空格，另一种就是指向单词的末尾为空格的位置
            //start和end 在start在单词的首字母，end在单词的最后一个字母后的第一个空格
            //接下来反转当前单词
            reverse(arr,start,end - 1);
            // 移动指针坐标
            end++;
            start = end;
          }else{
            // 以上两个条件都不符合的时候，说明当前单词还没到结尾，end指针继续往后移动
            end++;
          }
        }
           return String.valueOf(arr);
    }
    
    // 反转某个单词，开始位置和结束位置
    
    public void reverse(char[] arr,int start,int end){
        while(start < end){
            char temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }
}