本文共 1698 字，大约阅读时间需要 5 分钟。

题目描述

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

题目分析

字符串存在数组中，一个空格替换后需要多出2个存储位置，我们加以分析，会有以下两种情况：

case1：不在原来的字符串上替换

如果原来的字符串的存储空间非常有限，我们需要另外开辟一个足够大的数组，将原来数组里的内容复制过来，并在遇到空格时换成指定字符，这样的话需要比较多的额外空间。

为避免浪费更多的存储空间，我们应先遍历字符串，以找到字符串中空格的个数，从而申请额外的存储空间（替换一个空格需要多出2个存储位置），实现代码如下：

class Solution {
   public:	void replaceSpace(char *str,int length) {
   	    int i,j,count=0;	    for(i=0;i

运行时间：4ms占用内存：612k

可以看出这种解法对空间的要求比较高

case2：在原来的字符串上替换

当初始给定的字符串数组有比较多的内存空间时，有两种解法可供参考：

解法1：常规解法

遇到空格就替换，然后将后面的依次挪过去（挪2位），这样的话时间复杂度会特别大，不推荐

class Solution {
   public:	void replaceSpace(char *str,int length) {
           int i,j,count;	    for(i=0,j=0;i
   
    i+2;j--){
                       str[j]=str[j-2];                }                str[i]='%';                str[++i]='2';                str[++i]='0';            }	    }    }};
   

运行时间：4ms占用内存：492k

解法2：低复杂度解法

先遍历一遍数组，计算出有多少个空格，然后我们就可以知道数组里每个元素最终的存储位置了，因为我们所要替换的值的长度是一定的

那么我们可以倒着来，直接从最后一个填，一直填到第一个就行，遇到空格按照02%的顺序替换，我们需要两个指针以完成交换，代码如下：

class Solution {
   public:	void replaceSpace(char *str,int length) {
           int i,j,count=0;	    for(i=0;i
   
    =0;i--,j--){
               if(str[j]==' '){
                   str[i]='0';                str[--i]='2';                str[--i]='%';            }else{
                   str[i]=str[j];            }	    }    }};
   

运行时间：3 ms	占用内存：504K

Python简单解决

而使用Python语言就可以简单解决这个问题：

# -*- coding:utf-8 -*-class Solution:    # s 源字符串    def replaceSpace(self, s):        # write code here        r=''        for i in s:            if(i==' '):                r+='%'                r+='2'                r+='0'            else:                r+=i        return r

运行时间: 20ms 占用内存: 5752KB

转载地址：https://blog.csdn.net/Jeaten/article/details/107906779 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！