黑马程序员技术交流社区

标题: 字符移动 [打印本页]
作者: 薛旻    时间: 2014-3-3 17:25
标题: 字符移动
     编码完成下面的处理函数。函数将字符串中的字符“*”移动到串的前部分，前面的非“*”字符后移，但不能改变非“*”字符的先后顺序，函数返回串中字符“*”的数量。如原始串为：ab**cd**e**12，处理后为******abcde12，且函数返回值为5（要求使用尽量少的时间和辅助空间）
     贴出自己程序的运行时间。
作者: e.c    时间: 2014-3-3 19:35
获取长度len1，删除所有*
获取长度len2，在开始位置添加*
返回len2-len1
作者: Amorvos    时间: 2014-3-3 22:44
楼主我给你写了一个，你看看是不是你要的，你可以自己再改一下

  2. public class Number {
  3.         public static void main(String[] args) {
  4.                 StringBuilder sb = new StringBuilder("ab**cd**e**12");
  5.                 StringBuilder key = new StringBuilder(sb.length());
  6.                 int num = 0;
  7.                 for (int i = 0; i < sb.length(); i++) {
  8.                         if ('*' != sb.charAt(i)) {
  9.                                 key.append(sb.charAt(i));
  10.                         } else {
  11.                                 num++;
  12.                         }
  13.                 }
  14.                 key = key.reverse();
  15.                 for (int i = 0; i < num; i++) {
  16.                         key.append('*');
  17.                 }
  18.                 System.out.println(key.reverse());
  19.                 System.out.println(num);

  21.         }

  23. }
复制代码
作者: syw02014    时间: 2014-3-4 09:02
给你四种方法：第一种：
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <limits>

  5. using namespace std;
  6. void swap_star(char& a, char& b){
  7.         char t;
  8.         t = a;
  9.         a = b;
  10.         b = t;
  11. }


  14. int main()
  15. {
  16.         char star[] = "ab**cd**e*12";
  17.         cout << " star : " << star << endl;
  18.         int sz = sizeof(star);
  19.         int starpos = sz - 2;
  20.         int nonstar = sz - 2;
  21.         int cnt = 0;
  22.         while(starpos >= 0 && nonstar >= 0){
  23.                 while(star[starpos] != '*' && starpos > 0){ //从末位开始查找‘*’的索引
  24.                         --starpos;
  25.                 }
  26.                 if(starpos > 0){  // 计算非‘*’字符的起始索引，与‘*’一样，倒序搜索，因为要求不改变原非‘*’字符的顺序
  27.                         if(starpos > nonstar){
  28.                                 nonstar = nonstar - 1;
  29.                         }else{
  30.                                 nonstar = starpos - 1;
  31.                         }
  32.                 }else{  // 如果‘*’索引到了 0， 则说明已交换顺序完毕
  33.                         break;
  34.                 }
  35.                 while(star[nonstar] == '*' && nonstar > 0){ // 找到待交换非‘*’字符索引
  36.                         --nonstar;
  37.                 }
  38.                 if(star[nonstar] != '*' && nonstar >= 0){
  39.                         swap_star(star[starpos],star[nonstar]);                       
  40.                         starpos = starpos - 1;
  41.                 }else{
  42.                         cnt = starpos + 1;  // 交换完毕，‘*’字符的索引是从0开始的最后一个‘*’字符的索引
  43.                         break;
  44.                 }
  45.         }

  47.         cout << "finally : " << star <<  " star number : " << cnt << endl;

  49.         return 0;
  50. }
复制代码
第二种：
  1. #include <iostream>
  2. using namespace std;

  4. void movStar(char* p)
  5. {
  6.         int len = strlen(p);
  7.         int i;
  8.         for (i = len-1; p[i]!='*';i--);        //从后向前找到第一个'*'，然后开始覆盖。
  9.         int j = i;
  10.         for (;i >= 0; i--)
  11.         {
  12.                 if (p[i]!='*')
  13.                 {
  14.                         p[j--]=p[i];
  15.                 }
  16.         }
  17.         while(j>=0)
  18.         {
  19.                 p[j--]='*';
  20.         }
  21. }

  23. int main()
  24. {
  25.         char p[]="ab**cd**e*12";  
  26.         cout<<p<<endl;
  27.         movStar(p);
  28.         cout<<p<<endl;
  29. }
复制代码
第三种：

  1. #include <iostream>
  2. using namespace std;

  4. void swap(char* p, char* q)
  5. {
  6.         int temp = *p;
  7.         *p = *q;
  8.         *q = temp;
  9. }

  11. int movStar(char* p, int n)
  12. {
  13.         char* q1 = p+n-1, *q2 = p+n-1;
  14.         while (q1 > p)
  15.         {
  16.                 while (*q2 != '*')
  17.                         q2--;
  18.                 q1 = q2-1;
  19.                 while (*q1 == '*')
  20.                         q1--;
  21.                 swap(q1, q2);
  22.                 cout<<p<<endl;
  23.         }
  24.         return q2-q1+1;
  25. }


  28. int main()
  29. {
  30.         char p[]="ab**cd**e*12";
  31.         int cnt = movStar(p,strlen(p));
  32.         cout<<"after movStar..."<<endl;
  33.         cout<<"number of * is: "<<cnt<<endl;
  34.         cout<<p<<endl;
  35. }
复制代码
第四种：
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. void swap(char* str,int i,int j)
  5. {
  6.         if(str[i] != str[j])
  7.         {
  8.                 str[i]^=str[j];
  9.                 str[j]^=str[i];
  10.                 str[i]^=str[j];
  11.         }
  12. }
  13. int departStars(char *str)
  14. {
  15.         //k停留在其它字母上
  16.         int len,i,k,cout=0;
  17.         if(str==NULL) return 0;
  18.         if((len=strlen(str)) < 1) return 0;
  19.         i=k=len-1;
  20.         while(i>=0)
  21.         {
  22.                 if(str[i]!='*')
  23.                 {
  24.                         swap(str,i--,k--);
  25.                 }
  26.                 else
  27.                 {
  28.                         --i;
  29.                         ++cout;
  30.                 }
  31.         }
  32.         return cout;
  33. }
  34. int main(void) {
  35.         char str[]="*ABCD*D*BSD**d**";
  36.         printf("%d %s",departStars(str),str);
  37.         return 0;
  38. }
复制代码





欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2