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

剑指Offer_编程题——字符流中第一个不重复的字符

题目描述：

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

输出描述:

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

具体要求:

时间限制： C/C++ 1秒，其他语言2秒
空间限制： C/C++32M，其他语言64M

具体实现：

一、背景知识介绍：
  在做题之前，我们首先了解字符流的大概知识。字符流：就是在字节流的基础上，加上编码，形成的数据流。因为字节流在操作字符时，可能会有中文导致的乱码，所以由字节流引申出了字符流。这也就是字符流出现的意义。字符的输入流为：Reader。常用子类：FileReader；文件字符输入流常用方法：read（）、read（char[ ]）、read（char[ ] ，offset，len）。以及字符输出流： Writer；常用子类：文件字符输出流： Filewriter。文件字符输出常用方法：writer（）、writer（char[ ]）、writer（char[ ]，offset，len）、writer（string）以及flush（）刷新缓冲区。这里需要我们注意的是：close（）方法默认调用了flush（）方法，但是flush（）方法只刷新缓冲区，而close（）还会关闭IO流。
  我们在刚才解释字符流的时候，一直在提到另外的一个概念就是字节流，接下来给大家介绍二者之间的区别：字符流虽然以字节流为基础创建的，但是字节流可以支持声音，视频，图片，文本等所有文件类型，而字符流只支持文本文件。带缓冲区的字符流：BufferedReader/BufferedWriter 带缓冲区的字符输入流与字符输出流。带缓冲区的字符输入流：BufferedReader：常用方法：readLine（） 读取一行，如果为文件末尾，返回值为null。带缓冲区的字符输出流：BufferedWriter:常用方法：writer（string）将字符串写入 到输出流。 newLine（）根据系统的行分割符进行换行。
二、具体实现思路：

思路一：
  我们可以用到java中的Map+Queue来实现本题，具体用java实现如下：

import java.util.*;
public class Solution{
	private Map<Character, Integer> map = new HashMap<Character, Integer>();
	private Queue<Character> q = new LinkedList<>();
	public void Insert(char ch){
		if(map.containsKey(ch)){
			int value = map.get(ch);
			map.put(ch, ++value);
		}else{
			map.put(ch, 1);
		}
		q.offer(ch);
		while(!q.isEmpty() && map.get(q.peek()) > 1)
			q.poll();
	}
	public char FirstAppearingOnce(){
		return q.isEmpty()?'#':q.peek();
	}
}

代码效果图如图所示：

  在本代码中我们看到了q.offer() 以及 q.poll() 函数，接下来为了方便大家读懂代码，给大家介绍一下在java中队列Queue中的offer、add函数、poll函数remove函数以及peek函数和element函数的区别。首先，队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。并且通过LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。在Queue中常用的一些方法有：offer、add、poll、remove、peek以及element。首先我们介绍offer与add的区别：一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。接下来介绍poll，remove区别： remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似，但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。最后介绍peek，element区别： element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。
思路二：
  其实和思路一差不多，就是利用java中的Map+List将其实现，接下来具体用Java实现代码如下：

import java.util.*;
public class Solution{
	private Map<Character, Integer> map = new HashMap<Character, Integer>();
	private List<Character> list = new ArrayList<>();
	public void Insert(char ch){
		if(map.containsKey(ch)){
			int value = map.get(ch);
			map.put(ch,++value);
		}else
			map.put(ch, 1);
		list.add(ch);
	}
	public char FirstAppearingOnce(){
		if(list.isEmpty())
			return '#';
		for(Character c:list){
			if(map.get(c) == 1)
				return c;
		}
		return '#';
	}
}

代码效果图如图所示：

  我们在代码中看到了for(Character c:list)，为了让大家更好的理解该代码，给大家详细介绍Java中几种常用的for循环结构。在Java程序中，要“逐一处理”――或者说，“遍历”――某一个数组或Collection中的元素的时候，一般会使用一个for循环来实现（当然，用其它种类的循环也不是不可以，只是不知道是因为for这个词的长度比较短，还是因为for这个词的含义和这种操作比较配，在这种时候for循环比其它循环常用得多）。for (循环变量类型 循环变量名称 : 要被遍历的对象) 循环体；借助这种语法，遍历一个数组的操作就可以采取这样的写法。Java采用“for”（而不是意义更明确的“foreach”）来引导这种一般被叫做“for-each循环”的循环，并使用“:”（而不是意义更明确的“in”）来分割循环变量名称和要被遍历的对象。这样作的主要原因，是为了避免因为引入新的关键字，造成兼容性方面的问题――在Java语言中，不允许把关键字当作变量名来使用，虽然使用“foreach”这名字的情况并不是非常多，但是“in”却是一个经常用来表示输入流的名字（例如java.lang.System类里，就有一个名字叫做“in”的static属性，表示“标准输入流”）。的确可以通过巧妙的设计语法，让关键字只在特定的上下文中有特殊的含义，来允许它们也作为普通的标识符来使用。不过这种会使语法变复杂的策略，并没有得到广泛的采用。“for-each循环”并不是一个最近才出现的控制结构。在1979正式发布的Bourne shell（第一个成熟的UNIX命令解释器）里就已经包含了这种控制结构（循环用“for”和“in”来引导，循环体则用“do”和“done”来标识）。防止在循环体里修改循环变量：在默认情况下，编译器是允许在第二种for循环的循环体里，对循环变量重新赋值的。不过，因为这种做法对循环体外面的情况丝毫没有影响，又容易造成理解代码时的困难，所以一般并不推荐使用。Java提供了一种机制，可以在编译期间就把这样的操作封杀。具体的方法，是在循环变量类型前面加上一个“final”修饰符。这样一来，在循环体里对循环变量进行赋值，就会导致一个编译错误。借助这一机制，就可以有效的杜绝有意或无意的进行“在循环体里修改循环变量”的操作了。这里需要我么注意的是：这只是禁止了对循环变量进行重新赋值。给循环变量的属性赋值，或者调用能让循环变量的内容变化的方法，是不被禁止的。
思路三：
  我们可以用python中的filter函数以及lambda函数过滤后，返回结果即可。具体我们用python实习如下：

class Solution:
	def __init__(self):
		self.s = ''
	def FirstAppearingOnce(self):
		res = list(filter(lambda x: self.s.count(x) == 1, self.s))
		return res[0] if res else '#'
	def Insert(self, char):
		self.s += char

代码效果图如图所示：

  为了让大家更好的理解改代码，首先给大家介绍python中的lambda函数。lambda是Python编程语言中使用频率较高的一个关键字。在Python中，lambda的语法是唯一的。其形式如下：

lambda argument_list: expression

  其中，lambda是Python预留的关键字，argument_list和expression由用户自定义。具体介绍如下。

1. 这里的argument_list是参数列表，它的结构与Python中函数(function)的参数列表是一样的。具体来说，argument_list可以有非常多的形式。(a,b,a=1,b=1……)
2. 这里的expression是一个关于参数的表达式。表达式中出现的参数需要在argument_list中有定义，并且表达式只能是单行的。(1,None, a + b, sum(a),……)
3. 这里的lambda argument_list: expression表示的是一个函数。这个函数叫做lambda函数。
   lambda函数有如下特性：
   ①、lambda函数是匿名的：所谓匿名函数，通俗地说就是没有名字的函数。lambda函数没有名字。
   ②、 lambda函数有输入和输出：输入是传入到参数列表argument_list的值，输出是根据表达式expression计算得到的值。
   ③、lambda函数一般功能简单：单行expression决定了lambda函数不可能完成复杂的逻辑，只能完成非常简单的功能。由于其实现的功能一目了然，甚至不需要专门的名字来说明。
   lambda函数的用法：
     由于lambda语法是固定的，其本质上只有一种用法，那就是定义一个lambda函数。在实际中，根据这个lambda函数应用场景的不同，可以将lambda函数的用法扩展为以下几种：
   1、将lambda函数赋值给一个变量，通过这个变量间接调用该lambda函数。
   2、将lambda函数赋值给其他函数，从而将其他函数用该lambda函数替换。
   3、将lambda函数作为其他函数的返回值，返回给调用者。
   4、将lambda函数作为参数传递给其他函数。
   思路四：
     我们可以考虑使用一个有序字典OrderedDict()来保存每个字符及其出现的次数，字典本质是一个哈希表，存取的时间复杂度都是O(1)。然后每次获取第一次出现一次的字符时，遍历有序字典，找到第一个次数为1词的字符。最后整体时间复杂度为O(N)。具体我们用python将其实现：

import collections
class Solution:
	def __init__(self):
		self.str = collections.OrderedDict()
	def FirstAppearingOnce(self):
		for c in self.str:
			if self.str[c] == 1:
				return c
		return '#'
	def Insert(self, char):
		if char in self.str:
			self.str[char] += 1
		else:
			self.str[char] = 1

代码效果图如图所示：

思路五：
  其实本思路和思路四差不多，直接利用collections中的Counter()函数进行解题。并且通过字典统计其次数返回次数为1的结果即可。具体用Python实现如下：

from collections import Counter
class Solution:
	def __init__(self):
		self.words = []
	def FirstAppearingOnce(self):
		remm = Counter(self.words)
		for char in self.words:
			if remm[char] == 1:
				return char
		return '#'
	def Insert(self, char):
		self.words.append(char)	

代码效果图如图所示：

总结

  本题是主要考察从字符串中找出第一个出现的字符。本文在做题之前，首先给大家介绍了字符流的相关知识，并且通过五种方法来实现这道题目。从刚开始的Map和Queue队列以及List容器的应用到利用python中的字典、counter函数以及lambda和filter函数的结合。并且给大家介绍了一些比较不常用以及容易混淆的知识，方便大家更好的理解本代码。因此，我们在做题的时候，应该多次尝试各种方法，扩展自己的思维，写出优质的代码。总之，我们要继续加油，争取早日找到工作，Good Luck！！！

参考文献

[1] 负雪明烛
[2] ForcedOverflow
[3] God_white
[4] NayelyAA
[5] 肖哥shelwin
[6] java for循环的几种写法
[7] 学习笔记之Java队列Queue中offer/add函数,poll/remove函数,peek/element函数的区别
[8] JAVA中字符流详解