剑指offer第54题“字符流中第一个不重复的字符”

继续剑指Offer Go Go Go

Posted by Cfeng on April 4, 2019

字符流中第一个不重复的字符

题目描述

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

输出描述

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

思路

题意就是每输入一个字符,判断该字符流的第一个不重复的字符 那定义一个队列,存储字符的出现顺序,相同字符只存一次。 再定义一个数组,判断字符是否第一次出现。 在判断函数中,只要判断队首元素是否只出现一次,是就直接返回。 不是就pop,换下一个

C++实现

class Solution
{
private:
    queue<char> q;
    int arr[300]={0};
public:
  //Insert one char from stringstream
    
    void Insert(char ch)
    {
        arr[(int)ch]++;
        if(arr[(int)ch]==1){
            q.push(ch);
        }
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        while(!q.empty()){
            char ch = q.front();
            if(arr[(int)ch]==1){
                return ch;
            }
            q.pop();
        }
        return '#';
    }
};