算法-字符串替换空格

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

解题思路: 首先我们需要先想清楚一点,函数就要求输出替换后的结果,没有说是在原数据上替换,还是可以申请内存,创建一个新的字符串? 后者可以让问题变得简单,用比较直接的方式就可以实现一个时间复杂度为O(n)的代码,首先我们先遍历一遍字符串,找到到底有多少个空格以计算出替换后的长度,在上面的例子中,替换前是14,替换后是18,创建一个长度为18的数组,然后我们只要在从头遍历一次原字符串,没有出现空格就直接复制原字符串的内容,出现空格了就写入”%20”:

虽然这种方法得到了一个时间复杂度为O(n)的算法,但是一样牺牲了空间复杂度啊,要是我们只考虑在原数据上替换,而不新建数组呢?

那么这里有个前提条件,我们只能认为题目中给我们的数组长度是大于等于18的,要不然就会放不下,所以我们还可以先计算一下替换后的长度,然后加个判断,如果发现原数组长度不够,那就直接return好了,这样就可以成功甩锅!

假设原始数据是这样的(最起码也要是这样):

如果我们还是从前到后的遍历的话,时间复杂度就会变成O(n^2),因为每次遍历到空格的时候,还会带动着其他的数据向后移动:

所以,有没有什么办法能够兼顾时间复杂度和空间复杂度呢?? 用直接修改原数据的方法,从后向前替换空格!就酱:

这种方法的话,计算替换后的长度就有了一个新的作用,它告诉我们原数据中最后一位放在新数据的哪一位。

代码实现:

//length就是数组创建时候的长度
void ReplaceBlank(char string[], int length)
{
    if(string == NULL && length <= 0)
        return;

    //实际有数据的长度
    int originalLength = 0;
    int numberOfBlank = 0;
    int i = 0;
    while(string[i] != '\0')
    {
        ++ originalLength;

        if(string[i] == ' ')
            ++ numberOfBlank;

        ++ i;
    }

    //替换之后,新的数据需要的长度 
    int newLength = originalLength + numberOfBlank * 2;
    //在这里甩锅啦,让我在原数据上改,还不给够长度,我能怎么办?
    if(newLength > length)
        return;

    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
    {
        if(string[indexOfOriginal] == ' ')
        {
            string[indexOfNew --] = '0';
            string[indexOfNew --] = '2';
            string[indexOfNew --] = '%';
        }
        else
        {
            string[indexOfNew --] = string[indexOfOriginal];
        }

        -- indexOfOriginal;
    }
}  

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

编码的秘密(python版)

? ? 编码(python版) 最近在学习python的过程中,被不同的编码搞得有点晕,于是看了前人的留下的文档,加上自己的理解,准备写下来,分享给正在...

3107
来自专栏HappenLee的技术杂谈

C++雾中风景11:厘清C++类型转换(static_cast,dynamic_cast,reinterpret_cast,const_cast)

开门见山,先聊聊笔者对类型转换的看法吧。从设计上看,一门面向对象的语言是不一样提供类型转换的,这种方式破坏了类型系统。C++为了兼容C也不得不吞下这个苦果,在实...

371
来自专栏听雨堂

Python学习笔记(1):列表元组结构

Python的列表元组功能强大,令人印象深刻。一是非常灵活,二是便于集体操作。特别是以元组作为列表项的结构,和数据访问的结果能够对应起来,和习惯的二维表理解上也...

1966
来自专栏企鹅号快讯

编写高效简洁代码的那些招式1

高效的代码,每期都会给大家介绍一下编码的技巧,让我们代码更整洁更高效。我们会从python 语言切入,讲一讲如何写的代码更pythonic 。Pythonic ...

1686
来自专栏机器学习从入门到成神

几种有关排序的常见面试问题

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

882
来自专栏小白的技术客栈

Python内置数据结构之字典

今天给大家讲解Python内置数据结构:字典。字典的内容比较多,今天只是简单地介绍一下,明天会继续补充字典相关的内容。 关于Windows的环境安装及配置,小白...

2874
来自专栏编程微刊

JS数组排序技巧汇总(冒泡、sort、快速、希尔等排序)

1253
来自专栏peakxie

Json string值如何传递0x00-0xFF(5分钟理解Unicode,UTF8)

项目中,想通过Json传递0x00-0xFF字符串,自然想到Json的string值。

2337
来自专栏用户2442861的专栏

strcpy函数的实现

http://blog.csdn.net/gpengtao/article/details/7464061

602
来自专栏PHP在线

字符编码笔记

字符编码笔记:ASCII,Unicode和 UTF-8 1. ASCII码 我们知道,在计算机内部,所有的信息最终都表示为一个二进制的字符串。每一个二 进制位...

2679

扫码关注云+社区