劍指offer系列——劍指 Offer 05. 替換空格（C語言）

??前面的話??

大家好！博主開辟了一個新的專欄——劍指offer，我要開始刷題了！這個專欄會介紹《劍指offer》書上所有的面試編程題，并且會分享一些我的刷題心得，由于博主水平有限，如有錯誤，歡迎指正，如果有更好的解題思路和演算法可以分享給博主哦！一起加油！一起努力！

📒博客主頁：未見花聞的博客主頁
🎉歡迎關注🔎點贊👍收藏??留言📝
📌本文由未見花聞原創，CSDN首發！
??堅持和努力一定能換來詩與遠方！
💭參考書籍：📚《劍指offer第1版》，📚《劍指offer第2版》
💬參考在線編程網站：🌐牛客網🌐力扣
🙏作者水平很有限，如果發現錯誤，一定要及時告知作者哦！感謝感謝！
博主的碼云gitee，平常博主寫的程式代碼都在里面，

??劍指 Offer 05. 替換空格??

請實作一個函式，把字串s中的每個空格替換成"%20"，

💡示例：

輸入：s = "We are happy."
輸出："We%20are%20happy."

💡限制：

0 <= s 的長度 <= 10000

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

??解題思路??

在網路編程中，如果URL引數中含有特殊字符，如空格、#等，則可能導致服務器端無法獲得正確的引數值，我們需要將這些特殊符號轉換成服務器可以識別的字符，轉換的規則是在%后面跟上ASCII碼的兩位十六進制的表示，比如空格的ASCII碼是32，即十六進制的0x20，因此空格被替換成"%20"，再比如#的ASCII碼為 35，即十六進制的0x23，它在 URL中被替換為"%23"，

看到這個題目，我們首先應該想到的是原來一個空格字符，替換之后變成'%'、'2'和'0'這 3 個字符，因此字串會變長，如果是在原來的字串上進行替換，就有可能覆寫修改在該字串后面的記憶體，如果是創建新的字串并在新的字串上進行替換，那么我們可以自己分配足夠多的記憶體，由于在力扣在線平臺上C語言提供的是一個常量的字串，不能再原地進行修改，所以本文采用創建新的字串變數并在上面進行替換，

要創建一個新的字串變數，就考慮申請多少的空間，假設輸入的字串長度為len，你可以不經思考地申請一塊3*len + 1大小的空間，因為當這個字串全部是空格時替換后的長度就變為了3*len，考慮到還有一個\0，所以替換后的字串長度最大為3*len+1（包括\0），但是對于新空間的開辟，堅持“用多少開多少的原則”，我們可以先遍歷一遍原字串，計算出空格字符的數量cnt，原來是一個字符替換后變為三個字符，相當于增加了倆個字符，再加上最后的\0，所以需要給替換后的新字串長度開辟的空間為len + cnt*2 + 1，

開辟好足夠的空間后，就是字串的替換了，
對于這道題，博主給出3種解題方法：
方法1： 先將輸入的字串拷貝，然后在拷貝的字串變數上進行替換修改，對該字串進行遍歷，遇到空格將空格后的所有字符向后移動兩位，然后將空格替換為%20，

時間復雜度： O(N²)

方法2： 先將輸入的字串拷貝，然后在拷貝的字串變數上進行替換修改，與方法1不同的是這次準備兩個指標，一個指向原來字串\0的位置記為left，另一個指向新申請字串變數中將空格替換后\0的位置記為right，（這就表示新申請的空間要剛剛合適或者需要計算空格數量得到新的\0的位置）然后將left指向的字符移動到right所指向的空間，從后往前遍歷，當left遇到空格時將right向前移動3次，插入%20，直到left = right，當兩個指標相等時，表示字串替換完畢，

時間復雜度： O(N)

方法3： 邊進行字串拷貝邊進行空格替換，對新舊兩個字串同時進行遍歷，如果原來的字串遇到空格，就在新字串后插入%20，

時間復雜度： O(N)

編程語言：C語言
在線編程平臺：力扣

//方法1
char* replaceSpace(char* s){
    int len = strlen(s);
    int m = 0;
    int cnt = 0;
    for (m = 0; m < len; m++)
    {
        if (*(s + m) == ' ')
        {
            cnt++;
        }
    }
    //char* str = (char*)malloc(sizeof(char)*3*len + 1);//申請足夠的空間
    char* str = (char*)malloc(sizeof(char) * (len + cnt * 2 + 1));//申請足夠多的空間
    strcpy(str,s);//拷貝字串
    int i = 0;
    char rep[3] = {'%', '2', '0'};
    while (*(str + i) != '\0')
    {
        int right = len;
            if (*(str + i) == ' ')
            {
                len = len + 2;
                while (right > i)
                {
                    *(str + right + 2) = *(str + right);//移動空格后元素
                    right--;
                }
                int j = 0;
                while(right < i + 3)
                {
                    *(str + right)  = *(rep + j);//替換空格
                    right++;
                    j++;
                }
                i += 2;
            }
            i++;
    }
    return str;
}

//方法2
char* replaceSpace(char* s){
    int len = strlen(s);
    int m = 0;
    int cnt = 0;
    for (m = 0; m < len; m++)
    {
        if (*(s + m) == ' ')
        {
            cnt++;
        }
    }
    char* str = (char*)malloc(sizeof(char) * (len + cnt * 2 + 1));//申請足夠多的空間
    int left = len;
    int right = len + cnt*2;
    strcpy(str,s);//拷貝字串
    while(left >= 0 && left < right)
    {
        if (*(str + left) == ' ')
        {
            *(str + right) = '0';
            right--;
            *(str + right) = '2';
            right--;
            *(str + right) = '%';
            right--;
        }
        else
        {
            *(str + right) = *(str + left);
            right--;
        }
        left--;
    }
    return str;
}

//方法3
char* replaceSpace(char* s){
    int len = strlen(s);
    int m = 0;
    int cnt = 0;
    for (m = 0; m < len; m++)
    {
        if (*(s + m) == ' ')
        {
            cnt++;
        }
    }
    char* str = (char*)malloc(sizeof(char) * (len + cnt * 2 + 1));//申請足夠多的空間
    int i = 0;
    int j = 0;
    for (i = 0; i < len; i++, j++)
    {
        *(str + j) = *(s + i);//拷貝字符
        if (*(s + i) == ' ')
        {
            *(str + j) = '%';
            j++;
            *(str + j) = '2';
            j++;
            *(str + j) = '0';//遇到空格則替換字符
        }
    }
    *(str + j) = '\0';
    return str;
}