《剑指offer》刷题笔记（字符串）：字符流中第一个不重复的字符

发表于 | 更新于: | 分类于 | 阅读次数:
字数统计: 507 | 阅读时长 ≈ 2

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

输出描述

如果当前字符流没有存在出现一次的字符，返回#字符。

解题思路

好吧，我是第一次见这种需要写部分测试函数的题目。

题目很简单，用hash表来实现，其实hash表的键值为输入字符的ASCII码，hash的值初始化为-1，出现一次则设置为该字符在字符串中的位置，出现两次以上则设置为-2。

最后搜索的时候，根据hash表的值就可以找到第一个不重复的字符。

  • occurrence[i] = -1: 这个字符不存在；
  • occurrence[i] = -2: 这个字符出现了多次；
  • occurrence[i] >= 0: 这个字符只出现一次。

需要注意的是，因为我们要求如果当前字符流没有存在出现一次的字符，返回#字符，所以我们初始化字符时应该设置为’#’而不是’\0’。

C++版代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution
{
public:
    Solution()
    {
        memset(occurrence, -1, sizeof(occurrence));
    }
    //Insert one char from stringstream
    void Insert(char ch)
    {
        if(occurrence[ch] == -1)
            occurrence[ch] = index;
        else if(occurrence[ch] >= 0)
            occurrence[ch] = -2;
        index++;
    }
    //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        char ch = '#';
        int minIndex = numeric_limits<int>::max();
        for(int i = 0; i < 256; ++i){
            if(occurrence[i] >= 0 && occurrence[i] <= minIndex){
                ch = (char)i;
                minIndex = occurrence[i];
            }
        }
        return ch;
    }
private:
    int occurrence[256];
    int index;
};

系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～

完的汪(∪｡∪)｡｡｡zzz

0%