2005年11月金山笔试题
C语言
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=%s\n”, 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;
}
