欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

05替换空格

程序员文章站 2022-07-01 23:38:33
题目描述: 请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 解题思路有: #判断字符串是否为空,判断length是否大于0。 #记录空格的数量,没有空格直接返回原字符串。 1)考虑的问题: ......

题目描述:

请实现一个函数,将一个字符串中的每个空格替换成“%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

05替换空格
 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

05替换空格
 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 原始字符串+从后往前复制(使用指针

05替换空格
 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 };
use point

1」当两个指针相等的时候,终止。(此时已经没有空格了)


 

编写代码时遇到的问题:

 1)判断字符串(char *str)是否为空:if(str==null)

 2)判断某个字符是否是空格(两种方法):isspace(str[i]) 或 if(str[i]==' ')

 

基础知识:

1)字符串的最后一个字符是'\0',用于判断一个字符串是否结束。

2)编写程序时,一定要考虑极端的情况,如要查找的数组是空的,字符串是空的,要赋值的对象是同一个对象等。

3)原码:一个正数,转换为二进制位就是这个正数的原码。负数的绝对值转换成二进制位然后在高位补1就是这个负数的原码

     反码:正数的反码就是原码,负数的反码等于原码除符号位以外所有的位取反

     补码:正数的补码与原码相同,负数的补码为 其原码除符号位外所有位取反(得到反码了),然后最低位加1

     即:正数的反码和补码都与原码相同。

            在计算机中,正数是直接用原码表示的,负数用补码表示!

 

仍存在的问题:

1)length是指什么?

 猜测:限定原始字符串指针str可扩展的内存空间,即记录总长度。