替換空格

題目：請實現一個函數，把字符串中的每個空格替換成“%20”。例如輸入“We are happy.”,則輸出“We%20are%20happy.”。

      看到這個題目，我們首先應該想到的是原來一個空格字符，替換之後變成'%'、'2'和'0'這3個字符，因此字符串會變長。如果是在原來的字符串上做替換，那麼就有可能覆蓋修改在該字符串後面的內存。如果是創建新的字符串並在新的字符串上做替換，那麼我們可以自己分配足夠多的內存。

      在這裡介紹一種時間復雜度為O(n)的解法。 

      我們可以先遍歷一次字符串，這樣就能統計出字符串中空格的總數，並可以由此計算出替換之後的字符串的總長度。每替換一個空格，長度增加2，因此替換以後字符串的長度等於原來的長度加上2乘以空格數目。我們以字符串"We are happy."為例，"We are happy."這個字符串的長度是14（包括結尾符號'\0'），裡面有兩個空格，因此替換之後字符串的長度是18。

      我們從字符串的後面開始復制和替換。首先准備兩個指針，P1和P2。P1指向原始字符串的末尾，而P2指向替換之後的字符串的末尾（如圖（a）所示）。接下來我們向前移動指針P1，逐個把它指向的字符復制到P2指向的位置，直到碰到第一個空格為止。此時字符串包含如圖（b）所示，灰色背景的區域是做了字符拷貝（移動）的區域。碰到第一個空格之後，把P1向前移動1格，在P2之前插入字符串"%20"。由於"%20"的長度為3，同時也要把P2向前移動3格如圖（c）所示。

     我們接著向前復制，直到碰到第二個空格（如圖（d）所示）。和上一次一樣，我們再把P1向前移動1格，並把P2向前移動3格插入"%20"（如圖（e）所示）。此時P1和P2指向同一位置，表明所有空格都已經替換完畢。

參考代碼：

 
  ReplaceBlank( [],       ( == NULL && length <=            
     
      originalLength =       numberOfBlank =       i =      ([i] !=           ++  
         ([i] ==               ++  
         ++   
     
      newLength = originalLength + numberOfBlank *      (newLength >           
      indexOfOriginal =      indexOfNew =     (indexOfOriginal >=  && indexOfNew >          ([indexOfOriginal] ==                [indexOfNew --] =              [indexOfNew --] =              [indexOfNew --] =           
              [indexOfNew --] =    
         --  }

 完整代碼：

 #include<iostream>
 #include<.h>
    
 
  ReplaceBlank( [],       ( == NULL && length <=            
     
      originalLength =       numberOfBlank =       i =      ([i] !=           ++  
         ([i] ==               ++  
         ++   
     
      newLength = originalLength + numberOfBlank *      (newLength >           
      indexOfOriginal =      indexOfNew =     (indexOfOriginal >=  && indexOfNew >          ([indexOfOriginal] ==                [indexOfNew --] =              [indexOfNew --] =              [indexOfNew --] =           
              [indexOfNew --] =    
         --    
         length =   
      [length] =   
     ReplaceBlank(  
      newLength = strlen( 
        
     ( i =  ; i < newLength ; ++         cout<<     cout<<  
       }

測試代碼：

#include <stdio.h>
#include <string>

/*length 為字符數組string的總容量*/
void ReplaceBlank(char string[], int length)
{
    if(string == NULL && length <= 0)
        return;

    /*originalLength 為字符串string的實際長度*/
    int originalLength = 0;
    int numberOfBlank = 0;
    int i = 0;
    while(string[i] != '\0')
    {
        ++ originalLength;

        if(string[i] == ' ')
            ++ numberOfBlank;

        ++ i;
    }

    /*newLength 為把空格替換成'%20'之後的長度*/
    int newLength = originalLength + numberOfBlank * 2;
    if(newLength > length)
        return;

    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
    {
        if(string[indexOfOriginal] == ' ')
        {
            string[indexOfNew --] = '0';
            string[indexOfNew --] = '2';
            string[indexOfNew --] = '%';
        }
        else
        {
            string[indexOfNew --] = string[indexOfOriginal];
        }

        -- indexOfOriginal;
    }
}

void Test(char* testName, char string[], int length, char expected[])
{
    if(testName != NULL)
        printf("%s begins: ", testName);

    ReplaceBlank(string, length);

    if(expected == NULL && string == NULL)
        printf("passed.\n");
    else if(expected == NULL && string != NULL)
        printf("failed.\n");
    else if(strcmp(string, expected) == 0)
        printf("passed.\n");
    else
        printf("failed.\n");
}

// 空格在句子中間
void Test1()
{
    const int length = 100;

    char string[length] = "hello world";
    Test("Test1", string, length, "hello%20world");
}

// 空格在句子開頭
void Test2()
{
    const int length = 100;

    char string[length] = " helloworld";
    Test("Test2", string, length, "%20helloworld");
}

// 空格在句子末尾
void Test3()
{
    const int length = 100;

    char string[length] = "helloworld ";
    Test("Test3", string, length, "helloworld%20");
}

// 連續有兩個空格
void Test4()
{
    const int length = 100;

    char string[length] = "hello  world";
    Test("Test4", string, length, "hello%20%20world");
}

// 傳入NULL
void Test5()
{
    Test("Test5", NULL, 0, NULL);
}

// 傳入內容為空的字符串
void Test6()
{
    const int length = 100;

    char string[length] = "";
    Test("Test6", string, length, "");
}

//傳入內容為一個空格的字符串
void Test7()
{
    const int length = 100;

    char string[length] = " ";
    Test("Test7", string, length, "%20");
}

// 傳入的字符串沒有空格
void Test8()
{
    const int length = 100;

    char string[length] = "helloworld";
    Test("Test8", string, length, "helloworld");
}

// 傳入的字符串全是空格
void Test9()
{
    const int length = 100;

    char string[length] = "   ";
    Test("Test9", string, length, "%20%20%20");
}

int main(int argc, char* argv[])
{
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
    Test7();
    Test8();
    Test9();

    return 0;
}