05 替換空格

題目描述：

請實現一個函數，將一個字符串中的每個空格替換成“%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

class Solution {
public:
    void replaceSpace(char *str,int length) {
        //判斷特殊的情況
        if(str==NULL||length<=0)
            return;
        int totalLength=0;
        vector<int> index ;

        for (int i=0;str[i]!='\0';i++){
            totalLength++;
            //if(isspace(str[i]))
            if(str[i]==' ')
                index.push_back(i);
        }
        
        if (index.empty()) //判斷是否有空格
            return;
        else{
            int spaceNum = index.size();
            char* newstr = new char [totalLength+spaceNum*2+1]; //用不用加1？

            for(int i=0,k=0;i<=totalLength;i++) // 判斷的時候有等于（<=）'\0'也要拷貝
            {
                if(i==index[k]){
                    *newstr++='%';
                    *newstr++='2';
                    *newstr++='0';
                    str++;
                    k++;
                }
                else
                    *newstr++=*str++;
            }
            newstr=newstr-(totalLength+spaceNum*2)-1;
            str=str-totalLength-1;
            for(int j=0;j<=(totalLength+spaceNum*2);j++){
                str[j]=newstr[j];
            }
        }
    }
};

注意：

1」主體代碼line23-34執行結束后，newstr指針內存儲修改后的代碼。但該段代碼執行后指針指向'\0'的后一位（因此要多減一個1），要根據字符串長度將指針移回原始位置。（不要忘記指針移動）

2」要修改的是str，因此將newstr的值拷貝給str，函數運行結束后，newstr的被釋放（局部作用域）。

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

---

B 原始字符串+從后往前復制(使用數組) 運行時間：5ms 占用內存：476k

class Solution {
public:
    void replaceSpace(char *str,int length) {
        if (str==NULL||length<=0)  //應該使用||而不是&&，因為兩個中任意一個成立，均不用在判斷
            return;
        int totalLen = 0,spaceNum=0;
        for(int i=0;str[i]!='\0';i++){
            totalLen++;
            if(str[i]==' ')
                spaceNum++;
        }
        int totalNew = totalLen +2*spaceNum;
        //注意：c++中u取反使用！，而不是～（～1=-2，結果是true）
        if(!spaceNum||totalNew>length) //totalNew>length（應該是大于符號）
            return;
        for(int k = totalLen,j=totalNew;k>=0;k--,j--){
            if(k==j)
                return;
            if(str[k]==' '){
                str[j]='0';
                str[--j]='2';
                str[--j]='%';
            }
            else{
                str[j]=str[k];
            }
        }
    }
};

注意：

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 原始字符串+從后往前復制（使用指針）

class Solution {
public:
    void replaceSpace(char *str,int length) {
         if(str==NULL||length<=0)
             return ;
         int CountOfBlanks=0;
         int Originallength=0;
         for(int i=0;str[i]!='\0';i++)
             {
             Originallength++;
             if(str[i]==' ')
                 ++CountOfBlanks;
         }
         int len =Originallength+2*CountOfBlanks;
         if(len+1>length||!CountOfBlanks) //即：len>=length
             return ;
          
         char*pStr1=str+Originallength;//復制結束符‘\0’
         char*pStr2=str+len;
        while(pStr1<pStr2)
            {
            if(*pStr1==' ')
                {
                *pStr2--='0';
                *pStr2--='2';
                *pStr2--='%';    
            }
            else
             {
                 *pStr2--=*pStr1;
            }
            --pStr1;
        }
    }
};

1」當兩個指針相等的時候，終止。（此時已經沒有空格了）

---

?

編寫代碼時遇到的問題：

?1）判斷字符串（char *str）是否為空：if(str==NULL)

?2）判斷某個字符是否是空格（兩種方法）：isspace(str[i]) 或 if(str[i]==' ')

?

基礎知識：

1）字符串的最后一個字符是'\0'，用于判斷一個字符串是否結束。

2）編寫程序時，一定要考慮極端的情況，如要查找的數組是空的，字符串是空的，要賦值的對象是同一個對象等。

3）原碼：一個正數，轉換為二進制位就是這個正數的原碼。負數的絕對值轉換成二進制位然后在高位補1就是這個負數的原碼

???? 反碼：正數的反碼就是原碼，負數的反碼等于原碼除符號位以外所有的位取反

???? 補碼：正數的補碼與原碼相同，負數的補碼為 其原碼除符號位外所有位取反（得到反碼了），然后最低位加1

???? 即：正數的反碼和補碼都與原碼相同。

??????????? 在計算機中，正數是直接用原碼表示的，負數用補碼表示！

?

仍存在的問題：

1）length是指什么？

?猜測：限定原始字符串指針str可擴展的內存空間，即記錄總長度。

?

# prac 02

class Solution {
public:void replaceSpace(char *str,int length) {cout <<str<<endl;int num_sapce = 0;for(int i = 0;i<length;i++)if (str[i]==' ')num_sapce+=1;//if (num_sapce<1)//return str;int new_length = length + 2*num_sapce;char* new_str = new char[new_length];for(int old_index = length-1,new_index =new_length -1; old_index>=0;)if (str[old_index]==' '){old_index-=1;new_str[new_index--]='0';new_str[new_index--]='2';new_str[new_index--]='%';}else {new_str[new_index]=str[old_index];old_index-=1;new_index-=1;}for (int k = 0;k<new_length;k++){str[k]=new_str[k];}}
};
//題目要求：在原來的字符串上修改（即字符串首地址不變）
//因此，要把字符串在一次賦值回去，可以選擇不生成新的變量，在原地址上修改。