面试题【002字符串替换空格】精妙解法

题目描述

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

解题思路

老实说，看到这个题目想到的就是字符串替换，但是面试题肯定不是这么简单的，那么怎么在原字符串上进行高效的替换呢？我们的字符串替换，主要的消耗是在移位上，每遇到一个空格，后面的字符串就往后移位，那么之前的移位都没有作用了。我们知道字符串的长度，知道替换字符串的长度，如果还知道空格的多少，那么这个字符串的长度就知道了。知道长度之后，只需要把数据放到响应的位置就可以了。
步骤：
1. 遍历字符串，统计出空格数量
2. 再遍历一次，完成替换

代码实现

普通解法，直接替换字符串

public static string replacespaceforsimple(string str)
{
    return str.replace(" ", "%20");
}

精妙解法数据移位

public static string replacespace(string str)
{
    int count = 0;
    foreach (var item in str)
    {
        if (item == ' ')
        {
            count++;
        }
    }

    int olength = str.length;
    int length = olength + count * 2; //"%20".length-1
    char[] temparray = new char[length]; //新开辟了一个空间
    length--;
    for (int i = olength - 1; i >= 0; i--)
    {
        if (str[i] == ' ')
        {
            temparray[length--] = '0';
            temparray[length--] = '2';
            temparray[length--] = '%';
        }
        else
        {
            temparray[length--] = str[i];
        }
    }

    return new string(temparray);
}

赋值给另外一个

public static string replaceforbs(string str) {
    stringbuilder sb = new stringbuilder();
    foreach (var item in str) {
        if (item == ' ')
        {
            sb.append("%20");
        }
        else {
            sb.append(item);
        }
    }
    return sb.tostring();
}

测试

中间空格

[fact]
public void middle()
{
    string str = "we are happy.";
    assert.equal(coding002.replacespaceforsimple(str), coding002.replacespace(str));
    assert.equal(coding002.replacespaceforsimple(str), coding002.replaceforbs(str));
}

开始空格

[fact]
public void start()
{
    string str = " we are happy.";
    assert.equal(coding002.replacespaceforsimple(str), coding002.replacespace(str));
    assert.equal(coding002.replacespaceforsimple(str), coding002.replaceforbs(str));
}

结束空格

[fact]
public void end()
{
    string str = "we are happy. ";
    assert.equal(coding002.replacespaceforsimple(str), coding002.replacespace(str));
    assert.equal(coding002.replacespaceforsimple(str), coding002.replaceforbs(str));
}

多空格

[fact]
public void more()
{
    string str = "we     are  happy.";
    assert.equal(coding002.replacespaceforsimple(str), coding002.replacespace(str));
    assert.equal(coding002.replacespaceforsimple(str), coding002.replaceforbs(str));
}

空字符串

[fact]
public void empty()
{
    string str = "";
    assert.equal(coding002.replacespaceforsimple(str), coding002.replacespace(str));
    assert.equal(coding002.replacespaceforsimple(str), coding002.replaceforbs(str));

    str = " ";
    assert.equal(coding002.replacespaceforsimple(str), coding002.replacespace(str));
    assert.equal(coding002.replacespaceforsimple(str), coding002.replaceforbs(str));

    str = "  ";
    assert.equal(coding002.replacespaceforsimple(str), coding002.replacespace(str));
    assert.equal(coding002.replacespaceforsimple(str), coding002.replaceforbs(str));
}

结果

想入非非：扩展思维，发挥想象

1. 这个题可以扩展为替换其他的数据，不要局限于单一的替换，url就是ascii替换
2. 字符串是一种特殊的char[]