进阶:空间复杂度 ,时间复杂度
string caseout = "";1.读入测试用例字符串casein2.如果对应语言有Init()函数的话,执行Init() 函数3.循环遍历字符串里的每一个字符ch {Insert(ch);caseout += FirstAppearingOnce()}2. 输出caseout,进行比较。
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 '#'; //若遍历完未找到,则返回字符'#'。 } };
//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;
}
}