题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。
分析:这道题是2006年google的一道笔试题。
看到这道题时,最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较,如果在后面没有发现重复的字符,则该字符就是只出现一次的字符。如果字符串有n个字符,每个字符可能与后面的O(n)个字符相比较,因此这种思路时间复杂度是O(n2)。我们试着去找一个更快的方法。
由于题目与字符出现的次数相关,我们是不是可以统计每个字符在该字符串中出现的次数?要达到这个目的,我们需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数,也就是说这个容器的作用是把一个字符映射成一个数字。在常用的数据容器中,哈希表正是这个用途。
哈希表是一种比较复杂的数据结构。由于比较复杂,STL中没有实现哈希表,因此需要我们自己实现一个。但由于本题的特殊性,我们只需要一个非常简单的哈希表就能满足要求。由于字符(char)是一个长度为8的数据类型,因此总共有可能256 种可能。于是我们创建一个长度为256的数组,每个字母根据其ASCII码值作为数组的下标对应数组的对应项,而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256,以字符ASCII码为键值的哈希表。
我们第一遍扫描这个数组时,每碰到一个字符,在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时,就能直接从哈希表中得到每个字符出现的次数了。
参考代码如下:
///////////////////////////////////////////////////////////////////////
// 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
const int tableSize = 256;
unsigned int hashTable[tableSize];
for(unsigned int i = 0; i < tableSize; ++ i)
hashTable[i] = 0;
// get the how many times each char appears in the string
char* pHashKey = pString;
while(*(pHashKey) != '\0')
hashTable[*(pHashKey++)] ++;
// find the first char which appears only once in a string
pHashKey = pString;
while(*pHashKey != '\0')
{
if(hashTable[*pHashKey] == 1)
return *pHashKey;
pHashKey++;
}
// if the string is empty
// or every char in the string appears at least twice
return 0;
}
代码见E:/C++Primer/常用知识
发表评论
-
析构函数为虚函数的原因
2012-09-09 11:42 777我们知道,用C++开发的时候,用来做基类的类的析构函数 ... -
hash的应用
2012-08-31 23:02 918第一部分为一道百度面试题Top K算法的详解;第二部分为关 ... -
微软智力题
2012-08-29 19:59 534第一组1.烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有 ... -
C++不能被继承的类
2012-08-27 20:16 989一个类不能被继承, ... -
括号对齐问题
2012-08-27 10:47 1347解法一:左右括号成一对则抵消 可以 ... -
树的遍历
2012-08-19 10:43 670/****************************** ... -
堆排序
2012-08-16 14:24 839堆:(二叉)堆数据结构是一种数组对象。它可以被视为一棵完全 ... -
多态赋值
2012-08-14 16:16 774#include <iostream> usi ... -
static变量与static函数(转)
2012-08-13 10:15 695一、 static 变量 static变量大致分为三种用法 ... -
不用sizeof判断16位32位
2012-08-10 15:21 1656用C++写个程序,如何判断一个操作系统是16位还是3 ... -
找出连续最长的数字串(百度面试)
2012-08-09 15:15 1104int maxContinuNum(const char*in ... -
顺序栈和链栈
2012-08-06 10:01 759顺序栈:话不多说直接上代码 #include ... -
队列的数组实现和链表实现
2012-08-05 16:20 991话不多少,数组实现上代码: #include<i ... -
KMP算法详解
2012-08-02 21:40 843KMP算法: 是在一个“主文本字符串” ... -
字符串的最长连续重复子串
2012-08-01 15:05 9691两种方法: 循环两次寻找最长的子串: <方法一> ... -
寻找一个字符串连续出现最多的子串的方法(转)
2012-07-31 21:19 910算法描述首先获得后缀数组,然后1.第一行第一个字符a,与第二行 ... -
字符串的循环移位
2012-07-31 16:52 929假设字符串:abcdefg 左循环两位:cdefgab 右 ... -
一次谷歌面试趣事(转)
2012-07-31 15:26 720很多年前我进入硅谷 ... -
约瑟夫环问题(循环链表)
2012-07-30 21:31 1236题目描述:n只猴子要选大王,选举方法如下:所有猴子按 1, ... -
面试之单链表
2012-07-30 20:18 6861、编程实现一个单链表的建立/测长/打印。 ...
相关推荐
由第三方作者花费大量时间收集并整理散落在茫茫网络中的面经,并从中精选出若干具有代表性的技术类的面试题展开讨论,希望能给读者带来一些启发 例如; 把二元查找树转变成排序的双向链表 设计包含min函数的栈 把...
[原]《程序员面试题精选》05.输出一个字符串的所有子串 题目:给定一个字符串,输出其所有子字符串,例如给定字符串abc,则输出 :a,b,c,d,ab,bc,cd,abc,bcd,abcd。 分析:今天看到csdn博客上面的一题,...
- 字符串类笔试题 - JS笔试题 - 如何应对HR⾯ - 如何应对项⽬⾯ - 如何写简历 从前端基础,到网络协议,再到浏览器原理,前端工程化,前端流行框架,前端安全处理,工程化,算法相关,简历优化 适合人群: - 前端...
常见面试算法题的Scala语言实现,其中包括 链表,字符串,数组,已经面试建议和大数据的算法问题,希望可以帮助读者提高编写scala代码的能力,增加解决常见算法题的能力。
第一章 字符串 o 1.0 本章导读 o 1.1 旋转字符串 o 1.2 字符串包含 o 1.3 字符串转换成整数 o 1.4 回文判断 o 1.5 最长回文子串 o 1.6 字符串的全排列 o 1.10 本章习题 第二章 数组 o 2.0 本章导读 o 2.1 寻找最小的...
面试题15:一个参数可以既是const又是volatile吗 面试题16:一个指针可以是volatile吗 第5章 引用和指针 5.1 引用 面试题1:什么是引用 面试题2:常引用有什么作用 面试题3:流操作符重载为什么返回引用 5.2 指针 ...
第一篇(第1章)介绍了求职面试前都需要做好哪些准备工作:如何做好自己的职业规划;掌握面试的流程,在以后的面试中不会感到陌生,消除恐惧;怎样制作一个令人满意、访问量高的简历;去参加面试的时候着装上都需要...
程序员面试笔试合集,包括FAQ,内存管理、数据结构和算法、字符串操作等常见题,绝对能在笔试面试中加分!chm格式,方便阅读!
程序员面试攻略 【目录】 <br>前言 第1章 求职过程 第2章 程序设计面试题的解答思路 第3章 链表 第4章 树和图 第5章 数组与字符串 第6章 递归算法 第7章 其他程序设计问题 第8章 与...
常见算法笔试或面试题 笔试面试专栏:字符串 数组 vc题集 十道海量数据处理面试题与十个方法大总结 google全程面试题 其他一些公司的面试题
C++程序员面试、笔试经常遇到的一些算法示例集 pdf,相关内容:字符串匹配的KMP算法,括号匹配检测、求一个数组的最长递减字序列、一些数字题求解,输出一个字符串的所有组合,马戏团表演问题、Thread.sleep 与obj....
本书第1章至第6章分别阐述字符串、数组、树、查找、动态规划、海量数据处理等相关的编程面试题和算法,第7章介绍机器学习的两个算法—K近邻和SVM。 此外,《编程之法:面试和算法心得》每一章都有“举一反三”和...
第一章 求职过程 第二章 程序设计面试题的解答题思路 第三章 链表 第四章 树和图 第五章 数组和字符串 第六章 递归算法 第七章 其它程序设计问题 第八章 与计数、测量、排序有关的智力题 第九章 与图形和空间有关的...
独辟蹊径,角度很好,尤其适合我们要找一个好工作的想法,你为公司做了很多事情,也学了很多技术,可是 面试的题目你不一定能够过关,因为面试考题角度特别。要提高自己的生存能力,还是多研究一下吧。我看了前面的...
独辟蹊径,角度很好,尤其适合我们要找一个好工作的想法,你为公司做了很多事情,也学了很多技术,可是 面试的题目你不一定能够过关,因为面试考题角度特别。要提高自己的生存能力,还是多研究一下吧。我看了前面的...
写一个方法,实现字符串的反转,如:输入abc,输出cba 写一个方法,实现字符串的替换,如:输入bbbwlirbbb,输出bbbhhtccc。 3.数据类型之间的转换 如何将数值型字符转换为数字(Integer,Double) 如何将数字...
程序员刷最多道题可以面试#SOURCE 1. geeksforgeeks - 面试中的 10 大算法 图形 广度优先搜索 (BFS) 深度优先搜索 (DFS) 从源到所有顶点的最短路径Dijkstra 从每个顶点到每个其他顶点的最短路径Floyd Warshall 在图...
程序员面试题精选100题(07)-翻转句子中单词的顺序[算法] 2007-03-08 09:20:52| 分类: 字符串 | 标签:编程 就业 找工作
[原网页] [置顶] 程序员面试、算法研究、编程艺术、红黑树、数据挖掘5大系列集锦 [原网页] 程序员编程艺术第三十~三十一章:字符串转换成整数,通配符字符串匹配 [原网页] 程序员编程艺术第二十八~二十九章:最大...
第二次握手:服务器收到syn包,必须确认客户的SYN(ack=j+1),同时自己也发送一个 SYN包(syn=k),即SYN+ACK包,此时服务器进入SYN_RECV状态; 第三次握手:客户端收到服务器的SYN+ACK包,向服务器发送确认包...