卷进大厂系列之LeetCode刷题笔记：颠倒字符串里的单词（中等）

学算法，刷力扣，加油卷，进大厂！

题目描述

力扣题目链接
给你一个字符串 s ，颠倒字符串中单词的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：颠倒后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，颠倒后的字符串需要将单词间的空格减少到仅有一个。

提示：

• 1 <= s.length <= 104
• s 包含英文大小写字母、数字和空格 ’ ’
• s 中 至少存在一个 单词

涉及知识点

这道题目虽然是中等题目，但实际上做起来不难的。这里面主要涉及的还是将字符串放入数组中，因为数组是非常容易操作的，而且大家可以记住这些内容。所以这道题目所涉及的知识点是：

• 数组是存储在连续内存空间的相同类型数据的集合
• 数组下标都是从0开始
• 数组在内存空间的地址都是连续的
• 使用双指针来操作数组，从数组两端出发

那么根据题目，我们可以提炼的关键点：

• 输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格； 这些都是需要在代码中考虑的
• 返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格；结果字符串的前后端都不含空格，各个字母之间只能有一个空格

当然了，这道题目直接直白点想，既然是颠倒字符串，那我直接颠倒不就行了，确实可行，不过需要注意的是，颠倒完整体的字符串后，单个字母也是需要颠倒一下的，另外也要注意下去除多余空格。

题目解答

Java题解一

思路分析

将字符串放入数组，然后使用双指针操作数组，从数组的右向左将字符串中的字母依次放入一个可变的可变的字符序列StringBuilder

具体思路如下：

• 将字符串放入数组
• 定义左右指针，用来操作数组
• 首先去除数组中（原字符串）的最左边和最右边（首尾）的空格，可能有很多，所以用while
• 因为是颠倒，所以从数组的右边向左边遍历，定义一个临时指针
• 首先从右向左找第一个字母，只到遇到第一个空格为止
• 把第一个字符添加到字符序列result中，然后right = temp; 继续左移

class Solution {
    public String reverseWords(String s) {
        //将字符串放入数组方便反转
        char[] charArray=s.toCharArray(); 

        //定义左右指针
        int left=0;
        int right=s.length()-1;
        
        // 删除左边空格
        while(charArray[left]==' '){
            left++;
        }
        //删除右边空格
        while(charArray[right]==' '){
            right--;
        }
        //存放结果
        StringBuilder result = new StringBuilder();

        // 颠倒字符串
        while(left <= right){

            int temp = right;//临时指针

            // 从右向左找第一个字母，只到遇到第一个空格为止
            while(temp >= left && charArray[temp]!=' '){
                temp--;
            }
            // 找到右边第一个单词后将其正向放入result中
            for(int i = temp+1; i<= right; i++){
                result.append(charArray[i]);
            }
            //每个单词后添加一个空格，最后一个单词不添加
            if(temp > left) 
                result.append(' ');

            // 第一个空格后，其他的空格都跳过
            while(temp >= left && charArray[temp]==' '){
                temp--;
            }
            // 把 right 放到下一个单词出现的位置，继续循环
            right = temp; //左移
        }
        return result.toString(); //结果转为字符串
    }
}

Java题解二

思路分析

根据颠倒字符串的要求，直接暴力解法，先整体颠倒下，然后再颠倒下单个字母，注意去重多余空格。

具体思路如下：

• 主要是三个步骤：去重多余空格，颠倒整个字符串，颠倒单个字母
• 去重多余空格的时候，使用双指针的方便，从字符串的左右两端删除多余空格，以及字符串中间的的多余空格，注意中间的每个单词中间留一个空格
• 颠倒字符串，使用setCharAt()方法，交换前后两个字母，然后两个指针向中间移动
• 颠倒单个字母，遍历整个字符串，定义前后两个指针，调用前面定义的反转字符串的方法，对整个字符串中空格间的单词进行反转

class Solution {
    public String reverseWords(String s) {

        //去除多余空格
        StringBuilder result = trimSpaces(s); 

        // 翻转字符串
        reverse(result, 0, result.length() - 1);

        // 翻转单个单词
        reverseEachWord(result);

        return result.toString(); //输出结果
    }

    //去除多余空格
    public StringBuilder trimSpaces(String s) {
        int left = 0;
        int right = s.length() - 1;

        // 去掉字符串开头的空白字符
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }

        // 去掉字符串末尾的空白字符
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }

        // 将字符串间多余的空白字符去除
        StringBuilder sb = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);

            if (c != ' ') {
                sb.append(c);
            } else if (sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }

            ++left;
        }
        return sb;
    }

    //翻转字符串
    public void reverse(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left); //临时变量
            sb.setCharAt(left, sb.charAt(right)); //右边替换左边
            sb.setCharAt(right, tmp); //临时变量补上右边
            left++; //右移
            right--;//左移
        }
    }

    //翻转单个单词
    public void reverseEachWord(StringBuilder sb) {
        int n = sb.length();
        int start = 0;
        int end = 0;

        while (start < n) {
            // 循环至单词的末尾
            while (end < n && sb.charAt(end) != ' ') {
                ++end;
            }
            // 翻转单词
            reverse(sb, start, end - 1);
            // 更新start，去找下一个单词
            start = end + 1;
            ++end;
        }
    }
}