給定一個(gè)字符串，僅包含26個(gè)字母以及'*'字符，要求將所有'*'字符移動(dòng)到字符串前面，并且保證原字母順序不變。
開始想這不就是簡(jiǎn)單的一遍快排么，后來仔細(xì)想了想不太對(duì)啊，一遍快排就把字母順序打亂了，后來又想了想，還是有時(shí)間復(fù)雜度O(N)，空間復(fù)雜度O(1)的算法的，大體思想就是i從后向前掃描，找到第一個(gè)'*'，然后j在i的位置向前掃描，找到第一個(gè)字母，然后將str[i]與str[j]交換，之后i--，j--,繼續(xù)前面的過程，直到j(luò)<0為止。這樣做之所以復(fù)雜度為O(N)是因?yàn)閕每次都是遞減的，j同樣也是遞減的，這樣i最多走N步，j也同樣最多走N步，因此復(fù)雜度肯定是N的
程序如下：
1 #include <cstdio>
2 #include <string.h>
3
4 void inline swap(char* a, char* b) {
5 char temp = *a; *a = *b; *b = temp;
6 }
7
8 char *process(char *a, int len) {
9 int i = len - 1;
10 while (i >= 0 && a[i] != '*') --i;
11 int j = i - 1;
12 while (j >= 0 && a[j] == '*') --j;
13 if (j >= 0) swap(a + i, a + j);
14 --i, --j;
15 while (j >= 0) {
16 while (i >= 0 && a[i] != '*') --i;
17 while (j >= 0 && a[j] == '*') --j;
18 if (j >= 0) swap(a + i, a + j);
19 --i, --j;
20 }
21
22 printf("%s\n", a);
23 return a;
24 }
25
26 int main() {
27 //char a[] = "*ab****cd*efg**h";
28 char a[] = "**b****";
29 printf("%s\n", process(a, strlen(a)));
30 return 0;
31 }
32
posted on 2012-04-21 10:00
myjfm 閱讀(680)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
筆試+面試總結(jié)