面试算法题——将一个字符串中的空格替换成“ ％20”

题目要求：请实现一个函数，将一个字符串中的空格替换成“%20”。

例如，当字符串为"This  is test program. "则经过替换之后的字符串为"This%20%20is%20test%20program."

 

思路1：java——利用API中自带的replaceAll方法来实现替换。

首先来了解一下java.lang.String下的replace方法和replace方法都有什么区别吧——

1、replace方法

replace方法中的两个参数都是char类型的，所以它是用来替换一个字符串中的某个字符的。

举个例子：将字符串中的空格替换成“%” （注意：参数值要用单引号‘ ’）

public static void main(String[] args) {
        String a="This  is  test program.";
        String b=a.replace(
                ' ', '%'
        );
        System.out.println(b);
    }

运行结果：

2、replaceAll方法

在replaceAll方法中，两个参数都是String类型的，而且需要注意的是——被替换的字符串是正则表达式的子字符串，所以在实际使用的时候要注意转义。在这里就以该博客的题目举个例子说明：

例子：将字符串中的空格替换成“%20” （注意：参数值要用双引号" "）

public static void main(String[] args) {
        String a="This  is  test program.";
        String b=a.replaceAll(
            "\\ ", "%20"
         );
        System.out.println(b);
    }

运行结果：

虽然利用了该方法可以实现子字符串的替换，但是在面试中，面试官更希望看到的是你对于这个问题的解决思路，而不是利用已有的方法来实现。所以，接下来我们用算法思想去解决该问题。

思路2：C++——创建一个新的字符串，用于存放替换后的字符串。

如果遇到空格，就将"%20"放入新字符串中；如果遇到普通字符，就将该字符放入新字符串中即可。

代码如下：

#include <iostream>
using namespace std;
string ReplaceBlank(string s)
{
    int n=s.size();
    string res="";
    for(int i=0;i<n;i++)
    {
        if(s[i]==' ')
        {
            res += "%20";
        }
        else
        {
            //res.push_back(s[i]);
            res+=s[i];
        }
    }
    return res;
}

int main()
{
    string s="This  is  test program.";
    string res = ReplaceBlank(s);
    cout<<res<<endl;
    return 0;
}

运行结果：

思路3：C++——如果不允许创建新字符串，必须要在原来的字符串上进行操作，那么

首先思考一下，进行替换的一般顺序无非就是从前或者从后，如果我们从前往后替换字符串，由于我们是将空格（一个字符）替换成了"%20"（三个字符），那么处于在空格后面的字符串肯定会被覆盖，所以我们就考虑从后往前进行替换操作。

替换的整个操作过程如下：

（将字符串先转换为字符数组，再进行如下操作）

1. 遍历原字符串，统计原字符串中的空格数 n，并计算出原字符串的总长度s1；
2. 计算替换后新字符串的长度（s2=s1+n*2）；
3. 创建两个指针P1和P2，分别指向原字符串和新字符串的末尾处；
4. 若P1指向内容不是空格，就将P1指向的内容赋给P2指向的位置处；若point1指向内容为空格，就从P2处开始，依次前移，将'0'、'2'、'%'依次放入。
5. 直到P1与P2指向同一位置时，此时字符串中的所有空格都已经替换完毕。
    

代码实现如下：

#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

void blankReplace(char s[])
{
	int len = strlen(s);
    int count = 0;
    if(len<0||s==NULL)
	return;
	int i;
    for( i= 0;i < len;i++){
        if(s[i] == ' '){
            count++;
        }
    }
    int p1 = len;
    int p2 = 2*count+len;
    while(p1 != p2 && p1 >= 0){
        if(s[p1] == ' '){
            s[p2--] = '0';
            s[p2--] = '2';
            s[p2--] = '%';
            p1--;
        }
        else{
            s[p2--] = s[p1--];
        }
    }
    printf("%s",s);
}
int main()
{
    string s="This  is  test program.";
    //将字符串转换为字符数组 
    //方法1： 
    char *p=(char*)s.data();
    //方法2： 
    //char *p=(char*)s.c_str(); 
    blankReplace(p);
    return 0;
}

运行结果：

 

以上三种方法都可以解决字符串中的字符替换问题，你可以根据自己的实际需求来选择适合的方法。如果在面试中如果遇到这种问题，最好使用最后一种方法来解决，它更能体现算法思想。