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

微软等数据结构与算法面试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成员函数的问题。

代码如下：

#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 wordsfor(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 statisticsint 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 wordsint 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;}