一个字符替换的算法

怼烎@ 2022-06-09 04:00 155阅读 0赞

给定一个字符串把其中的空格替换成 （%） 这3个字符。

一种思路是从头开始查找，找到一个空格，就在此位置插入这3个字符，然后把后面的字符依次后移，这样虽然可以，但是后面的字符会被多次移动，并且事先不知道要插入几次，总共会插入多少字符，空间是否足够。

还有一种思路，先找出总共有多少空格，可以事先知道是否超出空间范围，计算出插入这3个字符后的最后位置，然后从原字符串的最后位置查找空格，开始替换，不是空格就依次后移。

StrReplace.cpp

\#include <iostream>

using namespace std;

void strRepace(char chArray\[\], int maxLen)\{  
if(chArray == NULL)  
return ;  
  
//计算空格数  
int numsOfSpace =0;  
int lenOfChars = 0;  
int index = 0;  
while(chArray\[index\] != '\\0')\{  
//等于空格  
if(chArray\[index\] == ' ')  
numsOfSpace++;  
lenOfChars++;  
index++;  
\}  
  
//新的结束位置,替换的字符(%)占3个字符，减去原来空格的一个字符，每替换一个空格要增加2个字符  
int lenOfCharsNew = lenOfChars + numsOfSpace\*2;  
if(lenOfCharsNew > maxLen)\{  
return;  
\}  
//开始从最后位置查找空格，并替换成（%）  
while(lenOfChars >=0 && lenOfCharsNew > lenOfChars)\{  
if(chArray\[lenOfChars\] == ' ')\{  
chArray\[lenOfCharsNew--\] = ')';  
chArray\[lenOfCharsNew--\] = '%';  
chArray\[lenOfCharsNew--\] = '(';  
\}else\{  
  
chArray\[lenOfCharsNew--\] = chArray\[lenOfChars\];  
\}  
lenOfChars--;  
\}  
  
cout << "repaced string:"<<chArray<<endl;  
\}  
  
int main()\{  
int length =100;  
char strArray\[length\] = "We love csdn.";  
int len = sizeof(strArray) / sizeof(strArray\[0\]);  
cout<< "len:" << len<<endl;  
strRepace(strArray, length);  
char strArray\_1\[length\] = " We love csdn. "; //前后各有一个空格。  
strRepace(strArray\_1, length);  
return 0;

测试结果:

PC:~/algorithm$ g++ StrReplace.cpp -o StrReplace  
PC:~/algorithm$ ./StrReplace  
len:100  
repaced string:We(%)love(%)csdn.  
repaced string:(%)We(%)love(%)csdn.(%)