面试题 58.1:翻转单词顺序列

题目描述

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

思路

先把句子中的所有字符进行翻转,再翻转每个单词中字符的顺序。

翻转每个单词时,添加两个指针,分别指向单词的第一个字符和单词的最后一个字符。

当第一个指针指向空格时,两个指针都前进一步。

否则判断第二个指针是是否到单词的最后一个字符了,到了则翻转,之后将两个指针分别前进一步指向空格。

否则说明还没到单词结尾,第二个指针继续前进一步。

这里第二个指针判断时需要注意索引越界以及是否已到结尾。

代码

public class Solution {
    public String ReverseSentence(String str) {
        if (str == null || str.length() == 0) {
            return "";
        }

        // 如果就是一个单词,不是句子
        if (!str.contains("")) {
            return str;
        }

        char[] charArray = str.toCharArray();
        int length = charArray.length;

        // 将整个句子进行翻转
        reverse(charArray, 0, length - 1);

        // 标记单词的第一个字符
        int left = 0;
        // 标记单词的最后一个字符
        int right = 0;

        // 找到单词,并翻转
        while (left < length) {
            // 如果指向的是空格
            if (charArray[left] == ' ') {
                left++;
                right++;
            } else if ((right < length - 1 && charArray[right + 1] == ' ') 
                      || right == length - 1) {
                // 当第二个指针的下一个字符是空格,说明已经到单词结尾
                // 或者第二个指针已经到句子结尾了,那么就可以翻转了
                reverse(charArray, left, right);
                // 两个指针指向单词后面的字符
                right++;
                left = right;
            } else { // 还没找到单词,第二个指针直接加 1
                right++;
            }
        }

        return new String(charArray);
    }

    private void reverse(char[] arr, int left, int right) {
        char ch;
        while (left < right) {
            ch = arr[left];
            arr[left] = arr[right];
            arr[right] = ch;
            left++;
            right--;
        }
    }
}

来源:35分类目录

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。