45. 翻转单词顺序列《剑指Offer》(Java版)

古城微笑少年丶 2022-01-30 13:37 87阅读 0赞

## 题目描述 ##

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

/**
     * 翻转句子中单词的顺序
     * 例如，输入：
     * “I am a student.”
     * 输出：
     * “student. a am I”
     */
    public class _042_ReverseSentence {
        public String ReverseSentence(String str) {
            char[] c = str.toCharArray();
            // 将“I am a student.”-->".tneduts a ma I"
            reserveStr(c, 0, c.length - 1);
            for (int last = 0, head = 0; last < c.length; last++) {
                if (c[last] == ' ') {
                    // 翻转所有单词
                    reserveStr(c, head, last - 1);
                    while (last < c.length && c[last] == ' ') {
                        last++;
                    }
                    head = last;
                    last--;
                } else if (last == c.length - 1) {
                    reserveStr(c, head, c.length - 1);
                }
            }
            return new String(c);
        }
    
        private void reserveStr(char[] c, int head, int last) {
            while (head < last) {
                swap(c, head, last);
                head++;
                last--;
            }
        }
    
        private void swap(char[] c, int head, int last) {
            char t = c[head];
            c[head] = c[last];
            c[last] = t;
        }
    
    }