【剑指offer】面试题05 - 替换空格

我会带着你远行 2022-11-03 01:43 11阅读 0赞

### 文章目录 ###

*  面试题 5 ：替换空格
 *   *  解法一：使用STL中string解决
     *  解法二：多指针移动法

# 面试题 5 ：替换空格 #

`题目描述`

> 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

`示例 1`

> 输入
> 
>     "We Are Happy"
> 
> 输出
> 
>     "We%20Are%20Happy"

## 解法一：使用STL中string解决 ##

> 思路：
> 
> 1.  使用 find 函数找到空格字符所在的 pos 位置
> 2.  使用 erase 函数删除 pos 位置上的空格字符
> 3.  使用 insert 函数将 “%20” 放在 pos 位置上

string replaceSpace(string s) { 
        int pos;
        while((pos = s.find(' ')) != string::npos)
        { 
            s.erase(pos, 1);
            s.insert(pos, "%20");
        }
        return s;
    }

## 解法二：多指针移动法 ##

> 思路：
> 
> 1.  遍历一次字符串统计有spaceCount个空格
> 2.  重新开辟一个sizeof(s)+spaceCount \* 2空间的新空间，将源字符串内容复制到新空间中，并让s指向新空间
> 3.  用p指针从后往前开始寻找空格，找到空格后，将空格后的所有内容后移两个位置，给%20留出两个位置
> 4.  此时，p指向空格，再加上移动让出来的两个位置，恰好可以赋值成%20
> 5.  按照此思路 p 继续向前寻找空格，直到 p 到达字符串起始位置

char* replaceSpace(char* s ) { 
        if (s == NULL) return s;    // 空指针
        // 1. 统计 s 中有多少个空格字符
        int spaceCount = 0;
        int sLeng = strlen(s);
        for (int i = 0; i < strlen(s); i++)
            if (s[i] == ' ') spaceCount++;
        if (spaceCount == 0) return s;    // 原字符串无空格字符
        // 按照空格字符个数对原字符进行扩容
        char* s_tmp = (char*)malloc(sizeof(s)+spaceCount * 2);
        if (s_tmp == NULL) return s;    // 内存不够无法扩容
        strcpy(s_tmp, s);
        s = s_tmp;
        s_tmp = NULL;	// 此时 s 中保存的是扩容之后的原字符串加多余容量
    
        int totalLength = strlen(s) + spaceCount * 2 + 1;	// 获取扩容后的字符串总长度
        s[totalLength - 1] = '\0';	//将末尾放置一个\0
        totalLength--;	
    
        /* end：指在字符串字母的末尾 p:遍历字符串寻找空格 begin：当p找到空格时，begin指到空格后面的字符 */
        for (int p = sLeng, end = sLeng; p >= 0; p--)
        { 
            if (s[p] == ' ')
            { 
                int begin = p + 1;
                // 将 begin 与 end之间的所有字符后移两位，给%20赋值在空格处让出位置
                for (int tmp = end; tmp >= begin; tmp--)
                    s[tmp + 2] = s[tmp];
                end += 2;
                s[p] = '%';
                s[p + 1] = '2';
                s[p + 2] = '0';
            }
        }
        return s;
    }