问题:
请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路:
- 找到空格的个数
- 创建一个新的字符串个数为空格*2+原字符串长度
- 进行复制,在空格处用%20取代
代码实现
// 第一种思路 从后往前填充字符串数组,效率较高
class Solution {
public:
void replaceSpace(char *str,int length) {
int count = 0;
for (int i = 0; i < length; ++i) {
if (str[i] == ' ') {
++count;
}
}
count *= 2;
int lastSeek = length+count;
for (int i = length; i >= 0; --i) {
if (i == lastSeek) break;
if (str[i] == ' ') {
str[lastSeek--] = '0';
str[lastSeek--] = '2';
str[lastSeek--] = '%';
continue;
}
str[lastSeek--] = str[i];
}
}
};
// 第二种思路,从前往后填充字符串数组,效率最低
class Solution {
public:
void replaceSpace(char *str,int length) {
int j = 0;
char dd[100];
for (int i = 0; i < length; ++i,++j)
{
if (str[i] != ' ') {
dd[j] = str[i];
}
else {
dd[j] = '%';
dd[++j] = '2';
dd[++j] = '0';
}
}
strcpy(str,dd);
}
};
// 第三种思路,双指针思路
class Solution {
public:
void replaceSpace(char *str,int length) {
if(str==NULL||length<=0)
return;
int realLength=0;
int blank=0;
int i=0;
while(str[i]!='\0')
{
++realLength;
if(str[i]==' ')
++blank;
++i;
}
int newLength=realLength+blank*2;
if(newLength>length)
return;
int index=realLength;
int newIndex=newLength;
while(index>=0&&newIndex>index)
{
if(str[index]==' ')
{
str[newIndex--]='0';
str[newIndex--]='2';
str[newIndex--]='%';
}
else
str[newIndex--]=str[index];
--index;
}
}
};