题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。
例如,当从字符流中只读出前两个字符 go 时,第一个只出现一次的字符是 g。
当从该字符流中读出前六个字符 google 时,第一个只出现一次的字符是 l。
如果当前字符流没有存在出现一次的字符,返回 # 字符。
数据范围
字符流读入字符数量 [0,1000]。
样例
输入:"google"
输出:"ggg#ll"
解释:每当字符流读入一个字符,就进行一次判断并输出当前的第一个只出现一次的字符。
算法1
(哈希+队列优化) $O(n)$
在做上一个题的时候,也在想队列优化,但是没想明白;这道题看了y总的写法之后就明白了。
C++ 代码
class Solution{
public:
unordered_map<char,int> count;
queue<int> q;
//Insert one char from stringstream
void insert(char ch)
{
if(++count[ch] > 1)
{
while(!q.empty() && count[q.front()] > 1) q.pop();
}
else
{
q.emplace(ch);
}
}
//return the first appearence once char in current stringstream
char firstAppearingOnce()
{
if(!q.empty()) return q.front();
return '#';
}
};
算法2
(自己的写法,哈希+遍历) $O(n^2)$
重复上道题的写法,没什么新意
C++ 代码
class Solution{
public:
string s;
unordered_map<char, int> mp;
//Insert one char from stringstream
void insert(char ch)
{
mp[ch]++;
s.push_back(ch);
}
//return the first appearence once char in current stringstream
char firstAppearingOnce()
{
for(auto c:s)
{
if(mp[c] == 1) return c;
}
return '#';
}
};