string caseout = "";1.读入测试用例字符串casein2.如果对应语言有Init()函数的话，执行Init() 函数3.循环遍历字符串里的每一个字符ch {Insert(ch);caseout += FirstAppearingOnce()}2. 输出caseout，进行比较。
如果当前字符流没有存在出现一次的字符，返回#字符。
"google"
"ggg#ll"
"abcdee"
"aaaaaa"
class Solution
{
public:
//Insert one char from stringstream
string s;
char hash[256]={0};
void Insert(char ch)
{
s+=ch;
hash[ch]++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
int size=s.size();
for(int i=0;i<size;++i)
{
if(hash[s[i]]==1)
return s[i];
}
return '#';
}
};
Solution: Java版的，使用一个HashMap来统计字符出现的次数，同时用一个ArrayList来记录输入流，每次返回第一个出现一次的字符都是在这个ArrayList（输入流）中的字符作为key去map中查找。
import java.util.*;
public class Solution {
HashMap<Character, Integer> map=new HashMap();
ArrayList<Character> list=new ArrayList<Character>();
//Insert one char from stringstream
public void Insert(char ch)
{
if(map.containsKey(ch)){
map.put(ch,map.get(ch)+1);
}else{
map.put(ch,1);
}
list.add(ch);
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{ char c='#';
for(char key : list){
if(map.get(key)==1){
c=key;
break;
}
}
return c;
}
}
public class Solution
{
int[] hashtable=new int[256];
StringBuffer s=new StringBuffer();
//Insert one char from stringstream
public void Insert(char ch)
{
s.append(ch);
if(hashtable[ch]==0)
hashtable[ch]=1;
else hashtable[ch]+=1;
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
char[] str=s.toString().toCharArray();
for(char c:str)
{
if(hashtable[c]==1)
return c;
}
return '#';
}
}
对这个题目思考，可以发现，出现的字符 和 它的出现的次数 是一种对应关系，自然联想到 哈希表的 key-value 这种对应，或者应用关联容器 map，可以很方便的解决这个问题。
class Solution
{
public:
//Insert one char from stringstream
void Insert(char ch)
{
vec.push_back(ch);
mapdata[ch]++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
vector<int>::iterator it;
for(it=vec.begin();it!=vec.end();it++)
{
if(mapdata[*it]==1)
return *it;
}
return '#';
}
map<char,int> mapdata;
vector<int> vec;
};
import java.util.LinkedHashMap;
import java.util.Map;
public class Solution {
private Map<Character, Integer> map = new LinkedHashMap<>();
//Insert one char from stringstream
public void Insert(char ch) {
if (map.containsKey(ch)) {
map.put(ch, map.get(ch) + 1);
} else {
map.put(ch, 0);
}
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce() {
for (Map.Entry<Character, Integer> set : map.entrySet()) {
if (set.getValue() == 0) {
return set.getKey();
}
}
return '#';
}
}
class Solution
{
int t, a[128];
public:
Solution(){
t = 0;
memset(a, 0, sizeof a);
}
//Insert one char from stringstream
void Insert(char ch){
if(a[ch]) a[ch] = -1;
else a[ch] = ++t;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce(){
char res = '#';
int mi = ~(1 << 31);
for(int i = 0; i < 128; ++i) if(a[i] > 0 && a[i] < mi) res = i, mi = a[i];
return res;
}
};
# -*- coding:utf-8 -*- ''' 题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。 例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。 当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。 ''' class Solution: def __init__(self): self.char_list = [-1 for i in range(256)] self.index = 0 # 记录当前字符的个数，可以理解为输入的字符串中的下标 ''' 解法：利用一个int型数组表示256个字符，这个数组初值置为-1. 每读出一个字符，将该字符的位置存入字符对应数组下标中。 若值为-1标识第一次读入，不为-1且>0表示不是第一次读入，将值改为-2. 之后在数组中找到>0的最小值，该数组下标对应的字符为所求。 在python中，ord(char)是得到char对应的ASCII码；chr(idx)是得到ASCII位idx的字符 ''' def FirstAppearingOnce(self): # write code here min_value = 500 min_idx = -1 for i in range(256): if self.char_list[i] > -1: if self.char_list[i] < min_value: min_value = self.char_list[i] min_idx = i if min_idx > -1: return chr(min_idx) else: return '#' def Insert(self, char): # 如果是第一出现，则将对应元素的值改为下边 if self.char_list[ord(char)] == -1: self.char_list[ord(char)] = self.index # 如果已经出现过两次了，则不修改 elif self.char_list[ord(char)] == -2: pass # 如果出现过一次，则进行修改，修改为-2 else: self.char_list[ord(char)] = -2 self.index += 1
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
常规的解法是用一个map来存储，这样空间复杂度为O(n)，然后每次都遍历map获取第一个不重复的字符，时间复杂度也为O(n)。下面显示i代码：
import java.util.Map;
import java.util.LinkedHashMap;
public class Solution {
//用有序的Map：LinkedHashMap来存放char，并且记录其出现次数
Map<Character,Integer> map = new LinkedHashMap<Character,Integer>();
//Insert one char from stringstream
public void Insert(char ch)
{
if(!map.containsKey(ch)){
map.put(ch,1);
}else{
map.put(ch,map.get(ch)+1);
}
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
for(char ch:map.keySet()){
int count = map.get(ch);
//目前第一个只出现一次的字符，返回
if(count == 1)
return ch;
}
return '#';
}
}这种很容易想到，但是能不能再优化一点呢？我们知道，ASCII码一共只有128个字符，那么我可以直接定义一个长度为128的数组，空间复杂度为O(n)，时间复杂度控制在常数级别，虽然我获取第一个只出现一次的元素需要一个while循环，但是这个循环不可能超过128，一般很快就可以拿到。
import java.util.LinkedList;
public class Solution {
//英文字符不会逃出128个ascii码的范围，所以定义这个长度的数组
//第一个ASCII码是一个空字符，所以我都是相对于` `进行一一排列
//比如数字'0'是30，那'0'-''等于30，就存在tmp[30]这个地方即可
//注意，tmp存的是出现的子树，即'0'出现了两次，那么tmp[30]就是2
int[] tmp = new int[128];
//维护一个队列，只保存一次进来的元素，重复的丢掉
LinkedList<Character> queue = new LinkedList<>();
//Insert one char from stringstream
public void Insert(char ch)
{
//第一次进来的元素放进队列尾部
if(tmp[ch-' '] == 0){
queue.add(ch);
}
//进来一次，就对相应坐标加一，统计出出现次数
tmp[ch-' ']++;
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
//取得时候是从队列得头部取，因为头部是比较早的数据
//出现次数大于等于2的话就不断丢弃，知道找到第一个出现次数为1的字符跳出循环
while(!queue.isEmpty() && tmp[queue.getFirst()-' ']>=2){
queue.removeFirst();
}
//拿到这个第一个只出现一次的字符
if(!queue.isEmpty()){
return queue.getFirst();
}
//拿不到了，说明没有只出现一次的字符，那么就返回#
return '#';
}
}
//用哈希表
class Solution
{
public:
//Insert one char from stringstream
void Insert(char ch)
{
s+=ch;
tab[ch]++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
for(int i=0;i<s.size();i++){
if(tab[s[i]]==1)
return s[i];
}
return '#';
}
private:
string s;
map<char,int> tab;
};
class Solution:
def __init__(self):
self.s = ''
self.queue = [] #这里只是保存出现奇数次的字符
def FirstAppearingOnce(self):
if self.queue:
return self.queue[0]
return '#'
def Insert(self, char):
self.s += char
if char in self.queue:
self.queue.pop(self.queue.index(char))
else:
self.queue.append(char) 举例‘ggg’，上面输出为：‘g#g’，而按照题意答案应该为：‘g##’
class Solution:
def __init__(self):
self.s = ''
self.queue = [] #按顺序保存所有只出现一次的字符
self.second = [] #按顺序保存所有出现过的字符
def FirstAppearingOnce(self):
if self.queue:
return self.queue[0]
return '#'
def Insert(self, char):
self.s += char
if char in self.queue:
self.queue.pop(self.queue.index(char))
elif char not in self.second:
self.queue.append(char)
self.second.append(char) 
public class Solution {
//Insert one char from stringstream
int[] hashtable = new int[256];
StringBuilder sc = new StringBuilder();
public void Insert(char ch)
{
sc.append(ch);
if(hashtable[ch] == 0){
hashtable[ch] = 1;
}
else{
hashtable[ch] += 1;
}
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
char[] str = sc.toString().toCharArray();
for(char s : str){
if(hashtable[s] == 1){
return s;
}
}
return '#';
}
}
大神的思路就是不一样
class Solution
{
public:
string s;
char hash[256] = {0};
//Insert one char from stringstream
void Insert(char ch)
{
s += ch;
hash[ch]++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
int size = s.size();
for(int i = 0; i < size; i++){
if(hash[s[i]] == 1)
return s[i];
}
return '#';
}
};
import java.util.*;
public class Solution {
private Map<Character, Integer> m = new LinkedHashMap<Character, Integer>();
public void Insert(char ch) {
if(!m.containsKey(ch)) {
m.put(ch, 1);
} else {
m.put(ch, m.get(ch)+1);
}
}
public char FirstAppearingOnce() {
for(Character c : m.keySet()) {
if(m.get(c) == 1) return c;
}
return '#';
}
}
import java.util.LinkedHashMap;
import java.util.Map;
public class Solution {
Map<Character, Integer> map = new LinkedHashMap<>();
//Insert one char from stringstream
public void Insert(char ch)
{
if(map.containsKey(ch))
map.put(ch, map.get(ch)+1);
else map.put(ch, 1);
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
for(Map.Entry<Character, Integer> en : map.entrySet())
{
if(en.getValue() == 1) return en.getKey();
}
return '#';
}
}
c++ map+单指针， Insert 时间复杂度O(n)，FirstAppearingOnce时间复杂度O(1)，空间复杂度O(n)
思路: map存储每个字符出现次数，指针p指向第一个未重复的字符(初始化0)。每次调用Insert的时候，检查指针p对应的字符出现次数是否>1，如果是p=p+1，不断此过程，直到p对应的字符出现次数<=1。调用FirstAppearingOnce判断p是否等于当前字符长度，如果是，返回'#'，否则返回p对应的字符。
直接看代码吧：
class Solution
{
public:
Solution()
{
mp = new int[256]{0};
p = 0;
}
//Insert one char from stringstream
void Insert(char ch)
{
mp[ch]++;
ss.push_back(ch);
while(mp[ss[p]] > 1)
p++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
if(p == ss.size())
return '#';
return ss[p];
}
private:
string ss;
int *mp;
int p;
}; 
class Solution
{
public:
//Insert one char from stringstream
void Insert(char ch)
{
str += ch;
cnt[ch].push_back(index);
index++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
if(cnt.size() == 0) return '#';
int idx = INT_MAX;
for(auto w : cnt){
if(w.second.size() == 1){
idx = min(idx, w.second[0]);
}
}
return (idx == INT_MAX ? '#' : str[idx]);
}
private:
unordered_map<char, vector<int>> cnt;
int index = 0;
string str;
}; 
class Solution
{
public:
//Insert one char from stringstream
string s;
void Insert(char ch)
{
s.push_back(ch); //输入字符到字符串s中
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
int hash[256]={0}; //初始化所有的字符出现的次数为0
int length=s.length();
for(int i=0;i<length;i++) //遍历字符串s，出现一次对应hash累加一次
{
hash[s[i]]++;
}
for(int i=0;i<length;i++)
{
if(hash[s[i]]==1) //找到第一个出现次数为1的字符，返回结束
return s[i];
}
return '#'; //若遍历完未找到，则返回字符'#'。
}
}; 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
//Insert one char from stringstream
private int[] occurence = new int[256];
private int index;
public Solution(){
for(int i=0;i<256;i++){
occurence[i] = -1;
}
index = 0;
}
void Insert(char ch)
{
if(occurence[ch] == -1)
occurence[ch] = index;
else if(occurence[ch] >= 0)
occurence[ch] = -2;
index++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
char ch = '\0';
int minIndex = Integer.MAX_VALUE;
for(int i=0;i<256;i++){
if(occurence[i] >=0 && occurence[i]<minIndex){
ch = (char)i;
minIndex = occurence[i];
}
}
if(ch == '\0')
return '#';
return ch;
}
}