151. 反转字符串中的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序（单词本身不反转，单词间的反转）。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
● 进阶：尝试使用O(1)额外空间复杂度的原地解法。

解题思路：
(1) 最简单的想法就是：先对字符串去除前后空格，然后使用一个StringBuilder对象(sb)，从后往前遍历String，找到一个单词（双指针划定）后就追加到sb中。

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        StringBuilder sb = new StringBuilder();
        int i = s.length()-1;
        int j = i;
        while(i >= 0){
            // 找下一个单词的末尾
            while(s.charAt(i) == ' ') i--;
            j = i;
            // 找下一个单词的头
            while((i-1) >= 0 && s.charAt(i-1) != ' ') i--;
            sb.append(s.substring(i, j+1));
            sb.append(" ");
            i--;
        }
        return sb.substring(0, sb.length()-1).toString();
    }
}

(2) 进阶的解法：【不使用任何库函数的基础上】消除多余空格+整体反转+单词反转。⭐
● 消除多余空格：同向双指针。【类似：代码随想录-移除元素】
● 整体反转：相向双指针【类似：代码随想录-反转字符串】
● 单词反转：(同整体反转，这里是局部反转) 相向双指针

class Solution {
    public String reverseWords(String s) {
        // 先将String转化成char[]
        char[] s_char = s.toCharArray();
        // 1、消除多余空格
        int i = 0;
        int j = 0;
        while(j < s_char.length){
            if(s_char[j] != ' ') s_char[i++] = s_char[j++];
            else{
                // 遇到空格了，找到最右边的空格
                while((j+1) < s_char.length && s_char[j] == s_char[j+1]) j++;
                if(j == s_char.length-1) break; // 末尾的空格
                if(i > 0) s_char[i++] = s_char[j++]; // 中间的空格
                else j++; // 开头的空格
            }
        }
        // 此时i就是有效的s_char长度
        int len = i;
        j = i - 1;
        i = 0;
        // 2、利用双指针，将整个字符数组反转
        reverseArrayByIndex(s_char, i, j);
        // 3、找到每个单词进行反转
        i = 0;
        j = 0;
        while(j < len){
            // 找到单词的尾
            while((j+1) < len && s_char[j+1] != ' ') j++;
            reverseArrayByIndex(s_char, i, j);
            i = j + 2;
            j = i;
        }
        return new String(s_char).substring(0, len);
    }
    public void reverseArrayByIndex(char[] arr, int i, int j){
        while(i < j){
            char c = arr[i];
            arr[i] = arr[j];
            arr[j] = c;
            i++;
            j--;
        }
    }
}