2005年11月金山笔试题
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;
}
