字符流中第一个不重复的字符

剑指OFFER题18------按牛客网通过率排序

时间：2018.10.25.2157 作者：Waitt

题目

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

时间限制：1秒 空间限制：32768K 热度指数：90751

解答

1、用一个128大小的数组统计每个字符出现的次数 2、用一个队列，如果第一次遇到ch字符，则插入队列；其他情况不在插入 3、求解第一个出现的字符，判断队首元素是否只出现一次，如果是直接返回，否则删除继续第3步骤

class Solution { unsigned t[128]={0}; queue<char> c; public: //Insert one char from stringstream void Insert(char ch) { t[ch]++; if(t[ch]==1) c.push(ch); } //return the first appearence once char in current stringstream char FirstAppearingOnce() { while(c.empty()==0) { if(t[c.front()]==1) return c.front(); c.pop(); } return '#'; } };

小知识点

ch - '0’是什么意思？

ch - '0’的意思就是把一个字符的ASCII值减去字符 ‘0’ 的ASCII值，实际上就是两个整数（对应的ASCII）的减法运算，得到就是一个整数（与对应的数字相对应）。 详见：https://zhidao.baidu.com/question/428525497964613852.html 详见：https://bbs.csdn.net/topics/370014272

ASCII码表及扩展ASCII码表

0～31及127(共33个)是控制字符或通信专用字符（其余为可显示字符）；

32～126(共95个)是字符(32是空格），其中48～57为0到9十个阿拉伯数字，65～90为26个大写英文字母，97～122号为26个小写英文字母，其余为一些标点符号、运算符号等；

后128个称为扩展ASCII码，扩展ASCII 码允许将每个字符的第8 位用于确定附加的128 个特殊符号字符、外来语字母和图形符号。 详见：https://blog.csdn.net/na_tion/article/details/50148883

数组创建

char s[1000] = {0}; memset(s, ‘0’, sizeof(s)); 详见：https://zhidao.baidu.com/question/301772182.html 详见：https://bbs.csdn.net/topics/340210628