微软等数据结构与算法面试100题第十题

第十题

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

分析：
可以根据空格符将单词分开，然后针对每个单词进行操作，string类型的有很多库函数，比如可以实现分割string类型的字符串。
这里使用c++实现，本来是想使用split函数进行分割的，但是MSDN上string对象成员函数http://msdn.microsoft.com/zh-cn/library/b873y76a%28v=vs.80%29
split函数示例运行不对，然后就采用查找空格来分割。希望有大牛指出split成员函数的问题。

代码如下：
[cpp]
#include<iostream>
#include<string>

using namespace std;
using std::string;

void reverseSequence(string & words)
{
    int lengthWords = words.length();
    if(0==lengthWords) return;

    char temp;
    //reverse all the words
    for(int i =0; i < lengthWords/2; i++)
    {
        temp = words.at(i);
        words.at(i) = words.at(lengthWords-1-i);
        words.at(lengthWords-1-i) = temp;
    }


    //conduct statistics
    int wordsNum = 0;
    for(int i = 0; i < words.length(); i++)
    {
        if(words.at(i)==' ')
            wordsNum++;
    }
    wordsNum = wordsNum + 1;

    int *arrayLength = new int[wordsNum];
    for(int i =0 ; i < wordsNum; i++)arrayLength[i] = 0;
    int j = 0;
    for(int i = 0; i < lengthWords; i++)
    {
        if(' '!=words.at(i))arrayLength[j]++;
        else j = j + 1;
    }

    //reverse each words
    int index;
    int currentIndex = 0;
    for(int i =0 ; i < wordsNum; i++)
    {
        index = currentIndex;
        while(index<arrayLength[i]/2 + currentIndex)
        {
            temp = words.at(index);
            words.at(index) = words.at(currentIndex+currentIndex+arrayLength[i]-1-index);
            words.at(currentIndex+currentIndex+arrayLength[i]-1-index)=temp;
            index++;
        }
        currentIndex = currentIndex + arrayLength[i] + 1;
    }

}

int main()
{
    string a = "i am a student";
    for(int i=0;i<a.length();i++)cout<<a.at(i);
    cout<<endl;

    reverseSequence(a);
    for(int i=0; i<a.length();i++)cout<<a.at(i);
    cout<<endl;
    return 0;
}

补充：软件开发 , C++ ,

微软等数据结构与算法面试100题 第十题

微软等数据结构与算法面试100题第十题