Code: Reverse A Sentence in Place

简介:
  这好像是传说中微软的一道面试题,没事做来玩玩。第一个方法想的比较ft,从时间复杂度上来看太大了;刚开始想其实是想的第二个方法,只是被第二个方法中把每个word都搞反了而郁闷了一下,其实再reverse一下每个word就纠正过来了:)

None.gif //  ReverseInPlace.cpp : Defines the entry point for the console application.
None.gif

None.gif #include  "stdafx.h"
None.gif #include  "string.h"
None.gif
None.gif #define SPACE    32
None.gif
None.gif void SwapInPlace( char * a,  char * b)
ExpandedBlockStart.gif ContractedBlock.gif dot.gif{
InBlock.gif     if ( *a != *b )
ExpandedSubBlockStart.gif ContractedSubBlock.gif     dot.gif{
InBlock.gif        *a = *a ^ *b;
InBlock.gif        *b = *a ^ *b;
InBlock.gif        *a = *a ^ *b;
ExpandedSubBlockEnd.gif    }
ExpandedBlockEnd.gif}
None.gif
None.gif void ReverseInPlace( char* src)
ExpandedBlockStart.gif ContractedBlock.gif dot.gif{
InBlock.gif    size_t len = strlen(src);
InBlock.gif     for ( size_t i=0 ; i < len ; ++i )
ExpandedSubBlockStart.gif ContractedSubBlock.gif     dot.gif{
InBlock.gif         if ( *(src+i) == SPACE )
ExpandedSubBlockStart.gif ContractedSubBlock.gif         dot.gif{
InBlock.gif             for ( size_t m=0 ; m <= i-1 ; ++m )
ExpandedSubBlockStart.gif ContractedSubBlock.gif             dot.gif{
InBlock.gif                 for ( size_t n=0 ; n < len-1 ; ++n )
ExpandedSubBlockStart.gif ContractedSubBlock.gif                 dot.gif{
InBlock.gif                    SwapInPlace(src+n, src+(len+n+1)%len);
ExpandedSubBlockEnd.gif                }
ExpandedSubBlockEnd.gif            }
InBlock.gif            len -= i;
InBlock.gif             for ( size_t n=0 ; n < len-1 ; ++n )
ExpandedSubBlockStart.gif ContractedSubBlock.gif             dot.gif{
InBlock.gif                SwapInPlace(src+n, src+(len+n+1)%len);
ExpandedSubBlockEnd.gif            }
InBlock.gif            len--;
InBlock.gif            i = -1;
ExpandedSubBlockEnd.gif        }
ExpandedSubBlockEnd.gif    }
ExpandedBlockEnd.gif}
None.gif
None.gif void ReverseInPlace2( char* src)
ExpandedBlockStart.gif ContractedBlock.gif dot.gif{
InBlock.gif    size_t i, start;
InBlock.gif    size_t len = strlen(src);
InBlock.gif     for ( i=0 ; i < len/2 ; ++i )
ExpandedSubBlockStart.gif ContractedSubBlock.gif     dot.gif{
InBlock.gif        SwapInPlace(src+i, src+len-1-i);
ExpandedSubBlockEnd.gif    }
InBlock.gif    start = 0;
InBlock.gif     for ( i=0 ; i < len ; ++i )
ExpandedSubBlockStart.gif ContractedSubBlock.gif     dot.gif{
InBlock.gif         if ( *(src+i) == SPACE || i == len-1 )
ExpandedSubBlockStart.gif ContractedSubBlock.gif         dot.gif{
InBlock.gif             if ( i== len-1 ) i++;
InBlock.gif             for ( size_t j=0 ; j < (i-start)/2 ; ++j )
ExpandedSubBlockStart.gif ContractedSubBlock.gif             dot.gif{
InBlock.gif                SwapInPlace(src+start+j, src+i-1-j);
ExpandedSubBlockEnd.gif            }
InBlock.gif            start = i+1;
ExpandedSubBlockEnd.gif        }
ExpandedSubBlockEnd.gif    }
ExpandedBlockEnd.gif}
None.gif
None.gif int _tmain( int argc, _TCHAR* argv[])
ExpandedBlockStart.gif ContractedBlock.gif dot.gif{
InBlock.gif     char str[] = "Reverse A Sentence In Place Absolutely a a";
InBlock.gif    printf("SRC: %s\r\n", str);
InBlock.gif    ReverseInPlace(str);
InBlock.gif    printf("DES: %s\r\n", str);
InBlock.gif    ReverseInPlace2(str);
InBlock.gif    printf("SRC: %s", str);
InBlock.gif    
InBlock.gif    getchar();
ExpandedBlockEnd.gif}

output:
None.gifSRC: Reverse A Sentence In Place Absolutely a a
None.gifDES: a a Absolutely Place In Sentence A Reverse
None.gifSRC: Reverse A Sentence In Place Absolutely a a

本文转自博客园鸟食轩的博客,原文链接:http://www.cnblogs.com/birdshome/,如需转载请自行联系原博主。

目录
相关文章
|
3月前
|
Python
完美解决丨2. `TypeError: list indices must be integers or slices, not str`
完美解决丨2. `TypeError: list indices must be integers or slices, not str`
LeetCode 150. Evaluate Reverse Polish Notation
根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
28 0
LeetCode 150. Evaluate Reverse Polish Notation
|
数据安全/隐私保护 C++ Python
LeetCode 804. Unique Morse Code Words
LeetCode 804. Unique Morse Code Words
52 0
Data Structures and Algorithms (English) - 6-4 Reverse Linked List(20 分)
Data Structures and Algorithms (English) - 6-4 Reverse Linked List(20 分)
96 0
Leetcode-Easy 804. Unique Morse Code Words
Leetcode-Easy 804. Unique Morse Code Words
74 0
Leetcode-Easy 804. Unique Morse Code Words
ValueError: Error when checking : expected input_1 to have 4 dimensions, but got array with shape
ValueError: Error when checking : expected input_1 to have 4 dimensions, but got array with shape
359 0