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

一、题目:替换空格

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

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

二、解题思路

2.1 O(n2)的解法

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

  假设字符串的长度是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个空格。

  从上面的分析我们可以看出,所有的字符都只复制(移动)一次,因此这个算法的时间效率是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#语言的特殊性,这里在测试初始化时做了一些特殊处理操作:

        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;
        }

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

        // 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);
        }

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

        // 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);
        }

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

        // 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);
        }

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

        // 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);
        }

  (5)Test5:传入NULL

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

            Assert.AreEqual(target, expected);
        }

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

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

            Assert.AreEqual(compared, expected);
        }

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

        // Test7:传入内容为一个空格的字符串
        [TestMethod]
        public void ReplaceBlankTest7()
        {
            // " "
            target[0] = ' ';

            Program.ReplaceBlank(target, maxLength);
            string compared = new string(this.GenerateNewTarget());
            string expected = "%20";

            Assert.AreEqual(compared, expected);
        }

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

        // 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);
        }

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

        // 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);
        }

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

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏企鹅号快讯

bash shell 中如何区别$和${}和$和

$()和${}的用法: 在 bash shell 中,$( ) 与 ` ` (反引号) 都是用来做命令替换用(command substitution)的。而...

35316
来自专栏Script Boy (CN-SIMO)

Qt Quick编程(1)——QML的核心部分ECMAScript

说道QML,不得不先说一下ECMAScript: ECMAScript语言的标准是由Netscape、Sun、微软、Borland等公司基于JavaScript...

4110
来自专栏闻道于事

Java之分支和循环

Java中的分支语句: if语句: if语句的四种写法:   (1)   if(表达式_布尔值) {   ...   }   (2)   if(表达式_布...

3079
来自专栏行者常至

001.python科学计算库numpy(上)

版权声明:本文为博主原创文章,允许转载,请标明出处。 https://blog.csdn.net/qwdafedv/article/deta...

922
来自专栏柠檬先生

JavaScript 基础(一)

基本语法: 区分大小写:       ECMAScript 中的一切(变量,函数名和操作符)都区分大小写。 标识符:     表示符就是指,变量,函数,属性...

21110
来自专栏Python研发

JavaScript

JavaScript是一门编程语言,浏览器内置了JavaScript语言的解释器,所以在浏览器上按照JavaScript语言的规则编写相应的代码,浏览器可以解释...

1382
来自专栏Python研发

go基础编程 day-2

  零值并不等于空值,而是当变量声明为某种来兴后的默认零值,通常情况下默认值为0,bool为false,string为空字符串。

1072
来自专栏代码世界

Python 中格式化字符串 % 和 format 两种方法之间的区别

  Python2.6引入了 format 格式化字符串的方法,现在格式化字符串有两种方法,就是 % 和 format ,具体这两种方法有什么区别呢?请看以下解...

4648
来自专栏ml

c语言格式大整理

1、C语言中,非零值为真,真用1表示;零值为假,假用0表示。 2、转义字符参考: \a 蜂鸣,响铃  \b 回退:向后退一格 ...

5067
来自专栏数据结构与算法

P1739 表达式括号匹配

题目描述 假设一个表达式有英文字母(小写)、运算符(+,—,*,/)和左右小(圆)括号构成,以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是...

3358

扫码关注云+社区

领取腾讯云代金券