MS面試曾出過這樣一道題目，將給定字符串按單詞翻轉，如，"This is Charles" -> "Charles is This"
方法一，需要額外緩沖區
?1
#include?
<
cstring
>
?2
void
?ReverseByWords(
char
?
*
s,?
char
?seperator)
?3
{
?4
????
int
?iRevTokenScanner?
=
?strlen(s)?
-
?
1
;
?5
????
char
?
*
buffer?
=
?
new
?
char
[iRevTokenScanner?
+
?
2
]();
?6
????
int
?iWritePos?
=
?
0
;
?7
????
int
?iWordEnd,?iWordReadPos;
?8
?9
????
while
?(iRevTokenScanner?
>=
?
0
)
10
????
{
11
????????
if
?(s[iRevTokenScanner]?
!=
?seperator)
12
????????
{
13
????????????iWordEnd?
=
?iRevTokenScanner;
14
????????????
15
????????????
while
?(iRevTokenScanner?
>=
?
0
?
&&
??s[iRevTokenScanner]?
!=
?seperator)
16
????????????????iRevTokenScanner
--
;
17
????????????
18
????????????iWordReadPos?
=
?iRevTokenScanner?
+
?
1
;
19
20
????????????
while
?(iWordReadPos?
<=
?iWordEnd)
21
????????????????buffer[iWritePos
++
]?
=
?s[iWordReadPos
++
];
22
????????}
23
????????
else
24
????????
{
25
????????????buffer[iWritePos
++
]?
=
?s[iRevTokenScanner
--
];
26
????????}
?
27
????}
28
29
????buffer[iWritePos]?
=
?
'
\0
'
;
30
????strcpy(s,?buffer);
31
32
????
if
?(buffer)
33
????
{
34
????????delete?[]?buffer;
35
????????buffer?
=
?
0
;
36
????}
37
}
方法二，個人比較prefer
?1void?ReverseString(char?*s,?int?start,?int?end)
?2{
?3????while?(start?<?end)
?4????{
?5????????if?(s[start]?!=?s[end])
?6????????{
?7????????????s[start]?^=?s[end];
?8????????????s[end]?^=?s[start];
?9????????????s[start]?^=?s[end];
10????????}
11????????????????
12????????start++;
13????????end--;
14????}
15}
16
17void?ReverseByWords(char?*s,?int?len,?char?seperator)
18{
19????int?start?=?0,?end?=?0;
20
21????ReverseString(s,?start,?len?-?1);
22
23????while?(end?<?len)
24????{
25????????if?(s[end]?!=?seperator)
26????????{
27????????????start?=?end;
28
29????????????while?(end?<?len?&&?s[end]?!=?seperator)
30????????????????end++;
31????????????end--;
32
33????????????ReverseString(s,?start,?end);
34????????}
35????????
36????????end++;
37
38????}//while
39}
等有空再回來作注釋吧，現在挺忙的，先把code貼出來
posted on 2006-11-16 18:50
Charles 閱讀(429)
評論(0) 編輯 收藏 引用 所屬分類:
面試小算法