【剑指offer】字符流中第一个不重复的字符

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
如果当前字符流没有存在出现一次的字符，返回#字符。

解题思路

方法1:

最简单的想法，用字符串str记录字符流中的每一个字符ch，同时利用一个数组hash记录每一个字符ch对应出现的次数，即hash[ch]，直至字符流中的所有字符被读取。然后，按照str中的字符顺序，遍历hash，找到第一个等于只出现一次的字符，即第一个hash[ch]=1对应的字符ch，返回。若没有存在出现一次的字符，则返回#。

注：标准ASCII共有128个字符，还有128个扩展ASCII以表示特殊符号字符、外来语字符和图形符号。在这题里，hash的大小设为128即可满足题意。

class Solution
{
public:
    string str;
    char hash[128] = {0};
  //Insert one char from stringstream
    void Insert(char ch)
    {
        str += ch;
        hash[ch]++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        for(char ch:str){
            if(hash[ch] == 1){
                return ch;
            }
        }
        return '#';
    }

};

说明：

for(char ch:str){
    ...
}

//相当于
char ch;
for(int i=0;i<str.length();i++){
    ch = str[i]
}

方法2:

这是借鉴讨论区的方法。

思路：
1、用一个128大小的数组统计每个字符出现的次数
2、用一个队列，如果第一次遇到ch字符，则插入队列；其他情况不在插入
3、判断队首元素是否只出现一次，如果是，直接返回；否则删除首元素，继续第3步骤

class Solution
{
public:
  //Insert one char from stringstream
    void Insert(char ch)
    {
         ++hashArray[ch-'\0'];
        if( hashArray[ch-'\0'] == 1){
            data.push_back(ch);
        }
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        while( !data.empty() && hashArray[data.front()] >= 2 ){
            data.pop_front();
        }
        if( data.empty() )
            return '#';
        return data.front();
    }
 
    private:
    unsigned char hashArray[128];
    deque<char> data;
};

方法2中使用了双向开口的deque队容器，也就是可以在队列的头尾两端分别做元素的插入和删除操作。vector是单向的队容器，若要在头部插入元素，则效率很低。

deque和vector容器的差异有：
(1) deque可以以常数项实践对头部进行元素的插入和删除操作；vector不行，服从先进先出 (FIFO) 原则。
(2) deque随时可以增加一段新的空间，是由动态的分段连续空间组成的；vector如果空间不足，则要重新配置一块更大的空间，将原来的元素复制到新的空间中，然后释放原来的空间。
(3) deque的迭代器不是普通的指针，运算会较为复杂，不常用。

关于deque的一些常用操作：

//初始化
deque<T> deqT;//默认构造形式

// 大小操作
deqT.size();//返回容器中元素的个数

deqT.empty();//判断容器是否为空

//数据的存取
deqT.at(idx);//返回索引idx所指的数据

deqT.front();//返回第一个数据。

deqT.back();//返回最后一个数据

//双端的插入和删除
deqT.push_back(elem);//在容器尾部添加一个数据

deqT.push_front(elem);//在容器头部插入一个数据

deqT.pop_back();//删除容器最后一个数据

deqT.pop_front();//删除容器第一个数据

//插入操作
deqT.insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。

deqT.insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。

//删除操作
deqT.clear();//删除所有数据

deqT.erase(beg,end);//删除[beg,end)的数据，返回下一个数据的位置。

deqT.erase(pos);//删除pos位置的数据，返回下一个数据的位置。

参考：
[1]: https://www.nowcoder.com/profile/320158/codeBookDetail?submissionId=1500461
[2]: https://blog.csdn.net/weixin_42462202/article/details/87537503