2005年11月金山笔试题。编码完成下面的处理函数。函数将字符串中的字符’*’移到串的前部分，前面的非’*’字符后移，但不能改变非’*’字符的先后顺序，函数返回串中字符’*’的数量。如原始串为：ab**cd**e*12，处理后为*****abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）
int change(char *str) {
int count = 0;
for(int i=0, j=0; str[i]; i++) {
if(str[i]==’*’) {
for(j=i-1; str[j]!=’*’&&j>=0; j–)
str[j+1]=str[j];
str[j+1] = ‘*’;
count++;
}
}
return count;
}
int main(int argc, char* argv[]) {
char str[] = “ab**cd**e*12”;
printf(“str1=%sn”, str);
printf(“str2=%s, count=%d”, str, change(str));
}
// 终于得到一个比较高效的算法，一个网友提供，估计应该和金山面试官的想法一致。算法如下：
int change(char *str) {
int i,j=strlen(str)-1;
for(i=j; j>=0; j–) {
if(str[i]!=’*’) {
i–;
} else if(str[j]!=’*’) {
str[i] = str[j];
str[j] = ‘*’;
i–;
}
}
return i+1;
}
