欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

《剑指Offer》字符流中第一个不重复的字符

程序员文章站 2022-05-12 22:22:06
...

《剑指Offer》字符流中第一个不重复的字符
实现下面两个函数,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;
};
相关标签: LeetCode