剑指Offer(二):替换空格

2017年11月20日13:11:09 14 3,141 °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
微信公众号
分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注!
Jack Cui

发表评论

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

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

    • 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 没有遇到过。