剑指Offer(二):替换空格

2017年11月20日13:11:09 26 8,973 °C
摘要

请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

剑指Offer(二):替换空格

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

1、思路

最简单的方法就是从头到尾遍历,但是时间复杂度为O(n^2)。

本文采用一种时间复杂度为O(n)的方法。

我们可以先遍历一次字符串,这样就可以统计出字符串空格的总数,并可以由此计算出替换之后的字符串的总长度。每替换一个空格,长度增加2,因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。以"We are happy"为例,"We are happy"这个字符串的长度为14(包括结尾符号"\n"),里面有两个空格,因此替换之后字符串的长度是18。

我们从字符串的尾部开始复制和替换。首先准备两个指针,P1和P2,P1指向原始字符串的末尾,而P2指向替换之后的字符串的末尾。接下来我们向前移动指针P1,逐个把它指向的字符复制到P2指向的位置,直到碰到第一个空格为止。碰到第一个空格之后,把P1向前移动1格,在P2之前插入字符串"%20"。由于"%20"的长度为3,同时也要把P2向前移动3格。

移动示意图:

剑指Offer(二):替换空格

2、编程实现

C++:

Python2.7:

weinxin
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:26   其中:访客  14   博主  12

    • avatar 裸奔的麻瓜 来自天朝的朋友 谷歌浏览器  LLD-AL10 Build/HONORLLD-AL10 广东省深圳市 联通 3

      大神,C++代码,扩展长度后,没有分配内存,会不会死机

      • avatar 张敏 来自天朝的朋友 谷歌浏览器 Windows 7 广东省深圳市 电信 3

        大神,你好,C++代码。 我理解的字符串的最后一个字母应该是str[index_orignal-1],但是你的代码中最后一个是str[index_orignal],字符串最后一个内容不是应该下标减1的么?

          • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省哈尔滨市 联通

            @张敏 已更新感谢。

          • avatar 大敏 来自天朝的朋友 谷歌浏览器 Windows 7 广东省深圳市南山区 电信 3

            大神,请问一下,C++第11行判断i下标对应的值是否结束后,i递增了一位,那判断是否是空格的不就跳过了第0个了吗?

              • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器  Android 8.0.0 MIX 2 Build/OPR1.170623.027 黑龙江省哈尔滨市 联通

                @大敏 输入的时候就已经判断字符串是否为空了。字符串不会为空,这么写可以的。

                  • avatar wmy 来自天朝的朋友 谷歌浏览器 Windows 10 湖北省武汉市 中南财经政法大学 0

                    @Jack Cui 对于这样的字符串” helloworld”,第十一行会跳过第一个空格,使得空格计算减少了吧

                      • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点

                        @wmy 不会,i++和++i的区别,i++先赋值再自加。

                  • avatar Irelia 来自天朝的朋友 谷歌浏览器 Windows 10 湖南省湘潭市 联通 1

                    不用replace,python怎么写

                      • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14 北京市 百度网讯科技联通节点

                        @Irelia 也是一样的,一个一个字符判断。

                          • avatar Irelia 来自天朝的朋友 谷歌浏览器 Windows 10 湖南省湘潭市 联通 1

                            @Jack Cui 但我觉得就无法和C++思想一样,从后往前,不增加额外空间(除非函数参数给了列表),如果用python,得定义一个列表来存新字符串,而且是从前往后判断?

                              • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点

                                @Irelia 字符串追加也是可以的。不用太纠结,这种题不会让你用python写,因为太简单。

                          • avatar Lucas 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_0 江苏省苏州市 电信 2

                            mac的vs上Debug时访问地址错误,EXC_BAD_ACCESS (code=2, address=,,,编译能通过,运行时Bus error: 10

                              • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点

                                @Lucas 没有遇到过。

                              • avatar 考研驸马 来自天朝的朋友 谷歌浏览器 Windows 10 浙江省杭州市 电信 0

                                大神,你好!我想请问下 第10行的i为什么没有给初值呀?是因为全局变量自动给初值0吗?
                                但写的时候给了初值i=0,调试会不通过!有点绕,后来我就把这段代码改成了
                                for (int i = 0; i < length; i++) {
                                original_length++;
                                if (str[i] == ' ')
                                number_blank++;
                                }

                                  • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                                    @考研驸马 代码有问题,已经更改。

                                  • avatar 康斯坦奇 来自天朝的朋友 谷歌浏览器 Windows 10 辽宁省沈阳市 东北大学一舍西 0

                                    大神,为什么从头到尾遍历,时间复杂度为O(n^2)?我用Python写的从头到尾遍历,时间复杂度应该是O(n):
                                    class Solution:
                                    # s 源字符串
                                    def replaceSpace(self, s):
                                    # write code here
                                    if len(s) == 0:
                                    return ”
                                    string = ”
                                    for i in range(len(s)):
                                    if s[i] == ‘ ‘:
                                    string += ‘%20’
                                    else:
                                    string += s[i]
                                    return string

                                      • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                                        @康斯坦奇 因为你新开了一个string字符串,用空间换了时间。
                                        如果要求在原有字符串s上操作,就必须的O(n^2)。

                                        • avatar wind 来自天朝的朋友 谷歌浏览器 Windows 10 湖北省 移动 0

                                          @康斯坦奇 我也感觉想不明白,在原有的字符串上怎么操作?

                                        • avatar conser 来自天朝的朋友 火狐浏览器 Windows 7 河南省洛阳市 电信 0

                                          if(newLen>length)
                                          return;
                                          大佬,感觉你这两句代码没有意义,删不删除都可以过题目!

                                            • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                                              @conser 这个是异常处理,就本题而言,删了也可以。

                                            • avatar ZX-FLY 来自天朝的朋友 谷歌浏览器 Windows 7 上海市 联通 1

                                              if(newLen>length)
                                              return;
                                              请问加入这段代码后,不相当于只要有空格,还没替换,程序就提前结束程序了吗?有点没懂

                                                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                                                  @ZX-FLY 如果满足这个条件,说明有异常,这就是异常捕获,但没做处理。可以去掉。

                                                    • avatar ZX-FLY 来自天朝的朋友 谷歌浏览器 Windows 7 上海市 联通 1

                                                      @Jack Cui 您好,还是有点没太懂。只要有空格,就满足if(newLen>length)的条件。那不相当于只要有空格就异常了?然后return;后的语句都不执行了

                                                        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                                                          @ZX-FLY 这里确实有点问题,直接去掉了。感谢。

                                                    • avatar 打不死的黄妖精 来自天朝的朋友 谷歌浏览器 Windows 8.1 江苏省无锡市 移动 1

                                                      您好,有个问题有些想不明白,这里的字符串定义成char *str,编译也没什么问题,可是你下面的str[newLen–] = ‘0’,这就等于说把str指针指向的字符串中的元素修改了,而这在运行中会造成程序崩溃;,但是使用char str[]就没有这样的问题