`

程序员面试题精选(13)-第一个只出现一次的字符

阅读更多

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

C++代码 复制代码
  1. ///////////////////////////////////////////////////////////////////////   
  2. // Find the first char which appears only once in a string   
  3. // Input: pString - the string   
  4. // Output: the first not repeating char if the string has, otherwise 0   
  5. ///////////////////////////////////////////////////////////////////////   
  6. char FirstNotRepeatingChar(char* pString)   
  7. {   
  8.       // invalid input   
  9.       if(!pString)   
  10.             return 0;   
  11.   
  12.       // get a hash table, and initialize it    
  13.       const int tableSize = 256;   
  14.       unsigned int hashTable[tableSize];   
  15.       for(unsigned int i = 0; i < tableSize; ++ i)   
  16.              hashTable = 0;   
  17.   
  18.       // get the how many times each char appears in the string   
  19.       char* pHashKey = pString;   
  20.       while(*(pHashKey) != '\0')   
  21.              hashTable[*(pHashKey++)] ++;   
  22.   
  23.       // find the first char which appears only once in a string   
  24.        pHashKey = pString;   
  25.       while(*pHashKey != '\0')   
  26.        {   
  27.             if(hashTable[*pHashKey] == 1)   
  28.                   return *pHashKey;   
  29.   
  30.              pHashKey++;   
  31.        }   
  32.   
  33.       // if the string is empty    
  34.       // or every char in the string appears at least twice   
  35.       return 0;   
  36. }   
///////////////////////////////////////////////////////////////////////
// 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;
} 

 

Java代码 复制代码
  1. public static char FirstNotRepeatingChar(String str)   
  2.     {   
  3.         if(str == null || str.equals(""))   
  4.             return 0;   
  5.         int []counts = new int[256];   
  6.         char ch;   
  7.         int index;   
  8.         for(int i=0; i < str.length();i++)   
  9.         {   
  10.             ch = str.charAt(i);   
  11.             index = (int)ch;   
  12.             counts[index]++;   
  13.         }   
  14.         for(int i =0; i< str.length(); i++)   
  15.         {   
  16.             ch = str.charAt(i);   
  17.             index = (int)ch;   
  18.             if(counts[index] == 1)   
  19.                 return ch;   
  20.         }   
  21.         return 0;   
  22.     }  
分享到:
评论

相关推荐

    JAVA程序员面试题5

    ### JAVA程序员面试题5知识点详解 #### 一、JSP和Servlet的相同点与不同点及其联系 **相同点:** - **都是基于Java的技术**:JSP和Servlet都使用Java语言编写,运行在Java虚拟机(JVM)上。 - **处理HTTP请求**:...

    程序员面试题精选100题

    【程序员面试题精选100题】是一份中文Word文档,包含了针对程序员的100道面试题目,这些题目详细解答了如何准备编程面试,尤其是技术面试环节。面试是求职过程中至关重要的一环,它能让雇主直接评估应聘者的技能和...

    asp.net初级程序员面试题

    ASP.NET 初级程序员面试题涉及了多个核心概念和技术,以下是对这些知识点的详细解析: 1. 访问修饰符:`private`、`protected`、`public`、`internal`是C#中的访问控制修饰符,它们决定了类成员的可见性。 - `...

    华为程序员等面试题精选

    代码示例中使用`strcpy`函数将字符串`"hello"`复制到了一个只分配了一个字符空间的`char`变量`a`的地址上,这将导致未定义行为,因为`strcpy`不会检查目标缓冲区的大小,可能会发生内存溢出。 ### 5. 字符串常量的...

    程序员面试题精选 题很多

    在程序员面试过程中,面试官常常会提出各种各样的问题来测试候选人的技能和思维能力。这些题目涵盖了数据结构、算法、编程语言特性等多个方面。下面我们将详细探讨两个常见的面试题及其解题思路。 第一个题目是“从...

    黑马程序员入学面试题

    - `String str=""`:表示`str`变量指向一个空字符串对象。 #### 26. 使用运算符"=="和方法equals()进行比较对象的区别? - `==`:比较两个对象的引用是否相等。 - `equals()`:比较两个对象的内容是否相等。 #### ...

    百战程序员1573题及答案

    1. **初识Java**:这部分通常涉及Java的历史、特点、环境配置以及第一个"Hello, World!"程序的编写,是入门Java的起点。 2. **数据类型和运算符**:讲解Java中的基本数据类型(如整型、浮点型、字符型、布尔型),...

    程序员面试100题数据结构和算法

    13. **第一个只出现一次的字符**:找出字符串中第一个只出现一次的字符,可以使用哈希表记录字符出现次数,然后遍历查找。 14. **圆圈中最后剩下的数字**:多人围成一圈按顺序报数,报到特定数的人离开,直到只剩一...

    C/C++程序员面试指南.杨国祥(带详细书签).pdf

    面试题13:建立一个二叉树 面试题14:计算一棵二叉树的深度 面试题15:在二元树中找出和为某一值的所有路径 第11章 排序 11.1 插入排序 面试题1:编码实现直接插入排序 面试题2:编码实现希尔(Shell)排序 11.2 ...

    2021最新Java程序员面试题

    在当前的IT行业中,Java程序员面试已经逐步升级为考察应聘者对多个技术栈的综合理解和应用能力。以下内容根据提供的文件信息整理出的Java程序员面试知识点: 1. MyBatis框架 - MyBatis定义:MyBatis是一个支持定制...

    程序员面试题精选 真的很好的

    然后,将这个结果与数组中的每一个元素进行异或,可以找到一个数字,使得它与另一个出现一次的数字异或后为0,这样就可以分别找到这两个数字。 5. **在从1到n的正数中1出现的次数**:这是一个关于位运算的问题。...

    java程序员面试题大全

    根据提供的文件信息,我们可以整理出一系列与Java程序员面试相关的知识点,包括但不限于基本数据类型、字符串操作、集合框架、异常处理等内容。下面是详细的知识点解析: ### 基本数据类型 1. **基本数据类型与...

    JAVA程序员面试题(1)\JAVA程序员面试题

    ### JAVA程序员面试题详解 #### 1. JSP与Servlet的区别及关系 - **定义**: - **Servlet**:是一种服务器端的轻量级通用技术组件,它主要用于动态生成Web页面,处理客户端请求,并返回响应。Servlet是用Java语言...

    Java程序员面试题大全

    【Java程序员面试题详解】 1. 数据库操作: - 创建表A时,要设置m字段为唯一(UNIQUE)且非空(NOT NULL),n字段初始值为0,m、n、y字段不可为空(NOT NULL)。 - 修改表A的n字段初始值,可以通过ALTER TABLE...

    java程序员面试宝典第二版机密面试题

    以下是一些可能出现在"java程序员面试宝典第二版机密面试题"中的关键知识点详解: 1. **Java基础**: - **数据类型**:包括基本类型和引用类型,了解它们的内存分配和作用范围。 - **变量**:理解变量的作用域和...

    程序员经典面试题

    【程序员经典面试题】涉及到的是两个常见的编程问题,一个是寻找字符串中第一个只出现一次的字符,另一个是层次遍历二叉树。这两个问题都考察了程序员对于数据结构和算法的理解及应用。 首先,第一个问题——寻找...

    CareerCup : Cracking the Coding Interview 第四版 顶级程序员面试问题精选 (英文原版)

    《CareerCup: Cracking the Coding Interview》第四版是一本广受程序员喜爱的面试准备指南,专注于解决顶级软件公司的编程面试问题。这本书包含了大量实际的编程挑战,旨在帮助程序员提升解决问题的能力,熟悉面试...

Global site tag (gtag.js) - Google Analytics