- 浏览: 913464 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (537)
- Java SE (114)
- Struts (18)
- Hibernate (25)
- Spring (3)
- Page_Tech (41)
- Others (87)
- Database (29)
- Server (24)
- OpenSource_Tools (15)
- IDE_Tool (22)
- Algorithm (28)
- Interview (22)
- Test (28)
- Hardware (1)
- Mainframe (25)
- Web application (4)
- Linux (3)
- PHP (17)
- Android (1)
- Perl (6)
- ubuntu (1)
- Java EE (9)
- Web Analysis (5)
- Node.js (2)
- javascript (2)
最新评论
-
一键注册:
request.getRequestURL()和request.getRequestURI() -
SuperCustomer:
...
SED的暂存空间和模式空间 -
juyo_ch:
讲得挺好理解的,学习了
java 死锁及解决 -
chinaalex:
最后一题答案正确,但是分析有误.按照如下过程,上一行为瓶,下一 ...
zz智力题 -
liaowuxukong:
多谢博主啦,弱弱的了解了一点。
C++/Java 实现多态的方法(C++)
题目:在一个字符串中找到第一个只出现一次的字符。如输入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 = 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;
- }
/////////////////////////////////////////////////////////////////////// // 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;
- }
发表评论
-
IGT JAVA Test
2012-06-18 10:18 01. static synchronized vs synch ... -
zz IBM 面试问题
2012-05-30 14:31 9651.JAVA内存回收机制 2.抽象类与接口的区别 3. ... -
面试的准备与发挥
2012-04-26 10:00 870面试是一场智力的较 ... -
栈内存和堆内存
2010-10-21 11:55 790堆:顺序随意栈:先进 ... -
淘宝面试的几个算法题
2010-10-21 11:27 1476一、给你1副扑克牌,你 ... -
程序员面试题精选(18)-用两个栈实现队列
2010-10-18 22:45 1089题目:某队列的声明如下: C++代码 t ... -
程序员面试题精选(17)-把字符串转换成整数
2010-10-18 22:44 999题目:输入一个表示整 ... -
程序员面试题精选(16)-O(logn)求Fibonacci数列
2010-10-18 22:41 1825题目:定义Fibonacci数列如下: / ... -
程序员面试题精选(15)-含有指针成员的类的拷贝
2010-10-18 22:41 884题目:下面是一个数组类的声明与实现。请分析这个类有什么问题,并 ... -
程序员面试题精选(14)-圆圈中最后剩下的数字
2010-10-18 22:40 1449题目:n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始 ... -
程序员面试题精选(12)-从上往下遍历二元树
2010-10-18 22:37 965题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按 ... -
程序员面试题精选(11)-求二元查找树的镜像
2010-10-18 22:36 1341题目:输入一颗二元查 ... -
程序员面试题精选(10)-在排序数组中查找和为给定值的两个数字
2010-10-18 22:33 1029题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两 ... -
程序员面试题精选(09)-查找链表中倒数第k个结点
2010-10-18 22:32 1144题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数 ... -
程序员面试题精选(08)-求1+2+...+n
2010-10-18 22:31 980题目:求1+2+…+n,要求不能使用乘除法、for、while ... -
程序员面试题精选(07)-翻转句子中单词的顺序
2010-10-18 22:30 1174题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺 ... -
程序员面试题精选(06)-判断整数序列是不是二元查找树的后序遍历结果
2010-10-18 22:27 781题目:输入一个整数数 ... -
程序员面试题精选(05)-查找最小的k个元素
2010-10-18 22:24 1439题目:输入n个整数,输出其中最小的k个。 例如输入1,2,3, ... -
程序员面试题精选(04)-在二元树中找出和为某一值的所有路径
2010-10-18 22:22 850题目:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到 ... -
程序员面试题精选(03)-求子数组的最大和
2010-10-18 22:20 850题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个 ...
相关推荐
### JAVA程序员面试题5知识点详解 #### 一、JSP和Servlet的相同点与不同点及其联系 **相同点:** - **都是基于Java的技术**:JSP和Servlet都使用Java语言编写,运行在Java虚拟机(JVM)上。 - **处理HTTP请求**:...
【程序员面试题精选100题】是一份中文Word文档,包含了针对程序员的100道面试题目,这些题目详细解答了如何准备编程面试,尤其是技术面试环节。面试是求职过程中至关重要的一环,它能让雇主直接评估应聘者的技能和...
ASP.NET 初级程序员面试题涉及了多个核心概念和技术,以下是对这些知识点的详细解析: 1. 访问修饰符:`private`、`protected`、`public`、`internal`是C#中的访问控制修饰符,它们决定了类成员的可见性。 - `...
代码示例中使用`strcpy`函数将字符串`"hello"`复制到了一个只分配了一个字符空间的`char`变量`a`的地址上,这将导致未定义行为,因为`strcpy`不会检查目标缓冲区的大小,可能会发生内存溢出。 ### 5. 字符串常量的...
在程序员面试过程中,面试官常常会提出各种各样的问题来测试候选人的技能和思维能力。这些题目涵盖了数据结构、算法、编程语言特性等多个方面。下面我们将详细探讨两个常见的面试题及其解题思路。 第一个题目是“从...
- `String str=""`:表示`str`变量指向一个空字符串对象。 #### 26. 使用运算符"=="和方法equals()进行比较对象的区别? - `==`:比较两个对象的引用是否相等。 - `equals()`:比较两个对象的内容是否相等。 #### ...
1. **初识Java**:这部分通常涉及Java的历史、特点、环境配置以及第一个"Hello, World!"程序的编写,是入门Java的起点。 2. **数据类型和运算符**:讲解Java中的基本数据类型(如整型、浮点型、字符型、布尔型),...
13. **第一个只出现一次的字符**:找出字符串中第一个只出现一次的字符,可以使用哈希表记录字符出现次数,然后遍历查找。 14. **圆圈中最后剩下的数字**:多人围成一圈按顺序报数,报到特定数的人离开,直到只剩一...
面试题13:建立一个二叉树 面试题14:计算一棵二叉树的深度 面试题15:在二元树中找出和为某一值的所有路径 第11章 排序 11.1 插入排序 面试题1:编码实现直接插入排序 面试题2:编码实现希尔(Shell)排序 11.2 ...
在当前的IT行业中,Java程序员面试已经逐步升级为考察应聘者对多个技术栈的综合理解和应用能力。以下内容根据提供的文件信息整理出的Java程序员面试知识点: 1. MyBatis框架 - MyBatis定义:MyBatis是一个支持定制...
然后,将这个结果与数组中的每一个元素进行异或,可以找到一个数字,使得它与另一个出现一次的数字异或后为0,这样就可以分别找到这两个数字。 5. **在从1到n的正数中1出现的次数**:这是一个关于位运算的问题。...
根据提供的文件信息,我们可以整理出一系列与Java程序员面试相关的知识点,包括但不限于基本数据类型、字符串操作、集合框架、异常处理等内容。下面是详细的知识点解析: ### 基本数据类型 1. **基本数据类型与...
### JAVA程序员面试题详解 #### 1. JSP与Servlet的区别及关系 - **定义**: - **Servlet**:是一种服务器端的轻量级通用技术组件,它主要用于动态生成Web页面,处理客户端请求,并返回响应。Servlet是用Java语言...
【Java程序员面试题详解】 1. 数据库操作: - 创建表A时,要设置m字段为唯一(UNIQUE)且非空(NOT NULL),n字段初始值为0,m、n、y字段不可为空(NOT NULL)。 - 修改表A的n字段初始值,可以通过ALTER TABLE...
以下是一些可能出现在"java程序员面试宝典第二版机密面试题"中的关键知识点详解: 1. **Java基础**: - **数据类型**:包括基本类型和引用类型,了解它们的内存分配和作用范围。 - **变量**:理解变量的作用域和...
【程序员经典面试题】涉及到的是两个常见的编程问题,一个是寻找字符串中第一个只出现一次的字符,另一个是层次遍历二叉树。这两个问题都考察了程序员对于数据结构和算法的理解及应用。 首先,第一个问题——寻找...
《CareerCup: Cracking the Coding Interview》第四版是一本广受程序员喜爱的面试准备指南,专注于解决顶级软件公司的编程面试问题。这本书包含了大量实际的编程挑战,旨在帮助程序员提升解决问题的能力,熟悉面试...