翻转单词序列【Java版】

方法一：一轮扫描法

//从后向前扫描，将单词转移到另一个O（n）空间String
//两重循环，外面i一直向左探测，探测到一个单词开始处，用j向右遍历，进行复制
public class Solution {
    public String ReverseSentence(String str) {
        String res = "";//【String不要用null初始化, 要用空字符串""】
        //如果写成 String str = null; ==>系统会得到str = "null"
        if(str == null || str.length()==0)return res;
        char[] ch = str.toCharArray();
        for(int i=ch.length-1; i>=0; --i){
            if(i==0 || ch[i-1]==' '){//i==0写在前面，防止i-1溢出
                for(int j=i; j!=ch.length && ch[j]!=' '; ++j){
                    res += ch[j];//【String直接加char】
                }
                if(i!=0) res += ' ';//加空格，最后不加
            }
        }
        return res;
    }
}//时间O(n) 空间O(n)

方法二：两轮翻转法

//首先完全翻转，然后逐个单词翻转
public class Solution {
    public String ReverseSentence(String str) {
        char[] ch = str.toCharArray();
        char temp = 0;
        for(int i=0; i<ch.length/2; ++i){
            temp = ch[i];
            ch[i] = ch[ch.length-1-i];
            ch[ch.length-1-i] = temp;
        }
        int left = 0;
        String res ="";
        for(int right=0; right<=ch.length-1; ++right){
            if(right == ch.length-1 || ch[right+1]==' '){
                for(int i=right; i>=left; --i){
                    res += ch[i];
                }
                if(right != ch.length-1)res += ' ';
                left = right+2;
            }
        }
        return res;
    }
}//时间O(n) 空间O(n)   
//此方法（对于Java语言）并无优势，两轮而且都调整、耗时多
//C语言，可以做到空间O(1)   //C语言对String操作的自由度更高