这好像是传说中微软的一道面试题,没事做来玩玩。第一个方法想的比较ft,从时间复杂度上来看太大了;刚开始想其实是想的第二个方法,只是被第二个方法中把每个word都搞反了而郁闷了一下,其实再reverse一下每个word就纠正过来了:)
output:
//
ReverseInPlace.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include "string.h"
#define SPACE 32
void SwapInPlace( char * a, char * b)
{
if ( *a != *b )
{
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
}
void ReverseInPlace( char* src)
{
size_t len = strlen(src);
for ( size_t i=0 ; i < len ; ++i )
{
if ( *(src+i) == SPACE )
{
for ( size_t m=0 ; m <= i-1 ; ++m )
{
for ( size_t n=0 ; n < len-1 ; ++n )
{
SwapInPlace(src+n, src+(len+n+1)%len);
}
}
len -= i;
for ( size_t n=0 ; n < len-1 ; ++n )
{
SwapInPlace(src+n, src+(len+n+1)%len);
}
len--;
i = -1;
}
}
}
void ReverseInPlace2( char* src)
{
size_t i, start;
size_t len = strlen(src);
for ( i=0 ; i < len/2 ; ++i )
{
SwapInPlace(src+i, src+len-1-i);
}
start = 0;
for ( i=0 ; i < len ; ++i )
{
if ( *(src+i) == SPACE || i == len-1 )
{
if ( i== len-1 ) i++;
for ( size_t j=0 ; j < (i-start)/2 ; ++j )
{
SwapInPlace(src+start+j, src+i-1-j);
}
start = i+1;
}
}
}
int _tmain( int argc, _TCHAR* argv[])
{
char str[] = "Reverse A Sentence In Place Absolutely a a";
printf("SRC: %s\r\n", str);
ReverseInPlace(str);
printf("DES: %s\r\n", str);
ReverseInPlace2(str);
printf("SRC: %s", str);
getchar();
}
#include "stdafx.h"
#include "string.h"
#define SPACE 32
void SwapInPlace( char * a, char * b)
{
if ( *a != *b )
{
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
}
void ReverseInPlace( char* src)
{
size_t len = strlen(src);
for ( size_t i=0 ; i < len ; ++i )
{
if ( *(src+i) == SPACE )
{
for ( size_t m=0 ; m <= i-1 ; ++m )
{
for ( size_t n=0 ; n < len-1 ; ++n )
{
SwapInPlace(src+n, src+(len+n+1)%len);
}
}
len -= i;
for ( size_t n=0 ; n < len-1 ; ++n )
{
SwapInPlace(src+n, src+(len+n+1)%len);
}
len--;
i = -1;
}
}
}
void ReverseInPlace2( char* src)
{
size_t i, start;
size_t len = strlen(src);
for ( i=0 ; i < len/2 ; ++i )
{
SwapInPlace(src+i, src+len-1-i);
}
start = 0;
for ( i=0 ; i < len ; ++i )
{
if ( *(src+i) == SPACE || i == len-1 )
{
if ( i== len-1 ) i++;
for ( size_t j=0 ; j < (i-start)/2 ; ++j )
{
SwapInPlace(src+start+j, src+i-1-j);
}
start = i+1;
}
}
}
int _tmain( int argc, _TCHAR* argv[])
{
char str[] = "Reverse A Sentence In Place Absolutely a a";
printf("SRC: %s\r\n", str);
ReverseInPlace(str);
printf("DES: %s\r\n", str);
ReverseInPlace2(str);
printf("SRC: %s", str);
getchar();
}
output:
SRC: Reverse A Sentence In Place Absolutely a a
DES: a a Absolutely Place In Sentence A Reverse
SRC: Reverse A Sentence In Place Absolutely a a
DES: a a Absolutely Place In Sentence A Reverse
SRC: Reverse A Sentence In Place Absolutely a a
本文转自博客园鸟食轩的博客,原文链接:http://www.cnblogs.com/birdshome/,如需转载请自行联系原博主。