字符流中第一个不重复的字符
题目
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。
输出描述:
如果当前字符流没有存在出现一次的字符，返回#字符。
方法
为了高效的解决这个问题，需要在O(1)时间内王数据容器里插入一个字符，以及更新一个字符对应的值。受第一个只出现一次的字符启发，采用哈希表来实现。
- 当哈希表中相应字符的值为1：该字符只出现1次
- 当哈希表中相应字符的值为2：该字符至少出现2次
哈希表是没有顺序的，所以还需要一个额外的栈，数组或者队列来记录字符的顺序。基于队列先进先出的性质，符合题目中“第一个”字符。所以采用哈希表和队列。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20# -*- coding:utf-8 -*-
class Solution:
# 返回对应char
def __init__(self):
self.adict={}
self.alist=[]
def FirstAppearingOnce(self):
# write code here
while len(self.alist)>0 and self.adict[self.alist[0]]==2:
self.alist.pop(0)
if len(self.alist)==0:
return '#'
return self.alist[0]
def Insert(self, char):
# write code here
if char not in self.adict:
self.adict[char]=1
self.alist.append(char)
else:
self.adict[char]=2