这里提供除原文之外的另一种思路,不过好像不如原文中的好,先记下吧。
大致思路:把要删除的字符集(假设为char *del)看成一个模子,把它套在原字符串(假设为char *src)中进行比较,一开始,del的第一个字符和src的第一个字符比较,不相同就同时后移指针,如相同,就删除src中的字符,并且把后面的所有字符前移,继续比较这一位,这样一直比较,直到del的字符都比较完后,再进行第二轮。第二轮比较时,把del的首字符对准src的第二个字符,开始上述过程。这样直到src的最后一个字符对准del的第一个字符为最后一轮。
这样做的缺点就是每次删除一个字符之后,都要进行大量的字符移动,很耗时,这个也是原文中的方法重点解决的一个问题。
原文中用一个256长度的数组来做hash表,有点浪费了,因为hash表的值只可能为0或1,所以可以用int的每一位对应一个hash表中的元素,这样就只需要8个int就可以组成这个hash表,大大节省了空间。
另外,原文中有一个需要考虑的地方,最后在pSlow指针处赋值\0后,pSlow指针之后的空间(直到\0)应该free掉吧。
下面全部为原文引用:
题目:输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如,输入"They are students."和"aeiou",则删除之后的第一个字符串变成"Thy r stdnts."。
分析:这是一道微软面试题。在微软的常见面试题中,与字符串相关的题目占了很大的一部分,因为写程序操作字符串能很好的反映我们的编程基本功。
要编程完成这道题要求的功能可能并不难。毕竟,这道题的基本思路就是在第一个字符串中拿到一个字符,在第二个字符串中查找一下,看它是不是在第二个字符串中。如果在的话,就从第一个字符串中删除。但如何能够把效率优化到让人满意的程度,却也不是一件容易的事情。也就是说,如何在第一个字符串中删除一个字符,以及如何在第二字符串中查找一个字符,都是需要一些小技巧的。
首先我们考虑如何在字符串中删除一个字符。由于字符串的内存分配方式是连续分配的。我们从字符串当中删除一个字符,需要把后面所有的字符往前移动一个字节的位置。但如果每次删除都需要移动字符串后面的字符的话,对于一个长度为n的字符串而言,删除一个字符的时间复杂度为O(n)。而对于本题而言,有可能要删除的字符的个数是n,因此该方法就删除而言的时间复杂度为O(n2)。
事实上,我们并不需要在每次删除一个字符的时候都去移动后面所有的字符。我们可以设想,当一个字符需要被删除的时候,我们把它所占的位置让它后面的字符来填补,也就相当于这个字符被删除了。在具体实现中,我们可以定义两个指针(pFast和pSlow),初始的时候都指向第一字符的起始位置。当pFast指向的字符是需要删除的字符,则pFast直接跳过,指向下一个字符。如果pFast指向的字符是不需要删除的字符,那么把pFast指向的字符赋值给pSlow指向的字符,并且pFast和pStart同时向后移动指向下一个字符。这样,前面被pFast跳过的字符相当于被删除了。用这种方法,整个删除在O(n)时间内就可以完成。
接下来我们考虑如何在一个字符串中查找一个字符。当然,最简单的办法就是从头到尾扫描整个字符串。显然,这种方法需要一个循环,对于一个长度为n的字符串,时间复杂度是O(n)。
由于字符的总数是有限的。对于八位的char型字符而言,总共只有28=256个字符。我们可以新建一个大小为256的数组,把所有元素都初始化为0。然后对于字符串中每一个字符,把它的ASCII码映射成索引,把数组中该索引对应的元素设为1。这个时候,要查找一个字符就变得很快了:根据这个字符的ASCII码,在数组中对应的下标找到该元素,如果为0,表示字符串中没有该字符,否则字符串中包含该字符。此时,查找一个字符的时间复杂度是O(1)。其实,这个数组就是一个hash表。这种思路的详细说明,详见 本面试题系列的第13题
。
基于上述分析,我们可以写出如下代码:
////////////////////////////////////////////////// /////////////////////
// Delete all characters in pStrDelete from pStrSource
////////////////////////////////////////////////// /////////////////////
voidDeleteChars(char* pStrSource, constchar* pStrDelete)
{
if(NULL == pStrSource || NULL == pStrDelete)
return;
// Initialize an array, the index in this array is ASCII value.
// All entries in the array, whose index is ASCII value of a
// character in the pStrDelete, will be set as 1.
// Otherwise, they will be set as 0.
constunsignedintnTableSize = 256;
inthashTable[nTableSize];
memset(hashTable, 0, sizeof(hashTable));
constchar* pTemp = pStrDelete;
while ('\0' != *pTemp)
{
hashTable[*pTemp] = 1;
++ pTemp;
}
char* pSlow = pStrSource;
char* pFast = pStrSource;
while ('\0' != *pFast)
{
// if the character is in pStrDelete, move both pStart and
// pEnd forward, and copy pEnd to pStart.
// Otherwise, move only pEnd forward, and the character
// pointed by pEnd is deleted
if(1 != hashTable[*pFast])
{
*pSlow = *pFast;
++ pSlow;
}
++pFast;
}
*pSlow = '\0';
}
原文地址:http://zhedahht.blog.163.com/blog/static/254111742 00801931426484/
发表评论
-
正则表达式regexp_like regexp_replace regexp_substr
2012-07-06 09:45 1236regexp_like regexp_like函数的基本构 ... -
asp 页面中使用正则表达式
2012-07-06 09:37 615RegExp就是建立正则 ... -
遮罩的使用
2012-07-06 09:30 649有N个按钮又不想其导航栏出现烦人的滚动条。 解决方法: ... -
数据库组件 Hxj.Data (三十)(Asp.Net 页面自动赋值与取值)
2012-07-05 20:45 646... -
Swing组件集合的事件处理(三)
2012-07-03 13:43 809除了基本的事件委 ... -
flex--LineChart
2012-07-02 10:38 568最近工作上用到了linechart,在网上查的资料还是非常 ... -
Flex4与java通信(二、与servlet通信)
2012-07-02 10:38 511说明:这里介绍使用URLRequest+URLLoader ... -
flex的mask处理
2012-07-02 10:38 602在做公司一个flash播放器时候,需要在一个swf中动态加 ... -
Flex 接入 WebService
2012-07-02 10:38 645因工作需要,要学会 Flex接入 WebService;在 ... -
[tamarin系列之9] 在线的eval
2012-07-01 00:16 553文章分类:Java编程 我们先做一个实验: 1、构建 ... -
android ubuntu9.10 源码的编译 Eclipse工程 Contacts编译 应用加载
2012-07-01 00:16 868第一部分:编译环 ... -
adobe Air 小玩意程序:加载百度随便听听
2012-07-01 00:16 591今天,我承认会有一点偷懒,在写微博的程序的时候,忽然 ... -
Embed
2012-07-01 00:16 724Flex 软件中经常需要使用一些外部的资源,如图片、声音、 ... -
成功使用ArcGIS API for iOS加载Google地图
2012-07-01 00:16 792终于能够使用ArcGIS API for iOS加载Goo ...
相关推荐
C#批量删除字符串中间的字符串,输入开始字符串,结束字符串,点击删除按钮之后,获取新的删除后的字符串(开始字符串跟结束字符串不删除)
在Python中,字符串是不可变的。所以无法直接删除字符串之间的特定字符。 所以想对字符串中字符进行操作的时候,需要将字符串转变为列表,列表是可变的,这样就可以实现对字符串中特定字符的操作。 1、删除特定字符 ...
用指针删除数组里面的字符串,简单易懂,专为初学者写的
第一、找出字符或者字符串的类型,是数字、字母还是其他特定字符,是可打印字符,还是不可打印字符(一些控制字符)。 第二、找出组成字符串的字符个数和字符串的存储结构(比如数组)。 第三、对串的常规操作:求子串、...
将该bat文件放入想处理的文件的同一文件夹中(注意,该bat会处理同一文件夹中所有的文件),双击运行,输入想删除的字符串,回车运行。
删除字符串中指定的字符函数,例子。。。。。。
按照系统已经定义的函数接口编写函数实体,实现:在主串中MainStr查找是否存在某特定子串SubStr1,若存在则将所有的SubStr1替换为新的指定子串SubStr2,函数返回字符串替换的次数。 具体要求和相关假设为: ① 函数...
这是一个如何在Excel中使用Visual Basic获取特定字符串并提取其加权值的示例。这个示例将删除不需要的列,并添加一个列,用于根据VLOOKUP引用表填充加权数字。 这是一个如何在Excel中使用Visual Basic获取特定字符串...
是编程人员必备的东东,比如有许多行代码或字符串,要在每个字符串前、后加什么字符,要删除字符,替换字符,删除前面,后面几个字符,删除多行代码中的空白行。或交换某特定字符的前后内容...不用再每字每句的手写...
主要介绍了JS实现字符串中去除指定子字符串方法,结合实例形式分析了javascript使用字符串替换与分割、聚合两种子字符串去除相关操作技巧,需要的朋友可以参考下
批处理bat文件,将当前文件夹下所有文件,文件名中的name1替换位name2,简单的几行代码,执行批处理重命名操作,如果想删除特定字符,name2为空即可
labview8.6编写的将字符串过滤成指定的字符串,包括 数值,大写,小写,十进制,16进制,8进制等
Shell 删除指定文件中含有指定字符的行,2个参数,脚本中有注释
mdl_strrep 是一种实用程序,用于识别名称中包含特定字符串的模块和其他 Simulink 组件。 MDL_STRREP(OBJECT,S1,S2) 用字符串 S2 替换 Simulink 对象及其子对象名称中所有出现的字符串 S1。 当模型在不同的上下文中...
主要介绍了pandas.DataFrame中删除包涵特定字符串所在的行,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
产品特点 查找字符串中所有出现的表情符号 在字符串中搜索特定于表情的表情符号 查找单个表情符号的定义 查找定义以获取表情符号列表 从字符串中删除所有表情符号 导入工具可使用规格更新Emoji数据 查找字符串中特定...
网上很多办法,虽然是对的,用起来结果不对。这里提供正确办法。 去掉开头的空格 $text= 123 456 ...# 删除字符串中所有空格 sed 's/[[:space:]]//g' 当然还有简单办法: # 只替换一个 text=${text/ /-} #
主要介绍了python去除字符串中的换行符的相关资料,然后在文章下面给大家补充介绍了python去除空格和换行符的方法,需要的朋友可以参考下
从数据库中select()读取一对多的信息时,经常需要将取出的数组用某个特定的字符分割,然后拼接成字符串。 常见的语法格式: foreach ($arr as $key => $value) { $arr_str = $arr['x_id'] . ',' . $arr_str; } ...