【5】字符串空格替换（时间复杂度为O(n)）

Dear 丶 2022-05-27 05:47 128阅读 0赞

## 面试题5：替换空格 ##

**题目：**请实现一个函数，把字符串中的每个空格替换成”%20”。例如输入“We are happy.”，  
则输出“We%20are%20happy.”。

**分析：**  
（1）如果按照普通思路，那么一个空格换为%20，相当于一个位置换三个，就需要将出现空格的地方向后移动，第一次出现空格后的单词移动一次，第二次出现空格的后有一个单词需要移动两次。。。。以此类推，显然这种方式的时间复杂为O(N^2),那么我们不妨换个角度思考；

（2）利用循环，遍历一遍数组，找到字符串末尾的位置的同时记录空格的个数，一旦知道空格的个数，那么，就可以得到转换后数组的总长度，我们可以利用两个指针，一个指向新数组的末尾p2，一个指向原数组的末尾p1，当p1大于等于零，并且两指针没有在同一个位置上时，循环继续；下面是具体实现代码；  
**代码实现：**

#include <cstdio>
    #include <cstring>
    
    void ReplaceBlank(char* string,int length)
    {
        if(string == NULL ||length<= 0)
        {
            printf("参数传入错误\n");
            return ;
        }
        int count = 0;
        int countofblank = 0;
        for(int i = 0; string[i]!= '\0';++i )
        {
            ++count ;
            if(string[i] == ' ')
            {
                ++countofblank ;
            }
        }
        int newlength = count+ countofblank*2;
        if(newlength > length)
        {
            return ;
        }
        int pcount = count;
        int pcountblank = newlength;
        while(pcount>= 0 && pcountblank > pcount)
        {
            if(string[pcount] == ' ')
            {
                string[pcountblank--] = '0';
                string[pcountblank--] ='2';
                string[pcountblank--] ='%';
    
            }
            else
            {
                string[pcountblank--] = string[pcount];
            }
            --pcount;
        }
    
    }
    
    
    
    //================测试代码=============================================
    //*********************************************************************
    //=====================================================================
    void test(char arr[],int len)
    {
        if(arr ==NULL ||len <= 0)
        {
            printf("arr ==NULL ||len <= 0参数传入错误\n");
            printf("\n");
            return ;
        }
        printf("替换前arr = %s\n",arr);
        printf("数组的长度len 为： %d\n",len);
        ReplaceBlank( arr, len );
        printf("替换后arr = %s\n",arr);
        printf("\n");
    }
    
    //==========1.正常测试：空格在句子中间 " we are happy."=================
    void test1()
    {
        const int num = 100;
        char arr[num]="we are happy.";
        int len = num;
        test(arr,len);
    }
    //==========2.正常测试：空格在句子开头 "    wearehappy."=================
    void test2()
    {
        const int num = 100;
        char arr[num]="    wearehappy.";
        int len = num;
        test(arr,len);
    }
    
    //==========3.正常测试：空格在句子末尾 "wearehappy.    "=================
    void test3()
    {
        const int num = 100;
        char arr[num]="wearehappy.    ";
        int len = num;
        test(arr,len);
    }
    //============4.有两个挨在一起的空格"we  are happy."============
    void test4()
    {
        const int num =100;
        char arr[num]="we  are happy.";
        int len = num;
        test(arr,len);
    }
    
    //============5.全是空格"             "============
    void test5()
    {
        const int num = 100;
        char arr[num]="             ";
        int len = num;
        test(arr,len);
    }
    
    //============6.传入为NULL"============
    void test6()
    {
    
        test(NULL,0);
    }
    
    //=================7.传入空字符串=========
    void test7()
    {
        const int num = 100;
        char arr[num]="";
        int len = num;
        test(arr,len);
    }
    int main()
    {
        test1();
        test2();
        test3();
        test4();
        test5();
        test6();
        test7();
        return 0;
    }

**测试结果：**  
![这里写图片描述][70]

[70]: /images/20220527/3db55d0350ed40798c61e2abe35b1e4a.png