在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。

admin2019-03-29 72

问题在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。

选项

答案/////////////////////////////////////////////////////////////////////// // Find the first char which appears only once in a string // Input: pString - the string // Output: the first not repeating char if the string has, otherwise 0 /////////////////////////////////////////////////////////////////////// char FirstNotRepeatingChar(char* pString) { // invalid input if(!pString) return 0; // get a hash table, and initialize it constinttableSize =256; unsignedinthashTable[tableSize]; for(unsignedinti = 0; i

解析这道题是2006年google的一道笔试题。
看到这道题时，最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较，如果在后面没有发现重复的字符，则该字符就是只出现一次的字符。如果字符串有n个字符，每个字符可能与后面的O(n)个字符相比较，因此这种思路时间复杂度是O(n2)。我们试着去找一个更快的方法。
由于题目与字符出现的次数相关，我们是不是可以统计每个字符在该字符串中出现的次数？要达到这个目的，我们需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数，也就是说这个容器的作用是把一个字符映射成一个数字。在常用的数据容器中，哈希表正是这个用途。
哈希表是一种比较复杂的数据结构。由于比较复杂，STL中没有实现哈希表，因此需要我们自己实现一个。但由于本题的特殊性，我们只需要一个非常简单的哈希表就能满足要求。由于字符（char）是一个长度为8的数据类型，因此总共有可能256 种可能。于是我们创建一个长度为256的数组，每个字母根据其ASCII码值作为数组的下标对应数组的对应项，而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256，以字符ASCII码为键值的哈希表。
我们第一遍扫描这个数组时，每碰到一个字符，在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时，就能直接从哈希表中得到每个字符出现的次数了。

转载请注明原文地址:https://kaotiyun.com/show/eRmZ777K

程序员面试

相关试题推荐

随机试题

最新回复(0)

在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。

程序员面试

Arogueloosecalledahackercouldtakecontroloftheentiresystembyimplantinghisowninstructionsinthesoftwareandthe

Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__

输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如输入整数22和如下二元树10

组合问题（从M个不同字符中任取N个字符的所有组合）

编码实现字符串转整型的函数（实现函数atoi的功能），据说是神州数码笔试题。如将字符串”+123”-->123,”-0123”-->-123,“123CS45”-->123,“123.45CS”-->123,“CS123.45”-->0

活动目录的作用

输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。输出861057911。

bob的电子邮件转发到wanglong@sina.com。

下列有关break和continue语句的叙述中，正确的是________。

关于水运工程大体积混凝土施工阶段的温度控制标准的说法，正确的有()。

水冷式冷凝器在运转中除适时放气和()外，还应加强冷却水系统的检查。

Hadyouworkedharderthattime,you______abetterposition.

男，68岁。突然神昏，半身不遂，目合口张，遗溺，四肢逆冷，脉象细弱。针灸取穴应该为

(2008年)在单缝夫琅禾费衍射实验中，屏上第三级明纹对应的缝问的波振面，可划分为半波带数目为()个。

关于施工现场堆放大宗材料、成品、半成品和机具设备的说法，正确的有()。

“学会关心”是下列哪个德育模式所强调的?()

在用来发射卫星的火箭头部涂了一层特殊的物质。这种物质可以避免火箭因高速运动与空气作用产生高温而被毁坏的危险。这种材料能起这种作用的主要原因是()。

中华民族崇尚精神的优秀传统，表现为对理想人格的推崇。下列古训中，反映这一诉求的有