首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如,输入”They are students.” 和”aeiou” ,则删除之后的第一个字符串变成”Thy r stdnts.” 。
输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如,输入”They are students.” 和”aeiou” ,则删除之后的第一个字符串变成”Thy r stdnts.” 。
admin
2019-03-29
91
问题
输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如,输入”They are students.” 和”aeiou” ,则删除之后的第一个字符串变成”Thy r stdnts.” 。
选项
答案
/////////////////////////////////////////////////////////////////////// // Delete all characters in pStrDelete from pStrSource /////////////////////////////////////////////////////////////////////// void DeleteChars(char* pStrSource, const char* 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. const unsigned int nTableSize = 256; int hashTable[nTableSize]; memset(hashTable, 0, sizeof(hashTable)); const char* 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’; }
解析
这是一道微软面试题。在微软的常见面试题中,与字符串相关的题目占了很大的一部分,因为写程序操作字符串能很好的反映我们的编程基本功。
要编程完成这道题要求的功能可能并不难。毕竟,这道题的基本思路就是在第一个字符串中拿到一个字符,在第二个字符串中查找一下,看它是不是在第二个字符串中。如果在的话,就从第一个字符串中删除。但如何能够把效率优化到让人满意的程度,却也不是一件容易的事情。也就是说,如何在第一个字符串中删除一个字符,以及如何在第二字符串中查找一个字符,都是需要一些小技巧的。
首先我们考虑如何在字符串中删除一个字符。由于字符串的内存分配方式是连续分配的。我们从字符串当中删除一个字符,需要把后面所有的字符往前移动一个字节的位置。但如果每次删除都需要移动字符串后面的字符的话,对于一个长度为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 表。
转载请注明原文地址:https://kaotiyun.com/show/yRmZ777K
0
程序员面试
相关试题推荐
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。例如:输入两个
公司要求开发一个继承System.Windows.Forms.ListView类的组件,要求达到以下的特殊功能:点击ListView各列列头时,能按照点击列的每行值进行重排视图中的所有行(排序的方式如DataGrid相似)。根据您的知识,请简要谈一下您的
如何部署一个ASP.net页面。
为邮件到达后应用规则“若发件人包含‘mary@sina.com’转发到wangtao@sina.com”。
创建一个新的邮件。
在金山毒霸2008中,手动查杀“移动存储设备”中的病毒木马。
计算机能直接识别和执行的语言是()A.机器语言B.高级语言C.数据库语言D.汇编程序
在foxpro中,要浏览多个数据库的字段,以下说法中正确的是()并允许进行字段的修改。A.使用listfields命令 B.browsefields命令C.前两者都不对 D.不能在command命令窗口中实现
随机试题
触摸屏是用于实现替代()的功能。
某男性工人,在施工中头部被砸伤,出血不止,急诊来院。经检查,沿发际外侧有一纵行裂口,长约3.5cm,需清创缝合。下列除哪一项外,都是供应头皮的血管
发行债券是公司追加资金的需要,它属于公司的资本金。
下列句子修辞归类正确的一项是()。①指导员讲的真来劲,嘎子竖起耳朵听②我的母亲早已迎着出来,接着飞出了八岁的侄子宏儿③荷花人暮犹愁热,低面深藏碧伞中④一颗有生命力的种子,如果不落在肥土里,而落在瓦砾堆里,它绝不会悲观,也绝不会叹气⑤油蛉在
甲参加某旅行社组织的新马泰五日游旅行团,在旅游过程中与旅行社导游发生争执打斗,将旅行社诉至法院,甲与旅行社形成的诉讼法律关系的客体是
已知A=,二次型f(x1,x2,x3)=xT(ATA)x的秩为2,求实数A的值.
Forthefirsttime,morewomenthanmenintheUnitedStatesreceiveddoctoraldegreeslastyear,theclimaxofdecadesofchang
在关系数据库设计中,关系模式设计属于()。
A、Thefamousbrands.B、Thecereals.C、Books.D、Meat.B列举中直接提到了cereals。A的干扰性较大,女士建议“你经常使用的品牌产品可以上网选购”,并没有说这些产品是“名牌产品”。
A、Shesellspapersandcigarettestolocalfactoryworkers.B、Shesellsfreshmilk,frozenfish,cookedmeattohousewives.C、Sh
最新回复
(
0
)