题目描述：
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解题思路有：
#判断字符串是否为空，判断length是否大于0。
#记录空格的数量，没有空格直接返回原字符串。
1）考虑的问题：替换字符串是在原字符串上修改（A）还是新建字符串修改（B）
2）：
2-1
2-2
测试用例：
1)"hello world"
代码：
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 };
use pointer
编写代码时遇到的问题：
1）判断字符串（char *str）是否为空：if(str==NULL)
2）判断某个字符是否是空格（两种方法）：isspace(str[i]) 或 if(str[i]==' ')
基础知识：
1）字符串的最后一个字符是'\0'，用于判断一个字符串是否结束。
2）编写程序时，一定要考虑极端的情况，如要查找的数组是空的，字符串是空的，要赋值的对象是同一个对象等。
3）原码：一个正数，转换为二进制位就是这个正数的原码。负数的绝对值转换成二进制位然后在高位补1就是这个负数的原码
反码：正数的反码就是原码，负数的反码等于原码除符号位以外所有的位取反
补码：正数的补码与原码相同，负数的补码为 其原码除符号位外所有位取反（得到反码了），然后最低位加1
即：正数的反码和补码都与原码相同。
在计算机中，正数是直接用原码表示的，负数用补码表示！
仍存在的问题：
1）length是指什么？
猜测：限定原始字符串指针str可扩展的内存空间，即记录总长度。
经验首页