《剑指Offer》字符流中第一个不重复的字符
程序员文章站
2022-05-12 22:22:06
...
实现下面两个函数,Insert
函数插入一个字符,FirstAppearingOnce
函数返回数据流中第一个出现的字符。
class Solution
{
public:
//Insert one char from stringstream
void Insert(char ch)
{
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
}
};
方法:使用一个链表保存字符流中不重复的字符,其中,链表的倒数第一个元素是第一个不重复的字符,哈希表存储字符与字符在链表中的位置。
unordered_map<char, list<char>::iterator> map;
list<char> L;
- 当第1个字符
g
读入时,哈希表为空,哈希表中找不到g
,则直接将g
插入链表的头部。且将其iterator
放入哈希表中,map['g']=L.begin();
FirstAppearingOnce()
返回g
. - 当第2个字符
o
读入时,哈希表中没有o
,则直接将o
插入链表头部,且将其iterator
放入哈希表,此时链表为o->g
.FirstAppearingOnce()
返回g
. - 当第3个字符
o
读入时,这时哈希表中有o
,需要将链表中的o
删除,因为链表只保存出现次数为1次的字符,此时链表为g
.FirstAppearingOnce()
返回g
. - 当第4个字符
g
读入时,这时哈希表中有g
,需要将链表中的g
删除,此时链表为空.FirstAppearingOnce()
返回#
. - 当第5个字符
l
读入时,这时哈希表中没有l
,将l
插入链表。FirstAppearingOnce()
返回l
.
以此类推。
class Solution
{
public:
//Insert one char from stringstream
void Insert(char ch)
{
if(map.count(ch)) {
L.erase(map[ch]);
} else {
L.insert(L.begin(), ch);
map[ch] = L.begin();
}
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
if(L.empty()) {
return '#';
} else {
return *(L.rbegin());
}
}
unordered_map<char, list<char>::iterator> map;
list<char> L;
};
上一篇: 网站运营:浅析网站的定位与盈利模式问题
下一篇: 电子商务网站推广的方法和经验分享
推荐阅读
-
剑指offer27:按字典序打印出该字符串中字符的所有排列
-
PHP获取字符流中第一个不重复字符的方法
-
剑指offer JZ54 字符流中第一个不重复的字符 Python 多解
-
剑指 offer代码最优解析——面试题35第一个只出现一次的字符
-
20200329-剑指offer-面试题48. 最长不含重复字符的子字符串(滑动窗口)
-
第一个只出现一次字符的位置 牛客网 剑指Offer
-
剑指offer——第一个只出现一次的字符位置
-
《剑指offer》-- 两个链表的第一个公共结点、链表中环的入口结点、删除链表中的重复结点
-
剑指offer两个面试案例 把字符串转换成整数 树中两个节点的最低公共祖先
-
剑指 Offer 48. 最长不含重复字符的子字符串