专栏首页深度学习与计算机视觉算法-字符串替换空格

算法-字符串替换空格

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

相关文章

  • C++ 传递动态内存

    这部分内容在引用作为函数的参数这个blog中有一些涉及,为了讨论引用传递顺带了参数传递与指针传递,在这里从动态内存传递的角度梳理一下,先看这样一个题目: 下...

    chaibubble
  • Ubuntu nfs配置

    NFS 即网络文件系统(Network File-System),可以通过网络让不同机器、不同系统之间可以实现文件共享。通过 NFS,可以访问远程共享目录,就像...

    chaibubble
  • 学习KNN(二)KNN算法手写数字识别的OpenCV实现

    学习KNN(一) 图像分类与KNN原理 学习KNN(二)KNN算法手写数字识别的OpenCV实现 学习KNN(三)KNN+HOG实现手写数字识别 简介 在Ope...

    chaibubble
  • Java Concurrent CountDownLatch

    CountDownLatch 用于使一组线程(1 or n)等待一个外部任务的完成。很多人将它称为闭锁,可以理解为锁的就是那些线程,然后需要一个外部任务的完成来...

    邹志全
  • 《剑指 offer》刷题记录之:动态规划与贪婪算法

    动态规划是编程面试中的热门话题。一般来说,能够用动态规划求解的问题具有如下三个特点:

    口仆
  • 剑指offer第10题:矩阵中的路径

    根据题目要求,需要我们从一个已知矩阵中找到一个可以挨个形成给定字符串的路径。如果有这条路径的话,我们需要返回true,如果没有的话,我们返回false,并且相同...

    鹏-程-万-里
  • 剑指Offer——编程题的Java实现

    声明:我写这个的意图是我在看书的过程中,就我掌握的内容做一个笔记,没有抄袭的意图。再次说明一下,我找工作的过程中并不顺利,没有像那些牛人们拿到一大把的Offer...

    zhaozhiyong
  • 剑指Offer——编程题的Java实现

    声明:我写这个的意图是我在看书的过程中,就我掌握的内容做一个笔记,没有抄袭的意图。再次说明一下,我找工作的过程中并不顺利,没有像那些牛人们拿到一大把的Offer...

    zhaozhiyong
  • Jtro的技术分享:unity的串口通讯

    串行接口(串口)通常指COM接口,是采用串行通信方式的扩展接口。串口按位(bit)发送和接收字节。尽管比按字节(byte)的并行通信慢,但是串口可以在使用一根线...

    LittleU
  • golang之递归

    超蛋lhy

扫码关注云+社区

领取腾讯云代金券