算法-字符串替换空格

题目: 实现一个函数,把字符串中的每一个空格替换成”%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参数,首先将参数值输出到标准的输出,并且不换行。函数读取用户输入的值,将其转换成字符串。

732
来自专栏鸿的学习笔记

Python对象的比较:is和==

这两个符号在Python的比较判断中应用广泛,但是这两者是有区别的,体现的是对象中的相等和标识符的概念。==符号比较的是两个对象是否相等,而is符号表达的则是标...

772
来自专栏黑泽君的专栏

Java中,类及其组成所使用的常见修饰符

Java中,类及其组成所使用的常见修饰符 (1)修饰符的分类: 权限修饰符:private、默认、protected、public 状态修饰符:stati...

912
来自专栏十月梦想

php数组遍历三种方法

2703
来自专栏从流域到海域

Python 迭代(iteration)

对一组数据进行遍历访问称为迭代(iteration)。 迭代是Python高级特性之一,而且Python的迭代比其他语言更为简便。但是请注意,迭代操作...

1956
来自专栏星回的实验室

js重修课[五]:类与模块

这个Range类中定义了一个接受两个参数的构造函数,和includes、foreach、toString三个实例方法,以及ZERO一个静态类方法。

1192
来自专栏我有一个梦想

C++服务器开发之基于对象的编程风格

Thread.h #ifndef _THREAD_H_ #define _THREAD_H_ #include <pthread.h> #include <b...

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

最长递增子序列

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

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

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

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

824
来自专栏C#

C#泛型方法解析

    C#2.0引入了泛型这个特性,由于泛型的引入,在一定程度上极大的增强了C#的生命力,可以完成C#1.0时需要编写复杂代码才可以完成的一些功能。但是作为开...

2109

扫码关注云+社区

领取腾讯云代金券