题解 | #翻转单词序列#

public class Solution {
    public String ReverseSentence(String str) {
        if (str == null) return "";
        char[] chars = str.toCharArray();
        // 消除多余的空格
        // 字符串最终的有效长度
        int len = 0;
        // 当前用来存放字符的位置
        int cur = 0;
        // 前一个字符是否为空格字符
        boolean space = true;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != ' ') { // chars[i]是非空格字符
                chars[cur++] = chars[i];
                space = false;
            } else if (space ==
                       false) { // chars[i]是空格字符，chars[i - 1]是非空格字符
                chars[cur++] = ' ';
                space = true;
            }
        }
        len = space ? (cur - 1) : cur;
        if (len <= 0) return "";

        // 对整一个有效字符串进行逆序
        reverse(chars, 0, len);
        // 对每一个单词进行逆序
        // 前一个空格字符的位置（有-1位置有个假想的哨兵，就是一个假想的空格字符）
        int prevSapceIdx = -1;
        for (int i = 0; i < len; i++) {
            if (chars[i] != ' ') continue;
            reverse(chars, prevSapceIdx + 1, i);
            prevSapceIdx = i;
        }
        // 翻转最后一个单词
        reverse(chars, prevSapceIdx + 1, len);
        return new String(chars, 0, len);
    }
    /**
     * 将[li, ri)范围内的字符串进行逆序
     */
    private static void reverse(char[] chars, int li, int ri) {
        ri--;
        while (li < ri) {
            // 左右字符交换
            char tmp = chars[li];
            chars[li] = chars[ri];
            chars[ri] = tmp;
            li++;
            ri--;
        }
    }
}

解题思想：

* 方式一：java-api

* 方式二：借助栈

* 方式三：原生方法