给定一个字符串，仅包含26个字母以及'*'字符，要求将所有'*'字符移动到字符串前面，并且保证原字母顺序不变。
开始想这不就是简单的一遍快排么，后来仔细想了想不太对啊，一遍快排就把字母顺序打乱了，后来又想了想，还是有时间复杂度O(N)，空间复杂度O(1)的算法的，大体思想就是i从后向前扫描，找到第一个'*'，然后j在i的位置向前扫描，找到第一个字母，然后将str[i]与str[j]交换，之后i--，j--,继续前面的过程，直到j<0为止。这样做之所以复杂度为O(N)是因为i每次都是递减的，j同样也是递减的，这样i最多走N步，j也同样最多走N步，因此复杂度肯定是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 阅读(643)
评论(0) 编辑 收藏 引用 所属分类:
笔试+面试总结