在看剑指offer的时候,感觉这三个题目很像,都是用哈希表可以解决,所以把这三个题整理出来,以供复习。

  剑指offer35题:第一个只出现一次的字符

  题目描述:在字符串中找出第一个只出现一次的字符。如输入“abaccdeff”,则输出‘b’.

  题目分析:统计字符串每个字符出现的次数,然后找出第一个只出现一次的字符。我们可以定义一个哈希表,这个哈希表的键值key是字符,value是该字符出现的次数。这样我们需要对字符串扫描两次,第一次扫描字符串时,每扫描一个字符就在哈希表对应项中把次数加1.第二次扫描时,每扫描一个字符就能从该哈希表中该字符出现的次数。这样没扫描一遍时间复杂度为O(n),扫描两次的总时间复杂度仍为O(n).由于数组大小为常数,所以空间复杂度为O(1).

  代码如下:

#include<iostream>
using namespace std;
char FirstNotReaptingchar(char* pString)
{
    if (pString == NULL)
        return '\0';
    const int tablesize = 256;                   //总共有256个字符
    unsigned int hashtable[tablesize];
    for (unsigned int i = 0; i < tablesize; ++i)      //初始化
    {
        hashtable[i] = 0;
    }

char* hashKey = pString;
    while (*hashKey != '\0')                  //第一次扫描字符串,统计相应字符出现的次数
    {
        hashtable[*(hashKey++)]++;
    }
    hashKey = pString;
    while (*hashKey != '\0')       //第二次扫描字符串,得出相应字符出现的次数并判断
    {
        if (hashtable[*hashKey] == 1)
            return *hashKey;
            hashKey++;
    }
    return '\0';
}
void main()
{
    char ch = FirstNotReaptingchar("abaccdeff");
    printf("%c\n", ch);
}

  剑指offer55题:字符流中第一个不重复的字符

  题目描述:请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当字符流中只读出前两个字符“go”时,第一个只出现一次的字符是‘g’。当从该字符流中读出前六个字符“google”时,第一个只出现一次的字符是‘l’.

  分析:我们可以看到这个题跟上面的题很像,因此可以用同样的数据结构哈希表来解决这个问题。由于字符只有256个,我们可以定义一个长度为256的哈希表。

  #include<iostream>
using namespace std;
class solution
{
public:
    solution()
        :index(0)
    {
        for (int i = 0; i < 256; ++i)
            hashtable[i] = -1;
    }

void Insert(char ch)
    {
        if (hashtable[ch] == -1)                          //如果hashtable[ch]==-1,表示没有这个字符
            hashtable[ch] = index;         //如果hashtable[ch]==-2,表示这个字符出现多次
         else if (hashtable[ch] >= 0)                    //如果hashtable[ch]>=0,表示这个字符只出现过一次
            hashtable[ch] = -2;
        index++;
    }
    
    char FirstapearringOnce()
    {
        char ch = '\0';
        int minIndex = numeric_limits<int>::max();   //标准模板库里面,表示取整型的最大值。
        for (int i = 0; i < 256; ++i)
        {
            if (hashtable[i]>=0 && hashtable[i] < minIndex)
            {
                ch = (char)i;
                minIndex = hashtable[i];
            }
        }
        return ch;
    }
private:
    int index;
    int hashtable[256];
};
void main()
{
    solution s;
    s.Insert('g');
    s.Insert('o');
    /*s.Insert('o');
    s.Insert('g');
    s.Insert('l');
    s.Insert('e');*/
    char ch=s.FirstapearringOnce();
    printf("%c\n", ch);
}

  剑指offer51题:数组中重复的数字

  题目描述:在一个长度为n的数组里面的所有的数字都在0到n-1的范围内。数组中某些数字是重复的,但是不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如,如果输出长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3.

  分析:这道题一看,就可以通过哈希表统计出每个数字出现的次数,然后找出次数大于1的数字。但是这里有个问题是,哈希表要开辟多大呢?我们知道哈希表是静态的,当输入的数据个数与哈希表大小不匹配时,是无法解决的。所以我们可以考虑书上提供的思路。以数组{2,3,1,0,2,5}为例,数组的第0个数字是2(从零开始计数,和数组的下标保持一致),与他的下标不等,于是把他与下标为2的数字交换,交换后的数组是{1,3,2,0,2,5,3}...依次类推得到数组{0,1,2,3,2,5,3}。我们可以看到下标为1,2,3的三个数字分别为1,2,3,他们的下表和数值都相等,因此不需要做任何操作。接下来扫描到下标为4的数字2.由于他的数值和下标不相等,所以比较他和下标为2的数字。此时下标为2的数字也是2,也就是说,下标为2和下标为4的两个位置都出现了,因此找到一个重复的数字。

  代码:

#include<iostream>
using namespace std;
bool FindReaptNum(int* a,int n,int* value)
{
    if (a == NULL || n < 0)
        return false;
    for (int i = 0; i < n; ++i)
    {
        if (a[i]<0 || a[i]>n - 1)
            return false;
    }
    const int tablesize = n;
    for (int i = 0; i < n; ++i)
    {
        while (a[i] != i)
        {
            if (a[i] = a[a[i]])
            {
                *value = a[i];
                return true;
            }

int tmp = a[i];
            a[i] = a[tmp];
            a[tmp] = tmp;
        }
    }
    return false;
}
void main()
{
    int a[] = { 2, 3, 1, 0, 2, 5, 3 };
    int* value=NULL;
    int num=FindReaptNum(a, sizeof(a)-1,value);
    printf("%d \n",num);
}

  总结:综上三个题目,我们可以了解到,使用哈希表解决问题时,应统计字符的出现次数,而统计整数数组时是不可以的,必须重新找其他思路。

04-14 05:55