88.2005年11月金山笔试题。编码完成下面的处理函数。

函数将字符串中的字符'*'移到串的前部分，

前面的非'*'字符后移，但不能改变非'*'字符的先后顺序，函数返回串中字符'*'的数量。

如原始串为：ab**cd**e*12， 处理后为*****abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）

思路：

*都是一样的，所以只要知道有多少*然后最后的时候补上就好了。现在首先要做的就是将所有非*的字符移动到数组的后面，这就简单了。

贴上代码：

int movStar(char * p, int n){ char * q1 = p+(n-1), *q2 = p+(n-1); while(q1>=p) {  if(*q1 != '*')   *q2-- = *q1;  q1--; } int nRet = q2 - q1; while(q2>=p) {  *q2-- = '*'; } return nRet;}

可是，我最初的想法可复杂多了。因为我开始的时候，只是想到了要进行交换位置，而没想到要直接覆盖。而且是要移动*和非*字符，时间复杂度差不多O(n^2)了都。自己太年轻了。。不过到现在也做了这么多的面试题目了。我自己的感觉是，有很多题目都是十分巧妙的。如果初次见的话，一般很难直接想到最优的解法。当然是大牛的话就不多说了。。。我觉得无论是面试题，还是将来实际工作中遇到的问题，首先第一步当然是要实现之，先不考虑时间和空间的限制。如果连最基本的功能的实现都做不到，什么都是空谈。其次才是再考虑时间和空间的问题，然后进一步优化得到比较优化的解。。。恩恩。