翻转句子中单词的顺序

时间:2022-02-25 11:43:21

微软面试题之一,难度系数低。

题目描述:

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


逻辑分析:因为之前看过July的《程序与编程艺术系列》,而第一篇刚好就是左旋字符串问题,这题和左旋字符串问题相似,解法也一目了然。

1、显然,字符串是以' '隔开,我们首先要分拆子串,然后将每一个子串进行翻转,以本题为例,I am a student.=>I ma a .tneduts

2、这时你可以看到翻转过的字符串就是结果的镜像,所以,只需要整体翻转一次,就可以完成要求。I ma a .tneduts=>student. a am I

3、上述做法的时空复杂度很容易分析,所谓翻转,无非就是逆序输出,那么很容易会想到栈,只需要压栈,然后弹栈,即可实现翻转的效果,时间复杂度O(n),空间复杂度O(n)。

4、仔细分析之后,就会发现,栈已经没有必要了,我们只需要一个交换元char temp;字符串反转时,只需要做经典的三步交换即可,时间复杂度O(n),空间复杂度O(1)。


最后,附上源码实现:

///copyright @玉涵
///updated 2014/1/8
#include <stdio.h>
#include <string.h>

void rotateStr(char *str, int start, int end)
{
if(str == NULL || start > end)
return ;

char temp;
while(start < end)
{
temp = str[start];
str[start] = str[end];
str[end] = temp;

start++;
end--;
}
}

void reverseStr(char *str)
{
int len = strlen(str);

int s = 0;
int e = 0;

for(int i=0; i<len; i++)
{
e++;
if(str[e] == ' ' || str[e] == '\0')
{
rotateStr(str, s, e-1);
s = e + 1;
}
}

rotateStr(str,0,len-1);
}

int main()
{
char str[] = "I am a student.";
reverseStr(str);
puts(str);
return 0;
}


截图:

翻转句子中单词的顺序