Question

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

思路：哈希和队列实现。

哈希记录次数，队列记录顺序。

import java.util.*;
public class Solution {
  Queue<Character> queue = new LinkedList<>();
  Map<Character, Integer> map = new HashMap<>();
  //Insert one char from stringstream
  public void Insert(char ch)
  {
    queue.add(ch);
    map.put(ch, map.getOrDefault(ch, 0)+1);
  }
  //return the first appearence once char in current stringstream
  public char FirstAppearingOnce()
  {
    while(queue.peek() != null){
      Character c = queue.peek();
      if(map.get(c) == 1) return c;
      //只有重复的才会出列，不重复会一直保存
      else queue.poll();
    }
    return '#';
  }
}