首页 > > 程序设计 > C/C++ >

05 替换空格

2018-11-20 03:15:09来源：博客园阅读 ()

题目描述：

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

解题思路有：

#判断字符串是否为空，判断length是否大于0。

#记录空格的数量，没有空格直接返回原字符串。

1）考虑的问题：替换字符串是在原字符串上修改（A）还是新建字符串修改（B）

2）在当前字符串替换，怎么替换才更有效率：

2-1 从前往后替换，后面的字符要不断往后移动，要多次移动，所以效率低下（在原字符串改动时）

2-2 从后往前，先计算需要多少空间，然后从后往前移动，则每个字符只为移动一次，这样效率更高一点。

测试用例：

1）输入中包含空格（空格位于最前方，最后方，中间，有连续多个空格）

"hello world"

2）输入中没有空格

3）特殊输入测试（字符串是nullptr指针；字符串是空字符串）

代码：

A 新建字符串+从前往后复制运行时间：3ms 占用内存：400-600k

 1 class Solution {
 2 public:
 3     void replaceSpace(char *str,int length) {
 4         //判断特殊的情况
 5         if(str==NULL||length<=0)
 6             return;
 7         int totalLength=0;
 8         vector<int> index ;
 9 
10         for (int i=0;str[i]!='\0';i++){
11             totalLength++;
12             //if(isspace(str[i]))
13             if(str[i]==' ')
14                 index.push_back(i);
15         }
16         
17         if (index.empty()) //判断是否有空格
18             return;
19         else{
20             int spaceNum = index.size();
21             char* newstr = new char [totalLength+spaceNum*2+1]; //用不用加1？
22 
23             for(int i=0,k=0;i<=totalLength;i++) // 判断的时候有等于（<=）'\0'也要拷贝
24             {
25                 if(i==index[k]){
26                     *newstr++='%';
27                     *newstr++='2';
28                     *newstr++='0';
29                     str++;
30                     k++;
31                 }
32                 else
33                     *newstr++=*str++;
34             }
35             newstr=newstr-(totalLength+spaceNum*2)-1;
36             str=str-totalLength-1;
37             for(int j=0;j<=(totalLength+spaceNum*2);j++){
38                 str[j]=newstr[j];
39             }
40         }
41     }
42 };

new array + front to back

注意：

1」主体代码line23-34执行结束后，newstr指针内存储修改后的代码。但该段代码执行后指针指向'\0'的后一位（因此要多减一个1），要根据字符串长度将指针移回原始位置。（不要忘记指针移动）

2」要修改的是str，因此将newstr的值拷贝给str，函数运行结束后，newstr的被释放（局部作用域）。

3」if (str==NULL||length<=0)，使用||而不是&&。

B 原始字符串+从后往前复制(使用数组) 运行时间：5ms 占用内存：476k

 1 class Solution {
 2 public:
 3     void replaceSpace(char *str,int length) {
 4         if (str==NULL||length<=0)  //应该使用||而不是&&，因为两个中任意一个成立，均不用在判断
 5             return;
 6         int totalLen = 0,spaceNum=0;
 7         for(int i=0;str[i]!='\0';i++){
 8             totalLen++;
 9             if(str[i]==' ')
10                 spaceNum++;
11         }
12         int totalNew = totalLen +2*spaceNum;
13         //注意：c++中u取反使用！，而不是～（～1=-2，结果是true）
14         if(!spaceNum||totalNew>length) //totalNew>length（应该是大于符号）
15             return;
16         for(int k = totalLen,j=totalNew;k>=0;k--,j--){
17             if(k==j)
18                 return;
19             if(str[k]==' '){
20                 str[j]='0';
21                 str[--j]='2';
22                 str[--j]='%';
23             }
24             else{
25                 str[j]=str[k];
26             }
27         }
28     }
29 };

ori array + back to front

注意：

1」C++中，取反使用！（即int spaceNum =1; !spaceNum; 结果是0）

而～spaceNum 结果是-2（true）

2」～20=-21，规律如下：

20的原码：0001 0100

～操作：1110 1011（逐位取反）这是一个负数，负数在计算机中以补码形式存储。因此该序列是一个负数的补码。

该负数的补码：1110 1011

该负数的反码：1110 1010 （减1）

该负数的原码：1001 0101（首位是符号位，-1）（0010101为21）。最后结果为-21。

C 原始字符串+从后往前复制（使用指针）

 1 class Solution {
 2 public:
 3     void replaceSpace(char *str,int length) {
 4          if(str==NULL||length<=0)
 5              return ;
 6          int CountOfBlanks=0;
 7          int Originallength=0;
 8          for(int i=0;str[i]!='\0';i++)
 9              {
10              Originallength++;
11              if(str[i]==' ')
12                  ++CountOfBlanks;
13          }
14          int len =Originallength+2*CountOfBlanks;
15          if(len+1>length||!CountOfBlanks) //即：len>=length
16              return ;
17           
18          char*pStr1=str+Originallength;//复制结束符‘\0’
19          char*pStr2=str+len;
20         while(pStr1<pStr2)
21             {
22             if(*pStr1==' ')
23                 {
24                 *pStr2--='0';
25                 *pStr2--='2';
26                 *pStr2--='%';    
27             }
28             else
29              {
30                  *pStr2--=*pStr1;
31             }
32             --pStr1;
33         }
34     }
35 };