剑指offer刷题笔记54（python）

题目描述

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

思路1

利用一个队列和字典来实现。

代码1

class Solution: # 注意，是第一次出现的不重复的字符，不是出现一个不重复的就返回一个 # 返回对应char def __init__(self): # 设置一个字典，用来记录每个字符出现的字数 self.memory = dict() # 设置一个队列用来记录字符流的出现的顺序，元素入队的时候，相同元素只入一次队， # 即可，根据字典记录的元素出现的次数来判断元素是否出队。 self.queue = [] def FirstAppearingOnce(self): # write code here while len(self.queue) and self.memory[self.queue[0]]>1: # 循环，队列排在前面的一定是先出现的，因此，要删除出现多次的队首元素，直到遇见只出现一次的字符，返回 self.queue.pop(0) return self.queue[0] if len(self.queue) else '#' def Insert(self, char): # write code here if char not in self.memory: self.memory[char]=0 self.memory[char]+=1 if self.memory[char]==1: # 如果不等于1，说明前面已经出现过了，再次入队会造成重复，降低效率。 self.queue.append(char)

思路2

由于ASCII码有128位，扩展的ASCII码有256位，字符最多有256个（不考虑中文字符），因此我们可以利用一个长度为256的数组来实现一个类似于字典的功能。 数组的各个位置（0-256）就相当于字符的ASCII码。数组的值初始化为-1， 表示第一次读入。数组的值不为-1且大于等于0时，表示不是第一次读入，修改当前的值为-2，在读入的时候，如果碰见-2，就不再进行处理了。同时要设置一个读入顺序的指标，当元素不为-2时，将这个指标赋值给不等于-2的元素。在读取的时候要读取数组元素值不大于等于0的最小的元素，并返回这个位置所代表的字符。

代码2

# -*- coding:utf-8 -*- class Solution: def __init__(self): self. occurence = [-1 for i in range(256)] self.index = 0 # 记录当前字符的出现的前后顺序，index越小，出现的越早，返回的时候，都是出现一次的时候，要返回index最小的 # 记录当前字符的出现的前后顺序，index越小，出现的越早，返回的时候，都是出现一次的时候，要返回index最小的 def FirstAppearingOnce(self): # write code here minValue = 10000 # 设置一个超大的数，使读入的字符流的长度小于min_value minIndex = -1 for i in range(256): # 循环遍历找到数组取值大于-1的最小值，并返回minIndex if self. occurence[i] >= 0: # 表示出现过1次，-1表示没出现过，-2表示出现过多次，只有大于-1才表示只出现过一次 if self. occurence[i] < minValue: minValue = self. occurence[i] minIndex = i if minIndex >= 0: return chr(minIndex) else: # 如果minIndex仍然等于-1，表示没有数组元素>=0,即要么没出现，要么出现过多次。返回“#” return '#' def Insert(self, char): # 如果是第一出现，则将对应元素的值改为下边 if self. occurence[ord(char)] == -1: self. occurence[ord(char)] = self.index # 如果不是-1，表示之前出现过了，再次出现就不是第一次了，修改当前的数组元素值为-2 else: self. occurence[ord(char)] = -2 self.index += 1 # 每读入一个字符，index+1，表示前后顺序