纵有疾风起
人生不言弃

剑指Offer面试题:3.替换空格


一、题目:替换空格

题目:请实现一个函数,把字符串中的每个空格替换成”%20″。例如输入“We are happy.”,则输出“We%20are%20happy.”。 

  在网络编程中,如果URL参数中含有特殊字符,如空格、’#’等,可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在’%’后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32,即十六进制的0x20,因此空格被替换成”%20″。再比如’#’的ASCII码为35,即十六进制的0x23,它在URL中被替换为”%23″。

剑指Offer面试题:3.替换空格插图

二、解题思路

2.1 O(n2)的解法

  最直观的做法是从头到尾扫描字符串,每一次碰到空格字符的时候做替换。由于是把1个字符替换成3个字符,我们必须要把空格后面所有的字符都后移两个字节,否则就有两个字符被覆盖了。下图展示了从前往后把字符串中的空格替换成’%20’的过程:

剑指Offer面试题:3.替换空格插图(1)

  假设字符串的长度是n。对每个空格字符,需要移动后面O(n)个字符,因此对含有O(n)个空格字符的字符串而言总的时间效率是O(n2)。

2.2 O(n)的解法

  Step1.先遍历一次字符串,这样就能统计出字符串中空格的总数,并可以由此计算出替换之后的字符串的总长度。

  以前面的字符串”We arehappy.”为例,”We are happy.”这个字符串的长度是14(包括结尾符号’\0’),里面有两个空格,因此替换之后字符串的长度是18。

  Step2.从字符串的后面开始复制和替换。

  准备两个指针,P1和P2。P1指向原始字符串的末尾,而P2指向替换之后的字符串的末尾。接下来向前移动指针P1,逐个把它指向的字符复制到P2指向的位置,直到碰到第一个空格为止。接着向前复制,直到碰到第二、三或第n个空格。

剑指Offer面试题:3.替换空格插图(2)

  从上面的分析我们可以看出,所有的字符都只复制(移动)一次,因此这个算法的时间效率是O(n),比第一个思路要快。

三、解决问题

3.1 代码实现

    public static void ReplaceBlank(char[] target, int maxLength)    {        if (target == null || maxLength <= 0)        {            return;        }        // originalLength 为字符串target的实际长度        int originalLength = 0;        int blankCount = 0;        int i = 0;        while (target[i] != '\0')        {            originalLength++;            // 计算空格数量            if (target[i] == ' ')            {                blankCount++;            }            i++;        }        // newLength 为把空格替换成'%20'之后的长度        int newLength = originalLength + 2 * blankCount;        if (newLength > maxLength)        {            return;        }        // 设置两个指针,一个指向原始字符串的末尾,另一个指向替换之后的字符串的末尾        int indexOfOriginal = originalLength;        int indexOfNew = newLength;        while (indexOfOriginal >= 0 && indexOfNew >= 0)        {            if (target[indexOfOriginal] == ' ')            {                target[indexOfNew--] = '0';                target[indexOfNew--] = '2';                target[indexOfNew--] = '%';            }            else            {                target[indexOfNew--] = target[indexOfOriginal];            }            indexOfOriginal--;        }    }

3.2 单元测试

  由于C#语言的特殊性,这里在测试初始化时做了一些特殊处理操作:

剑指Offer面试题:3.替换空格插图(3)

        const int maxLength = 100;        char[] target = new char[maxLength];        // Pre-Test        [TestInitialize]        public void ReplaceBlankInitialize()        {            for (int i = 0; i < maxLength; i++)            {                target[i] = '\0';            }        }        public char[] GenerateNewTarget()        {            int length = 0;            for (int i = 0; i < maxLength && target[i] != '\0'; i++)            {                length++;            }            char[] newTarget = new char[length];            for (int i = 0; i < maxLength && target[i] != '\0'; i++)            {                newTarget[i] = target[i];            }            return newTarget;        }

View Code

  (1)Test1:空格在句子中间

剑指Offer面试题:3.替换空格插图(5)

        // Test1:空格在句子中间        [TestMethod]        public void ReplaceBlankTest1()        {            // "hello world"            target[0] = 'h';            target[1] = 'e';            target[2] = 'l';            target[3] = 'l';            target[4] = 'o';            target[5] = ' ';            target[6] = 'w';            target[7] = 'o';            target[8] = 'r';            target[9] = 'l';            target[10] = 'd';            Program.ReplaceBlank(target, maxLength);            string compared = new string(this.GenerateNewTarget());            string expected = "hello%20world";            Assert.AreEqual(compared, expected);        }

View Code

  (2)Test2:空格在句子开头

剑指Offer面试题:3.替换空格插图(7)

        // Test2:空格在句子开头        [TestMethod]        public void ReplaceBlankTest2()        {            // " helloworld"            target[0] = ' ';            target[1] = 'h';            target[2] = 'e';            target[3] = 'l';            target[4] = 'l';            target[5] = 'o';            target[6] = 'w';            target[7] = 'o';            target[8] = 'r';            target[9] = 'l';            target[10] = 'd';            Program.ReplaceBlank(target, maxLength);            string compared = new string(this.GenerateNewTarget());            string expected = "%20helloworld";            Assert.AreEqual(compared, expected);        }

View Code

  (3)Test3:空格在句子末尾

剑指Offer面试题:3.替换空格插图(9)

        // Test3:空格在句子末尾        [TestMethod]        public void ReplaceBlankTest3()        {            // "helloworld "            target[0] = 'h';            target[1] = 'e';            target[2] = 'l';            target[3] = 'l';            target[4] = 'o';            target[5] = 'w';            target[6] = 'o';            target[7] = 'r';            target[8] = 'l';            target[9] = 'd';            target[10] = ' ';            Program.ReplaceBlank(target, maxLength);            string compared = new string(this.GenerateNewTarget());            string expected = "helloworld%20";            Assert.AreEqual(compared, expected);        }

View Code

  (4)Test4:连续有两个空格

剑指Offer面试题:3.替换空格插图(11)

        // Test4:连续有两个空格        [TestMethod]        public void ReplaceBlankTest4()        {            // "helloworld "            target[0] = 'h';            target[1] = 'e';            target[2] = 'l';            target[3] = 'l';            target[4] = 'o';            target[5] = ' ';            target[6] = ' ';            target[7] = 'w';            target[8] = 'o';            target[9] = 'r';            target[10] = 'l';            target[11] = 'd';            Program.ReplaceBlank(target, maxLength);            string compared = new string(this.GenerateNewTarget());            string expected = "hello%20%20world";            Assert.AreEqual(compared, expected);        }

View Code

  (5)Test5:传入NULL

剑指Offer面试题:3.替换空格插图(13)

        // Test5:传入NULL        [TestMethod]        public void ReplaceBlankTest5()        {            target = null;            Program.ReplaceBlank(target, 0);            char[] expected = null;            Assert.AreEqual(target, expected);        }

View Code

  (6)Test6:传入内容为空的字符串

剑指Offer面试题:3.替换空格插图(15)

        // Test6:传入内容为空的字符串        [TestMethod]        public void ReplaceBlankTest6()        {            // ""            Program.ReplaceBlank(target, maxLength);            string compared = new string(this.GenerateNewTarget());            string expected = "";            Assert.AreEqual(compared, expected);        }

View Code

  (7)Test7:传入内容为一个空格的字符串

剑指Offer面试题:3.替换空格插图(17)

        // Test7:传入内容为一个空格的字符串        [TestMethod]        public void ReplaceBlankTest7()        {            // " "            target[0] = ' ';            Program.ReplaceBlank(target, maxLength);            string compared = new string(this.GenerateNewTarget());            string expected = "%20";            Assert.AreEqual(compared, expected);        }

View Code

  (8)Test8:传入的字符串没有空格

剑指Offer面试题:3.替换空格插图(19)

        // Test8:传入的字符串没有空格        [TestMethod]        public void ReplaceBlankTest8()        {            // "helloworld "            target[0] = 'h';            target[1] = 'e';            target[2] = 'l';            target[3] = 'l';            target[4] = 'o';            target[5] = 'w';            target[6] = 'o';            target[7] = 'r';            target[8] = 'l';            target[9] = 'd';            Program.ReplaceBlank(target, maxLength);            string compared = new string(this.GenerateNewTarget());            string expected = "helloworld";            Assert.AreEqual(compared, expected);        }

View Code

  (9)Test9:传入的字符串全是空格

剑指Offer面试题:3.替换空格插图(21)

        // Test9:传入的字符串全是空格        [TestMethod]        public void ReplaceBlankTest9()        {            // "     "            target[0] = ' ';            target[1] = ' ';            target[2] = ' ';            target[3] = ' ';            target[4] = ' ';            Program.ReplaceBlank(target, maxLength);            string compared = new string(this.GenerateNewTarget());            string expected = "%20%20%20%20%20";            Assert.AreEqual(compared, expected);        }

View Code

  单元测试结果如下图所示:

剑指Offer面试题:3.替换空格插图(23)

 

文章转载于:https://www.cnblogs.com/edisonchou/p/4738106.html

原著是一个有趣的人,若有侵权,请通知删除

未经允许不得转载:起风网 » 剑指Offer面试题:3.替换空格

分享到: 生成海报
avatar

评论 抢沙发

评论前必须登录!

立即登录   注册

切换注册

登录

忘记密码 ?

切换登录

注册

我们将发送一封验证邮件至你的邮箱, 请正确填写以完成账号注册和激活