面试题58(1):翻转字符串

题目

翻转单词顺序
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student"，则输出“student. a am I”。

解题思路

1. 翻转句子中所有的字符
2. 翻转每个单词中字符的顺序

代码

• 注意字符串方式和字符方式的区别
  字符串方式初始化一个字符串和输出一个字符串

string str = "I am a student.";
for(int i = 0; i < s.size();i++)
    {
        cout << s[i];
        
    }
    cout << endl;

字符方式初始化一个字符串(c语言特有的)和输出一个字符串

char str[] = "I am a student.";
int i = 0;
    while(s[i]!='\0')
    {
        cout << s[i++];
        
    }
    cout << endl;

• 字符char方式

1. 定义两个指针pBegin和pEnd,分别指向字符串的头部和尾部。翻转整个句子。
2. 以空格为分隔符分离出一个单词，并进行翻转。
   两个指针pBegin和pEnd指向字符串的首部。
   先移动pEnd指针，当pEnd指针遇到空格时，说明pBegin和pEnd之间的距离代表一个单词，此时*pEnd会回退一个字符，翻转，这样空格的位置保持不变。
   让pBegin = ++pEnd,会让这两个指针共同指向空格也就是到达if( *pBegin == ' ') ，使两个指针共同经过空格符，然后重复上述过程。

class Solution{
  public:
    void Reverse(char *pBegin,char *pEnd)
    {
        if(pBegin == NULL || pEnd == NULL)
        {
            return ;
        }
        while(pBegin < pEnd)
        {
            char temp = *pBegin;
            *pBegin   = *pEnd;
            *pEnd     = temp;

            pBegin++;
            pEnd--;
        }
    }
    
    char*  ReverseSentence(char *pData)
    {
        if(pData == NULL)
        {
            return NULL;
        }
        char *pBegin = pData;
        char *pEnd   = pData;
        while(*pEnd != '\0')
        {
            pEnd++;
        }
        pEnd--; //去掉\0
        //翻转整个句子
        Reverse(pBegin,pEnd);
        //翻转句子中的每个单词
        pBegin = pEnd = pData;
        while(*pBegin !='\0')
        {
            if(*pBegin == ' ')//截出一个单词
            {
                pBegin++;
                pEnd++;
            }
            else if(*pEnd == ' ' || *pEnd == '\0')
            {
                Reverse(pBegin,--pEnd);
                pBegin = ++pEnd;
            }
            else
            {
                pEnd++;
            }
        }
        return pData;
    }
};

• 字符串string方式

class Solution{
  public:
    void Reverse(string &str,int left,int right)
    {
        while(left < right)
        {
            char temp = str[left];
            str[left]   = str[right];
            str[right]  = temp;

            left++;
            right--;
        }
    }
    
    string  ReverseSentence(string str)
    {
        int length = str.size();
        int left = 0;
        int right= length-1;
        Reverse(str,left,right);

        left = 0;
        for(int i = 0; i <= length;i++)
        {
            if(str[i] == ' ' || str[i] == '\0')
            {
                Reverse(str,left,i-1);
                left = i+1;
            }
        }
        return str;
    }
};

完整代码见Github