首页 > 剑指offer > Google面试题-第一个只出现一次的字符
2014
03-21

Google面试题-第一个只出现一次的字符

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

这道题是2006年google的一道笔试题。

遇到字符统计的问题,一般都应该考虑哈希(其实就是数组模拟),因此字符数量有限,一个256长度数组就够用了,也不需要哈希函数。

有了这个表,下面的就很简单了,首先遍历一遍字符串,就字符的ASCII值作为我们哈希表的键值,而数组中的value值存储每一个字符出现的次数。第二遍遍历字符串,取出第一个value值为1的键值即可。根据这种思路,我们很容易得到如下的代码:

#include<iostream>
#include<string>
#include<cstring>
using namespace std;

char FindFirstNotRepeatedChar(char *pstring)
{
    if(pstring == NULL)
        return 0;

    //定义并初始化哈希表
    const int hashLength = 256;
    unsigned int hashList[hashLength];
    for(int i = 0;i < hashLength;++i)
    {
        hashList[i] = 0;
    }

    //第一遍遍历,hash表记录每个字符出现的次数
    char *pchar = pstring;
    while(*pchar != '\0')
    {
        hashList[*pchar]++;
        pchar++;
    }

    //指针重新指向字符串的第一个字符
    pchar = pstring;

    //第二遍遍历,返回第一个次数为1的字符
    while(*pchar != '\0')
    {
        if(hashList[*pchar] == 1)
        {
            return *pchar;
        }

        pchar++;
    }

    //没有只出现一次的字符
    return 0;
}

int main()
{
    cout<<"please enter your string:"<<endl;
    const int maxSize = 100;
    char str[maxSize];
    cin>>str;

    cout<<"the first not repeated char is:"<<endl;
    cout<<FindFirstNotRepeatedChar(str)<<endl;

    return 0;
}

运行结果如下:

参考:http://zhedahht.blog.163.com/blog/static/25411174200722191722430/


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.