【题目】
原文:
1.5 Write a method to replace all spaces in a string with ‘%20’.
译文:
写一个函数,把字符串中所有的空格替换为%20 。
【分析】
我们首先应该想到的是原来一个空格字符,替换之后变成'%','2','0'三个字符,因此字符串会变长。如果是在原来的字符串上做替换
,那么我们就有可能覆盖修改在该字符串后面的内存。如果是创建信的字符串并在新的字符串上做替换,那么我们自己可以分配足够的
内存。由于两种不同的解决方案,我们应该向面试官问清楚,让他们明确告诉我们需求。假设面试官让我们在原来的字符串上做替换,
并且保证输入的字符串后面有足够多的空余内存。
【思路一】
我们最应该想到的方法就是从头扫描字符串,每一次遇到空格字符的时候就做替换。由于是把一个字符替换成三个字符,我们必须把
空格后面的所有字符都想后面移动两个位置,否则就有两个字符被覆盖了。
举个例子:
我们从头扫描“ we are happy.”中的每一个空格替换成"%20"。
假设字符串的长度是n。对每一个空格字符,需要移动后面O(n)个字符,因此含有O(n)个空格字符的字符串而言总的时间复杂度
为O(n^2)。
【思路二】
我们可以先遍历一遍字符串,这样我们先统计出空格字符的个数,并由此计算出替换空格字符之后的字符串的总长度。
每替换一个空格,长度增加2,因此替换以后的字符串长度等于原来字符串长度加上2*(空格数目)。
举个例子:“ we are happy.”
这个字符串的长度为14,里面有两个空格,因此替换之后的字符串长度为18.
我们从字符串的后面开始复制和替换。首先准备两个指针p1,p2。p1指向原始字符串的末尾,p2指向替换之后的字符串的末尾。
接下来我们向前移动指针p1,逐个把它指向的字符复制到p2指向的位置,直到碰到第一个空格字符为止。碰到第一个空格之后
把p1向前移动一个位置,在p2之前插入字符串“%20”。由于“%20”的长度为3,同时也要把p2向前移动三个位置。我们接着复制,直到
碰到第二个空格,进行同样的操作。
【代码一】
/*********************************
* 日期:2014-05-13
* 作者:SJF0115
* 题目: 替换空格
* 来源:CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
//替换空格
char* ReplaceBlank(char* str){
int i;
int len = strlen(str);
if(len <= 0){
return str;
}
//统计空格个数
int count = 0;
for(i = 0;i < len;i++){
if(str[i] == ' '){
count++;
}
}
//p1 指向原始字符串的末尾
int p1 = len;
//p2 指向替换之后的字符串的末尾
int p2 = len + 2*count;
//开辟一个字符串
char *str2 = new char[p2+1];
//替换
while(p1 >= 0){
if(str[p1] == ' '){
p1--;
str2[p2--] = '0';
str2[p2--] = '2';
str2[p2--] = '%';
}
else{
str2[p2--] = str[p1--];
}
}
return str2;
}
int main(){
char* str = "we are happy.";
str = ReplaceBlank(str);
cout<<str<<endl;
return 0;
}
分享到:
相关推荐
总有些奇葩,不经任何学习,就使用excel文件,...这里给出vba模板,把当前表示换行的多个空格替换为单个换行符。一次运行,会处理sheet所有的单元格中的多余空格。 如果需要针对选中区域的进行替换,请留言,改天再传。
将HTML标签外的空格替换为
javascript将字符串中的多个空格替换为一个空格的正则实例.docx
用C语言写的一个小工具,用来删除文件中的多余空格(行尾空格)、文件末尾无用的空行、以及使用4个空格替换tab键。 目前支持的文件包括.c .h .s .txt .sct,内有操作说明。
[Java]算法练习-空格替换练习题
用 替换字符串空格 C语言 时间复杂度O(n)
解决PB无法直接识别全角空格问题,特写该函数,将字符串中的全角空格替换为半角空格。
将字符串中的多个空格,缩减为一个空格(C语言实现)
主要介绍了javascript将字符串中的多个空格替换为一个空格的正则实例,需要的朋友可以参考下
自己写来用的,分享一下,可以去字符串的空格(Trim),查找替换字符串(Replace)
shell脚本替换文件中的tab为空格,删除空白行(空白行:有空格而没有字符)
用下划线替换空格或用空格替换下划线; 对描述/标题和文件名有用
将源程序中的制表符,换行符替换为单个空格符
源码,可安装在XE7\XE8\XE10,已修正中文bug,特别是中文行文习惯空两字开头,但fastreport会自动遇空格转下一行。找了很久都没找到解决此问题的fr,干脆自己动手解决,同时加入其它字符处理,使之更符合中文习惯。
替换空格(python) 题目 请实现一个函数,将一个字符串中的每个空格替换成“ ”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We Are Happy。 思路1(创建新字符串) 创建一个新字符串ss, 遍历原字符串...
下载后放在myeclipse目录下plugins文件夹下替换同名jar,解决空格的代码自动补全问题
主要介绍php中替换字符串中的空格为逗号,的方法。感觉还不错,大家可以参考下
替换空格.md
python 实现 替换空格