剑指Offer 第27天 JZ75 字符流中第一个不重复的字符

字符流中第一个不重复的字符_牛客题霸_牛客网

 

描述

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

数据范围：字符串长度满足 1≤n≤1000 1≤n≤1000  ，字符串中出现的字符一定在 ASCII 码内。
进阶：空间复杂度 O(n) O(n)  ，时间复杂度 O(n) O(n) 

后台会用以下方式调用 Insert 和 FirstAppearingOnce 函数

string caseout = "";

1.读入测试用例字符串casein

2.如果对应语言有Init()函数的话，执行Init() 函数

3.循环遍历字符串里的每一个字符ch {

Insert(ch);

caseout += FirstAppearingOnce()

}

2. 输出caseout，进行比较。

返回值描述：

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

示例1

输入：

"google"

返回值：

"ggg#ll"

示例2

输入：

"abcdee"

返回值：

"aaaaaa"

【解法一】使用哈希表 + 字符串

class Solution
{
public://Insert one char from stringstreamvoid Insert(char ch) {s+=ch;mp[ch]++;}//return the first appearence once char in current stringstreamchar FirstAppearingOnce() {for(auto &e : s)if(mp[e] == 1)return e;return '#';}map<char, int> mp;string s;
};

【解法二】使用队列 + 哈希表

class Solution
{
public://Insert one char from stringstreamvoid Insert(char ch) {if(mp.find(ch)==mp.end())q.push(ch);mp[ch]++;}//return the first appearence once char in current stringstreamchar FirstAppearingOnce() {while(!q.empty()){if(mp[q.front()]==1)return q.front();elseq.pop();}return '#';}queue<char> q;map<char, int> mp;
};