- 浏览: 140916 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
Jonathan樊:
请LZ不要简单的Copy过来,好吧?起码编辑一下啊~~该加的超 ...
直接拿来用!最火的Android开源项目 -
tao71535:
学习了、
不过为还是觉得看视频做例子、
比较好、、
Intent总结
题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。 分析:这道题是2006年google的一道笔试题。
看到这道题时,最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较,如果在后面没有发现重复的字符,则该字符就是只出现一次的字符。如果字符串有n个字符,每个字符可能与后面的O(n)个字符相比较,因此这种思路时间复杂度是O(n2)。我们试着去找一个更快的方法。
由于题目与字符出现的次数相关,我们是不是可以统计每个字符在该字符串中出现的次数?要达到这个目的,我们需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数,也就是说这个容器的作用是把一个字符映射成一个数字。在常用的数据容器中,哈希表正是这个用途。
哈希表是一种比较复杂的数据结构。由于比较复杂,STL中没有实现哈希表,因此需要我们自己实现一个。但由于本题的特殊性,我们只需要一个非常简单的哈希表就能满足要求。由于字符(char)是一个长度为8的数据类型,因此总共有可能256 种可能。于是我们创建一个长度为256的数组,每个字母根据其ASCII码值作为数组的下标对应数组的对应项,而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256,以字符ASCII码为键值的哈希表。
我们第一遍扫描这个数组时,每碰到一个字符,在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时,就能直接从哈希表中得到每个字符出现的次数了。
参考代码如下:
看到这道题时,最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较,如果在后面没有发现重复的字符,则该字符就是只出现一次的字符。如果字符串有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 = 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; }
public static char FirstNotRepeatingChar(String str) { if(str == null || str.equals("")) return 0; int []counts = new int[256]; char ch; int index; for(int i=0; i < str.length();i++) { ch = str.charAt(i); index = (int)ch; counts[index]++; } for(int i =0; i< str.length(); i++) { ch = str.charAt(i); index = (int)ch; if(counts[index] == 1) return ch; } return 0; }
发表评论
-
微软等数据结构+算法面试100题
2011-02-23 17:48 1896微软等100题系列V0.1版终于结束了。 从2010年10月 ... -
百度11月4日网上笔试题及答案
2010-10-27 22:27 1190编程: 用C语言实现一个revert函数,它的功能是将输入的字 ... -
程序员面试题精选(18)-用两个栈实现队列
2009-08-15 12:01 1883题目:某队列的声明如 ... -
程序员面试题精选(17)-把字符串转换成整数
2009-08-15 12:00 2350题目:输入一个表示整数的字符串,把该字符串转换成整数并输出。例 ... -
程序员面试题精选(16)-O(logn)求Fibonacci数列
2009-08-15 11:59 2580题目:定义Fibonacci数列如下: / ... -
程序员面试题精选(15)-含有指针成员的类的拷贝
2009-08-15 11:57 1459题目:下面是一个数组 ... -
程序员面试题精选(14)-圆圈中最后剩下的数字
2009-08-15 11:55 2281题目:n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始 ... -
程序员面试题精选(12)-从上往下遍历二元树
2009-08-15 11:49 1173题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按 ... -
程序员面试题精选(11)-求二元查找树的镜像
2009-08-15 11:43 1185题目:输入一颗二元查 ... -
程序员面试题精选(10)-在排序数组中查找和为给定值的两个数字
2009-08-15 11:40 1880题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两 ... -
程序员面试题精选(09)-查找链表中倒数第k个结点
2009-08-15 11:30 1700题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数 ... -
程序员面试题精选(08)-求1+2+...+n
2009-08-08 21:18 2627题目:求1+2+…+n,要求 ... -
程序员面试题精选(07)-翻转句子中单词的顺序
2009-08-08 21:17 1869题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺 ... -
程序员面试题精选(06)-判断整数序列是不是二元查找树的后序遍历结果
2009-08-08 21:15 1497题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历 ... -
程序员面试题精选(05)-查找最小的k个元素
2009-08-08 21:14 1708题目:输入n个整数,输出其中最小的k个。 例如输入1,2,3, ... -
程序员面试题精选(04)-在二元树中找出和为某一值的所有路径
2009-08-08 21:12 1248题目:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到 ... -
程序员面试题精选(03)-求子数组的最大和
2009-08-08 21:10 1867题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个 ... -
程序员面试题精选(02)-设计包含min函数的栈
2009-08-08 21:08 1768题目:定义栈的数据结构,要求添加一个min函数,能够得到栈的最 ... -
程序员面试题精选(01)-把二元查找树转变成排序的双向链表
2009-08-08 20:58 1900题目:输入一棵二元查 ...
相关推荐
[原]《程序员面试题精选》05.输出一个字符串的所有子串 题目:给定一个字符串,输出其所有子字符串,例如给定字符串abc,则输出 :a,b,c,d,ab,bc,cd,abc,bcd,abcd。 分析:今天看到csdn博客上面的一题,...
面试题13:建立一个二叉树 面试题14:计算一棵二叉树的深度 面试题15:在二元树中找出和为某一值的所有路径 第11章 排序 11.1 插入排序 面试题1:编码实现直接插入排序 面试题2:编码实现希尔(Shell)排序 11.2 ...
第一篇(第1章)介绍了求职面试前都需要做好哪些准备工作:如何做好自己的职业规划;掌握面试的流程,在以后的面试中不会感到陌生,消除恐惧;怎样制作一个令人满意、访问量高的简历;去参加面试的时候着装上都需要...
字符存到新文件的第一个字符 以此类推 3 main主函数执行完毕后 是否可能会再执行一段代码 (朗讯的一道笔试题) 答案:可以 可以用 onexit 注册一个函数 它会在main 之后执行; 如果你需要加入一段在main退出后执行...
程序员面试攻略 【目录】 <br>前言 第1章 求职过程 第2章 程序设计面试题的解答思路 第3章 链表 第4章 树和图 第5章 数组与字符串 第6章 递归算法 第7章 其他程序设计问题 第8章 与...
第一章 字符串 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 寻找最小的...
独辟蹊径,角度很好,尤其适合我们要找一个好工作的想法,你为公司做了很多事情,也学了很多技术,可是 面试的题目你不一定能够过关,因为面试考题角度特别。要提高自己的生存能力,还是多研究一下吧。我看了前面的...
C++面试题 1.是不是一个父类写了一个virtual 函数,如果子类覆盖它的函数不加virtual ,也能实现多态? virtual修饰符会被隐形继承的。 private 也被集成,只事派生类没有访问权限而已 virtual可加可不加 子类的...
独辟蹊径,角度很好,尤其适合我们要找一个好工作的想法,你为公司做了很多事情,也学了很多技术,可是 面试的题目你不一定能够过关,因为面试考题角度特别。要提高自己的生存能力,还是多研究一下吧。我看了前面的...
第一章 求职过程 第二章 程序设计面试题的解答题思路 第三章 链表 第四章 树和图 第五章 数组和字符串 第六章 递归算法 第七章 其它程序设计问题 第八章 与计数、测量、排序有关的智力题 第九章 与图形和空间有关的...
写一个方法,实现字符串的反转,如:输入abc,输出cba 写一个方法,实现字符串的替换,如:输入bbbwlirbbb,输出bbbhhtccc。 3.数据类型之间的转换 如何将数值型字符转换为数字(Integer,Double) 如何将数字...
总结Python基础面试题全文共6页,当前为第1页。总结Python基础面试题全文共6页,当前为第1页。总结Python基础面试题 总结Python基础面试题全文共6页,当前为第1页。 总结Python基础面试题全文共6页,当前为第1页。 1...
本压缩包主要内容为c#教程(书籍)及一些经典资料,主要包括...各个公司面试题(214题) 23种设计模式.pdf c++笔试面试宝典2009版.doc 程序员面试宝典.pdf 高质量C++-C编程指南.mht 注意:共有两个分卷,这是分卷2。
本压缩包主要内容为c#教程(书籍)及一些经典资料,主要包括...各个公司面试题(214题) 23种设计模式.pdf c++笔试面试宝典2009版.doc 程序员面试宝典.pdf 高质量C++-C编程指南.mht 注意:共有两个分卷,这是分卷1。
【面试题库网整理 .net 面试题(附答案)(四)】 7. 某一密码仅使用K、L、M、N、O共5个字母,密码中的单词从左向右排列,密码单词必须遵循如下规则: (1) 密码单词的最小长度是两个字母,可以相同,也可以不同 ...
程序员面试刷题的书哪个好 有了这个列表,程序员不愁没练手的小项目了 实现文章“有了这个列表,程序员不愁没练手的小项目了” 个人对的这个的实现Demo 初衷 这个列表原本首发在伯乐在线的一篇译文:。2016年9月21日...
程序员刷最多道题可以面试#SOURCE 1. geeksforgeeks - 面试中的 10 大算法 图形 广度优先搜索 (BFS) 深度优先搜索 (DFS) 从源到所有顶点的最短路径Dijkstra 从每个顶点到每个其他顶点的最短路径Floyd Warshall 在图...
第二次握手:服务器收到syn包,必须确认客户的SYN(ack=j+1),同时自己也发送一个 SYN包(syn=k),即SYN+ACK包,此时服务器进入SYN_RECV状态; 第三次握手:客户端收到服务器的SYN+ACK包,向服务器发送确认包...
然而可以创建一个变量,其类型是一个抽象类,并让它指向具体子类的一个实例。不能有抽象构造函数或抽象静态方法。Abstract 类的子类为它们父类中的所有抽象方法提供实现,否则它们也是抽象类为。取而代之,在子类中...
第一章 关键 字............................................................................................. ...................................... 9 1.1,最宽恒大量的关键字----auto......................