本文共 1055 字,大约阅读时间需要 3 分钟。
题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时,第一个只出现一次的字符是"l"。time and time again, i ask myself,问自己,为什么这么傻x,这么傻逼~
简单思路: map记录字符出现次数;数组记录insert的字符;每次遍历字符数组,结合map,看是否出现1次; 让我们问问神奇海螺吧后的神奇思路: 用一个数组,记录每个元素的出现次数;一个队列,将字符第一次出现的时候,加入队列; 取第一个出现次数为1的字符:找队首元素,判断其出现次数是否为1,如果是,则返回;如果不是,出队,判断下一个。 注意点: 字符,拥有其对应的整数,我想说的是,字符A,对应ascii中的65,字符a,对应97。import java.util.LinkedList;public class Solution { // 来自讨论区 int[] count = new int[128]; // 只有128个字符么 嗯。 LinkedListqueue = new LinkedList (); //Insert one char from stringstream public void Insert(char ch) { count[ch]++; if(count[ch] == 1){ queue.offer(ch); } } //return the first appearence once char in current stringstream public char FirstAppearingOnce() { while(!queue.isEmpty()){ char cur = queue.peek(); if(count[cur] == 1){ return cur; } queue.pop(); } return '#'; }}
转载地址:http://ogwji.baihongyu.com/