微软等数据结构与算法面试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 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;
}

更多详细信息请查看java教程网 http://www.itchm.com/forum-59-1.html