字符流中第一个不重复的字符（字符串）

本文主要是介绍字符流中第一个不重复的字符（字符串），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

描述

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

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

string caseout = "";

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

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

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

Insert(ch);

caseout += FirstAppearingOnce()

}

2. 输出caseout，进行比较。

返回值描述：

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

这题看到大佬分享的解题思路很好，就照搬过来啦~

方法：哈希+队列

针对题目的描述，我们先提出两个问题？

Q1. 给定一个字符串（只不过这里的字符串是可变的），如果快速判断一个字符是否存在于字符串中，如果存在，也就是重复？
Q2. 这里先不考虑重复，如果快速返回第一个字符？有没有感觉有点像先来先服务？

对于一道题，如果没有思路，就要针对题目给自己问问题。然后针对问题，来考虑需要什么样的算法或者数据结构。

A1：对于“重复问题”，惯性思维应该想到哈希或者set。对于“字符串问题”，大多会用到哈希。因此一结合，应该可以想到，判断一个字符是否重复，可以选择用哈希，在c++中，可以选择用unordered_map<char, int>

A2：对于字符流，源源不断的往池子中添加字符，然后还要返回第一个满足什么条件的字符，显然设计到了“顺序”，也就是先来的先服务，这种先进先出的数据结构不就是队列嘛。因此，这里可以用队列。

假如你已经知道了要用hash 和 queue 这两个数据结构，你可以试着自己想一想，接下来的算法过程是怎么样的？
这里我提供一个算法过程，如下：

1. 初始化一个unordered_map<char, int> mp, queue<char> q

2. 对于Insert(char ch)操作， 如果ch是第一次出现，则添加到q中，然后在mp中记录一下次数，如果不是第一次出现，也就是重复了，那么我们就没必要添加到q中，但是还是需要在mp中更新一下次数，因为之后要根据次数来判断是否重复。

3. 对于FirstAppearingOnce()操作，我们直接判断q的头部，然后在mp中检查一下，是否重复，如果没有重复，那就是我们想要的数据。否则，如果重复了，那就应该弹出头部，然后判断下一个头部是否满足要求。

class Solution
{
public:
  //Insert one char from stringstream
    queue<char> q;
    unordered_map<char, int> mp;
    void Insert(char ch)
    {
         // 如果是第一次出现， 则添加到队列中
         if (mp.find(ch) == mp.end()) {
             q.push(ch);
         }
         // 不管是不是第一次出现，都进行计数
         ++mp[ch];
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        while (!q.empty()) {
            char ch = q.front();
            // 拿出头部，如果是第一次出现，则返回
            if (mp[ch] == 1) {
                return ch;
            }
            // 不是第一次出现，则弹出，然后继续判断下一个头部
            else {
                q.pop();
            }
        }
        return '#';
    }
};

这篇关于字符流中第一个不重复的字符（字符串）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！