欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-12 22:15:55
...

剑指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();
	}
}

代码效果图如图所示:
Day54:字符流中第一个不重复的字符
  在本代码中我们看到了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 '#';
	}
}

代码效果图如图所示:
Day54:字符流中第一个不重复的字符
  我们在代码中看到了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

代码效果图如图所示:
Day54:字符流中第一个不重复的字符
  为了让大家更好的理解改代码,首先给大家介绍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

代码效果图如图所示:
Day54:字符流中第一个不重复的字符
思路五:
  其实本思路和思路四差不多,直接利用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)	

代码效果图如图所示:
Day54:字符流中第一个不重复的字符

总结

  本题是主要考察从字符串中找出第一个出现的字符。本文在做题之前,首先给大家介绍了字符流的相关知识,并且通过五种方法来实现这道题目。从刚开始的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中字符流详解