剑指offer剖析__空格替换字符串问题

快来打我* 2022-08-22 03:45 127阅读 0赞

**问题：在"we are happy"这个字符串中，将所有的空格替换成字符串%20.**

**分析：如果我们不定义一个新的字符数组，就在原字符数组中进行替换，要将一个字节的空格替换成三个字节的字符数组%20，这会产生数组的越界访问，如果允许我们开辟一个新的空间来存放替换后的字符串，则问题将会变得非常简单。** **设置两个指针分别指向新旧字符串首元素，遍历原字符串，如果碰到空格就在新字符串上填入“%20”，否则就复制元字符串上的内容。**

#include <stdio.h>
    #include <string.h>
    #include <assert.h>
    char *Instead(const char *strSrc, char *strDes)
    {
    assert(strSrc != NULL && strDes != NULL);
    char *p=strDes;
    char *pDes;
    const char *pSrc;
    pDes = strDes;
    pSrc = strSrc;
    
    while (*pSrc != '\0')
    {
    if (*pSrc != ' ')
    {
    *pDes++ = *pSrc;    //拷贝原字符串内容
    
    }
    else
    {
    memcpy(pDes, "%20", 3);    //遇到空格在替换后的那个字符数组中插入%20
    pDes += 3;
    }
    pSrc++;
    }
    *pDes = '\0';
    return p;
    }
    
    int main()
    {
    char s[] = "we are happy";
    char s2[20];
    char *p;
    p = Instead(s, s2);
    printf("%s",p);
    return 0;
    }

**但是如果面试官要求 在原先的字符串上操作，并且保证原字符串有足够长的空间来存放替换后的字符串，那么我们就得另想方法。**

**如果从前往后替换字符串，那么保存在空格后面的字符串肯定会被覆盖，那么我们就考虑从后往前进行替换。**

**1.首先遍历原字符串，找出字符串的长度以及其中的空格数量，**

**2.根据原字符串的长度和空格的数量我们可以求出最后新字符串的长度。**

**3.设置两个指针point1和point2分别指向原字符串和新字符串的末尾位置。**

**4.如果point1指向内容不为空格，那么将内容赋值给point2指向的位置，如果point1指向为空格，那么从point2开始赋值“02%”**

**5.直到point1==point2时表明字符串中的所有空格都已经替换完毕。**

**代码如下：**

char* Instead1(char *str, int sz,int len)
    {
                     char *pstr = str ;
                     int blank_count = 0;
                     int k;
                     int point1, point2;
                     while (*pstr)
                    {
                                     if (*pstr == ' ' )
                                                    blank_count++;
                                    pstr++;
                    }
                    k = len + blank_count *2;
                    point1 = len;
                    point2 = k;
                     str[k + 1] = '\0' ;
                     while (point1 >= 0 && point2 >= point1)
                    {
                                     if (str [point1] != ' ')
                                                     str[point2--] = str [point1--];
                                     else
                                    {
                                                     str[point2--] = '0' ;
                                                     str[point2--] = '2' ;
                                                     str[point2--] = '%' ;
                                                    point1--;
                                    }
                                    
                    }
                     return str ;
    }
    
    int main()
    {
                     char s[20] = "we are happy" ;
                     char *p;
                    p = Instead1(s, sizeof(s)/sizeof (s[0]),strlen(s));
                    printf( "%s", p);
                     return 0;
    
    }

博主初学小白，欢迎大家积极给出意见，一起讨论，一起进步。