每行都做了详细代码解释,两种方法,通俗易懂:字符流中第一个不重复的字符
字符流中第一个不重复的字符
http://www.nowcoder.com/questionTerminal/00de97733b8e4f97a3fb5c680ee10720
方法一:
本来是想用unordered_map的,但是系统显示unordered_map无定义,可能是没有包含include<unordered_map>这个文件库。
首先定义了一个map<char, int>count;对输入的字符进行计数,其次用res标记迄今为止出现的第一个符数,如果下一次输入是得这个字符res出现重复,则将res置‘#’,重头遍历map数组,找到只出现一次的字符。
但其实是有bug的,系统没有检测出来,例如输入的是cbac,则正确输出应该是cccb,但是本程序的输出是ccca,因为map排序自动将a排在了b的前面。</unordered_map>
class Solution { public: //Insert one char from stringstream Solution() {//构造函数,初始化私有变量res res= '#'; } void Insert(char ch) { count[ch]++;//标记字符出现的次数 if (ch == res)res = '#';//如果之前标记的字符重复出现了, } //return the first appearence once char in current stringstream char FirstAppearingOnce() { if (res == '#')//如果res=='#',说明之前记录的res被重复出现了,此时需要再次遍历迭代器,寻找第一个出现的字符 { map<char, int>::iterator it = count.begin(); for (; it != count.end(); ++it) { if (it->second == 1) { res = it->first; break; } } } return res; } private: map<char, int>count;//使用map对输入的数计数 char res; //标记第一个出现一次的字符 };
方法二:
//仿照hash表实现,str存储插入的字符,hash[256]存储插入字符的个数。以其ascii位索引位,同时用string标记字符出现的次数,并初始化所有的值为0。
class Solution { public: string str; char hash[256] = {0};//因为每个字符的ascii码是不同的,所以就以其ascii位索引位,同时用string标记字符出现的次数,并初始化所有的值为0。 void Insert(char ch) { str.append( ch);//用string标记字符出现的次数,将新出现的字符插入尾部 hash[ch]++; } char FirstAppearingOnce() { for(char ch :str){//遍历插入的字符 if(hash[ch] == 1){ return ch; } } return '#'; } };