字符串旋转问题
需要 O(N) 的时间，O(1) 的空间
借助字符串翻转
ABCEFG
((ABC)'(EFG)')'
=(CBAGFE)'
=EFGABC
对一个字符串，进行给定位置的逆转。
1 #include <iostream>
2 using namespace std;
3
4 void swap(char& a, char& b)
5 {
6 a ^= b;
7 b ^= a;
8 a ^= b;
9 }
10
11 void reverse(char* s, int l, int h)
12 {
13 while (l < h)
14 {
15 swap(s[l++], s[h--]);
16 }
17 }
18
19 int getLen(char* s)
20 {
21 int ret = 0;
22 while (*s++ != '\0')
23 {
24 ++ret;
25 }
26 return ret;
27 }
28
29 char* rotate(char* s, int pos)
30 {
31 int t = getLen(s) - 1;
32 reverse(s, 0, pos - 1);
33 reverse(s, pos, t);
34 reverse(s, 0, t);
35 return s;
36 }
37
38 int main()
39 {
40 char s[100];
41 int pos;
42 while (cin >> s >> pos)
43 {
44 cout << rotate(s, pos) << endl;
45 }
46 return 0;
47 }
http://www.cppblog.com/jake1036/archive/2011/03/05/141163.html
posted on 2011-06-17 22:58
unixfy 阅读(119)
评论(0) 编辑 收藏 引用