[编程题]空格替换

热度指数：53092 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个string iniString 及其长度 int len, 已知该字符串中有空格，现要求编写程序将字符串中空格替换为“%20”。返回更改后的string。假设该字符串有足够的空间存放新增的字符，并且知道原字符的长度(小于等于1000)，同时保证字符串由大小写的英文字母组成。

测试样例：

"Mr John Smith”,13

返回："Mr%20John%20Smith"

”Hello  World”,12

返回：”Hello%20%20World”

算法知识视频讲解

妇科圣手

两种思路：

1. 如果允许额外开辟空间，很简单，StringBuffer就可以了

2. 如果不允许额外开辟空间，如果采取每遇到一个空格就把空格后的字符往后挪，算法复杂度无疑太高。剑指offer中提供的思路是先计算出字符串的总长度，遍历一遍得到空格数，得到替换后的字符串长度，然后用两个指针分别指向原始字符串的末尾位置和目标字符串的末尾位置（同在这个字符数组中），由后往前进行复制和替换。这样做的好处是所有字符都只复制一次。算法复杂度为O(n)。

解法1
import java.util.*;

public class Replacement {
    public String replaceSpace(String iniString, int length) {
        // 如果允许分配额外空间
        if (iniString == null || iniString.length() <= 0)
            return iniString;
        
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < length; i++) {
            char c = iniString.charAt(i);
            if (c == ' ')
                sb.append("%20");
            else
                sb.append(c);
        }
        return sb.toString();
    }
}

解法2
public String replaceSpace(String str) {
        char[] charArr = str.toCharArray();
        // 计算源字符串的长度和空格的数量
        int originalLength = charArr.length;
        int numberOfBlank = 0;
        for (char item : charArr)
            if (item == ' ')
                numberOfBlank++;
        // 计算新的字符串长度
        int newLength = originalLength + numberOfBlank * 2;
        char[] newcharArr = new char[newLength];
        //
        int indexOfOriginal = originalLength - 1;
        int indexOfNew = newLength - 1;
        while (indexOfOriginal >= 0) {
            if (charArr[indexOfOriginal] == ' ') {
                newcharArr[indexOfNew--] = '0';
                newcharArr[indexOfNew--] = '2';
                newcharArr[indexOfNew--] = '%';
                indexOfOriginal--;
            } else {
                newcharArr[indexOfNew--] = charArr[indexOfOriginal--];
            }
        }
        return String.valueOf(newcharArr);
    }

发表于 2017-05-23 23:59:03 回复(6)

冷冰冰

// 我觉得能用正则干嘛不用呢...
public String replaceSpace(String iniString, int length) {
   return iniString.replaceAll(" ", "%20");
}
// 或者
public String replaceSpace(String iniString, int length) {
	StringBuilder sb = new StringBuilder();                       
	for (int i = 0; i < length; i++) {                            
		char c = iniString.charAt(i);   
		if(c == ' '){          
			sb.append("%20");    
		}else{  
			sb.append(c);
		}                                                      
	}                                                             
	return sb.toString();                                         
}

编辑于 2015-12-22 21:31:13 回复(19)

rainyan

这里用到一个string的resize方法，所以不需要重新定义一个新的string变量来存储结果。

void resize (size_t n);
void resize (size_t n, char c);

If n is smaller than the current string length , the current value is shortened to its first n character, removing the characters beyond the n th.

If n is greater than the current string length , the current content is extended by inserting at the end as many characters as needed to reach a size of n . If c is specified, the new elements are initialized as copies of c , otherwise, they are value-initialized characters (null characters).

class Replacement {
public:
    string replaceSpace(string iniString, int length) {
        if(length<=0)
            return iniString;
        int blank = 0;
        for(int i=0;i<length;++i)
            if(iniString[i]==' ')
            	++blank;
        int newLength = length+(blank<<1);
        iniString.resize(newLength);
        int index1 = length-1;
        int index2 = newLength-1;
        while(index1>=0 && index2>index1){
            if(iniString[index1]==' '){
				iniString[index2--]='0';
                iniString[index2--]='2';
                iniString[index2--]='%';
            }
            else
                iniString[index2--]=iniString[index1];
            --index1;
        }
        return iniString;
    }
};

发表于 2016-04-22 14:54:46 回复(2)

ahac

class Replacement {
public:
	string replaceSpace(string iniString, int length) {
		// write code here
		string newStr;
		for (int i = 0; i < length; i++){
			if (iniString[i] == ' '){
				newStr.push_back('%');
				newStr.push_back('2');
				newStr.push_back('0');
			}
			else{
				newStr.push_back(iniString[i]);
			}
		}
		return newStr;
	}
};

发表于 2016-02-22 17:44:55 回复(2)

Python

华科平凡

return iniString.replace(" ","%20")

python solution, one line.

发表于 2017-10-01 20:12:17 回复(0)

往逝如枫

//就一个replaceAll就可以了啊

import java.util.*;

public class Replacement {
    public String replaceSpace(String iniString, int length) {
       return iniString.replaceAll(" ","%20");
    }

发表于 2016-02-01 14:34:06 回复(0)

文剑木然

虽然知道题目的本意可能是遍历下字符串，手动写替换过程，但是，感觉这种细节没必要太抠了。。

# -*- coding:utf-8 -*-
class Replacement:
    def replaceSpace(self, iniString, length):
        return iniString.replace(' ', '%20')

运行时间：39ms

占用内存：5732k

发表于 2018-09-26 14:50:57 回复(1)

drdr

    string replaceSpace(string iniString, int length) {
        int spaceCnt = 0;
        for(int i = 0; i < length; ++i)
            if(iniString[i] == ' ') spaceCnt++;
        int newLength = length + 2*spaceCnt;
        iniString.resize(newLength); //不知道输入iniString是否有足够的空间，所以直接resize.
        for(int i = length-1; i >= 0; --i){
            if(iniString[i] == ' '){
                iniString[--newLength] = '0';
                iniString[--newLength] = '2';
                iniString[--newLength] = '%';
            }
            else
                iniString[--newLength] = iniString[i];
        }
        return iniString;
    }

发表于 2017-08-15 16:22:40 回复(1)

牛客463120号

//用了stl中的replace函数
string replaceSpace(string iniString, int length) 
{
	// write code here
	for(int i = 0; i < length; )
	{
	    if(iniString[i] == ' ')
		{
		   iniString.replace(i,1,"%20",0,3);
		   i = i + 3;
		  length = length + 2;
		}
		else
			i++;
	}
	return iniString;
}

编辑于 2016-11-05 16:33:48 回复(0)

忆水寒

class Replacement {
public:
    string replaceSpace(string iniString, int length) {
        // write code here
    string newString;
	for(int i=0;i<length;i++)
	{
		if(iniString[i]==' ')
		   {
		   	 //newString+=iniString[i];
		     newString=newString+"%20"; 
		     continue;
		   }
		newString+=iniString[i];
	}
	return newString; 
    }
};

发表于 2016-07-22 14:13:02 回复(2)

FVector

//有疑问，我的输出会多一块，我以为指针越界了然而半天没找到问题在哪里，只好最后强制字符串终结才过，求解决方案？
class Replacement {
public:
    string replaceSpace(string iniString, int length) {
        // write code here
        int count=0;
        for(int i=0;i<length;i++)
        {
            	if(iniString[i]==' ')
                    count++;
        }
        int size=length+2*count;
        string temp;
        for(int p=0;p<size;p++)
            {
            temp[p]=' ';
        }
        
        for(int j=0,k=0;k<size;j++)
            {

            if(iniString[j]==' ')
                {
				temp[k++]='%';
                temp[k++]='2';
                temp[k++]='0';
                
            }
            else if(iniString[j]=='\0'){
                break;
            }
              else 
        {
                temp[k++]=iniString[j];
            }
        }
        temp[size]='\0';
        return temp;
        }
    
};

发表于 2016-05-22 15:05:48 回复(2)

眞杺＆槑槑

# -*- coding:utf-8 -*-
class Replacement:
    def replaceSpace(self, iniString, length):
        (2766)# write code here
        res = ""
        for i in range(length):
            if iniString[i] == ' ':
                res += "%20"
            else:
                res += iniString[i]
        return res

发表于 2020-03-17 23:06:58 回复(0)

我觉得直接在定义一个字符串，碰到不是空格的就加进去，是空格的就变成加“%20”不就好了吗。。。。

class Replacement {
public:
    string replaceSpace(string iniString, int length) {
        string final;
        for (int i = 0; i < length; i++)
        {
            if (iniString[i]==' ')
            {
                final += "%20";
            }
            else if (iniString[i]!=' ')
            {
               final += iniString[i];
            }
        }
        return final;
    }
};

发表于 2020-02-10 13:54:35 回复(0)

半雨微凉

string replaceSpace(string iniString, int len)
{
	string s;
	for (auto i : iniString)
	{
		if (i == ' ')
		{
			s += "%20";
		}
		else
		{
			s += i;
		}
	}

	return s;
}

没有额外要求，直接+即可~

发表于 2019-09-03 20:14:27 回复(0)

东单

import java.util.*;

public class Replacement {
    public String replaceSpace(String iniString, int length) {
        return iniString.replaceAll("[ ]","%20");// write code here
    }
}

发表于 2019-08-14 15:45:10 回复(0)

我要沐浴在阳光下

垃圾牛客，人家原书输入的是char数组，然后原地改。。。

发表于 2019-06-14 14:49:45 回复(0)

牛客网-小菜鸟

为什么没有人发现这道题目的Java版有问题？

我是对照着书来做的题目。

这道题目的本意是为了考察数组内的移动，本身题目的参数就给得有问题

我认为题目应该是这样的：

public String replaceSpaceA(char[] iniCharArr, int length) {
        // 计算出新的长度
        int spaceCount = 0;
        for (int i = 0; i < length; i++) {
            if (iniCharArr[i] == ' ') {
                spaceCount ++;
            }
        }
        // 从后面开始移起
        int startIndex = length - 1;
        int newLengthIndex = length + spaceCount * 2 -1;
        while (startIndex != newLengthIndex) {
            char moveChar = iniCharArr[startIndex];
            if (moveChar == ' ') {
                iniCharArr[newLengthIndex] = '0';
                iniCharArr[newLengthIndex-1] = '2';
                iniCharArr[newLengthIndex-2] = '%';
                newLengthIndex -= 3;
            } else {
                iniCharArr[newLengthIndex] = moveChar;
                newLengthIndex--;
            }
            startIndex--;
        }
        // 要截取一下，否则会通不过测试
        return new String(iniCharArr, 0, length + spaceCount * 2);
    }

编辑于 2019-01-18 02:32:58 回复(1)

SamcYang

了解string 的insert 和 replace 就很简单了

class Replacement {

public:
string replaceSpace(string iniString, int length) {
// write code here
if (length <= 0)
{
return iniString;
}

for (size_t i=0; i < iniString.size(); i++)
{
if (iniString[i] == ' ')
{
iniString.replace(i,1,"%20",3);
}
}
return iniString;
}
};

发表于 2018-04-15 13:56:47 回复(0)

绘羽

class Replacement {

public:

string replaceSpace1(string iniString, int length) {//先在空格处插入%20，再删除空格

// write code here

for (int i = 0; i < iniString.size(); i++){

if (iniString[i] == ' '){

iniString.insert(i, "%20");

i += 3;

}

for (int i = 0; i < iniString.size(); i++){

if (iniString[i] == ' '){

iniString.erase(i, 1);

}

return iniString;

}

string replaceSpace2(string iniString, int length) { //建立一个新字符串，将iniString元素一个一个写入，其中遇到空格写入%20

// write code here

string newString ;

for (int i = 0; i < iniString.size(); i++){

if (iniString[i] == ' ')

newString.operator+=("%20");//newString.append( "%20");

else

newString.operator+=(iniString[i]);//newString.push_back (iniString[i]);

}

return newString;

}

};

发表于 2017-08-18 23:35:22 回复(0)

Java

村长，那人偷牛！

//方式一：
    public String replaceSpace(String iniString, int length) {
        if(iniString==null||"".equals(iniString)||length<=0) return iniString;
        return iniString.replace(" ","%20");
    }
 //方式二
     public String replaceSpace(String iniString, int length) {
        if(iniString==null||"".equals(iniString)||length<=0||iniString.length()!=length) return iniString;
         StringBuffer sb=new StringBuffer("");
         for(int i=0;i<length;i++){
             if(iniString.charAt(i)==' ') sb.append("%20");
             else sb.append(iniString.charAt(i));
         } 
         return sb.toString();
     }
//方法三：一样的道理
 public String replaceSpace(String iniString, int length) {
        if(iniString==null||"".equals(iniString)||length<=0||iniString.length()!=length) return iniString;
          StringBuffer str=new StringBuffer(iniString);
          str.insert(0,'#');
          str.append('#');
          String[] value=str.toString().split(" ");
          StringBuffer sb=new StringBuffer();
         for(int i=0;i<value.length;i++){
             sb.append(value[i]);
             if(i==value.length-1) break;
             else sb.append("%20");
         } 
          sb.deleteCharAt(0);
          sb.deleteCharAt(sb.length()-1);
         return sb.toString();
     }

编辑于 2017-05-10 16:24:19 回复(0)