厦门建设与管理局网站,wordpress不用缓存,福州企业网站建设专业服务,做网站怎么拿框架的原代码字符流中第一个不重复的字符_牛客题霸_牛客网 描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如#xff0c;当从字符流中只读出前两个字符 go 时#xff0c;第一个只出现一次的字符是 g 。当从该字符流中读出前六个字符 “google当从字符流中只读出前两个字符 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) {sch;mp[ch];}//return the first appearence once char in current stringstreamchar FirstAppearingOnce() {for(auto e : s)if(mp[e] 1)return e;return #;}mapchar, 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 #;}queuechar q;mapchar, int mp;
};
