函數實現將網址進行如下操作
www.google.com 轉成 com.google.www 及 mail.netease.com 轉成 com.netease.mail
不允許用STL,空間為 O(1)
http://topic.csdn.net/u/20110425/12/8b5e155c-73d1-40af-84b8-6b6493f638e2.html一開始把 O(1) 看做時間復雜度了，如果是空間復雜度，直接在原地兩次翻轉即可。整體翻轉，部分翻轉順序可以任意。
1 #include <iostream>
2 using namespace std;
3
4 void reverse_(char* s, int left, int right)
5 {
6 while (left < right)
7 {
8 s[left] ^= s[right];
9 s[right] ^= s[left];
10 s[left] ^= s[right];
11 ++left;
12 --right;
13 }
14 }
15
16 int findch(char* s, char c, int n)
17 {
18 int ret, len = strlen(s);
19 for (ret = n; ret < len; ++ret)
20 {
21 if (s[ret] == c)
22 {
23 return ret;
24 }
25 }
26 return -1;
27 }
28
29 char* reverse(char* s)
30 {
31 reverse_(s, 0, strlen(s) - 1);
32 int left = 0, right = findch(s, '.', left);
33 while (right != -1)
34 {
35 reverse_(s, left, right - 1);
36 left = right + 1;
37 right = findch(s, '.', left);
38 }
39 reverse_(s, left, strlen(s) - 1);
40 return s;
41 }
42
43 int main()
44 {
45 char s[100];
46 while (cin >> s)
47 {
48 cout << reverse(s) << endl;
49 }
50 return 0;
51 }
如果是時間復雜度呢？
這里由個限制，就是只有兩個 . 符號時才成立。使用字符串數組存儲字符串，將首尾字符串指針交換即可。
例如 mail.netease.com
存在于字符串指針數組中：
mail
.
netease
.
com
將指向 mail 和 指向 com 的兩個字符串指針交換即可。
1 #include <iostream>
2 using namespace std;
3
4 int main()
5 {
6 char* s[100];
7 int i;
8 for (i = 0; i < 100; ++i)
9 {
10 s[i] = new char[100];
11 }
12 char c;
13 i = 0;
14 int j = 0;
15 // while (cin >> c)
16 // while (scanf("%c", &c))
17 while (c = getchar())
18 {
19 if (c == '\n')
20 {
21 break;
22 }
23 if (c != '.')
24 {
25 s[i][j] = c;
26 ++j;
27 s[i][j] = '\0';
28 }
29 else
30 {
31 // s[i][j] = '\0';
32 ++i;
33 s[i][0] = c;
34 s[i][1] = '\0';
35 j = 0;
36 ++i;
37 }
38 }
39 char* t = s[0];
40 s[0] = s[i];
41 s[i] = t;
42 for (j = 0; j <= i; ++j)
43 {
44 cout << s[j];
45 }
46 cout << endl;
47 return 0;
48 }
posted on 2011-04-25 23:18
unixfy 閱讀(244)
評論(0) 編輯 收藏 引用