算法-字符串替换空格

题目: 实现一个函数,把字符串中的每一个空格替换成”%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 条评论
登录 后参与评论

相关文章

来自专栏Bug生活2048

Python自学之路-内置函数说明及实例(四)

如果提供了promat参数,首先将参数值输出到标准的输出,并且不换行。函数读取用户输入的值,将其转换成字符串。

532
来自专栏Deep learning进阶路

Python随记(三)字典

Python随记(三)字典 字典(Dictionary) 也是序列(sequence)的一种,是另一种可变容器模型。字典的值并没有特殊的顺序,但是都存储在一个...

2000
来自专栏闻道于事

JavaScript深入浅出补充——(一)数据类型,表达式和运算符

项目基本做完,在进行下一阶段学习之前先看视频学习回顾一下JavaScript 一、数据类型 JavaScript中有五种原始类型和一种对象类型 ? JavaSc...

3255
来自专栏峰会SaaS大佬云集

C#学习---基础入门(一)

值类型:整数/实数/字符/布尔    结构/枚举   -------值类型直接存储值(对一个对象进行修改,不会改动其他对象值)

654
来自专栏mukekeheart的iOS之旅

OC学习3——C语言特性之指针

1、指针是C语言中的一个非常重要的概念,实际上,OC系统类的变量、自定义类的变量等都是指针。定义指针变量的语法格式如下,其中*代表一个指针变量,整个语法代表定义...

2308
来自专栏流媒体

指针与数组和函数的几个关系

733
来自专栏运维技术迷

连仕彤博客[Python笔记] isinstance() 函数

isinstance() 函数来判断一个对象是否是一个已知的类型,类似 type()。但是isinstance和type是有区别的:

451
来自专栏十月梦想

php数组遍历三种方法

1223
来自专栏康怀帅的专栏

Redis set 类型

从集合 (set) 中插入或者删除元素,set 中不能有重复值 sadd set1 12 13 14 移除 srem set1 12 13 集合元素数量 sca...

3504
来自专栏机器学习算法工程师

最长递增子序列

最长递增序列不要求数组元素连续问题,返回递增序列长度和递增序列。o(n^2)做法,顺序比较以第i个元素开头的递增序列即可。 利用动态规划来做,假设数组为1, -...

3466

扫码关注云+社区