题解 | #字符流中第一个不重复的字符#

import java.util.*;
public class Solution {
    LinkedList<Character> list = new LinkedList();
    Map<Character, Integer> map = new HashMap();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        // hashmap key char value count
        // !contains hashmap的 linkedlist add
        //     hashmap put 1
        // else hashmap get v+1
        if(map.containsKey(ch)) {
            map.put(ch,map.get(ch)+1);
        } else {
            list.add(ch);
            map.put(ch, 1);
        }
    }

    public char FirstAppearingOnce()
    {
        System.out.println(list.toString());
        // while peek is > 1
        while(!list.isEmpty() && map.get(list.peek()) > 1) {
            list.pop();
        }
        if(list.isEmpty()) {
            return '#';
        } else {
            return list.peek();
        }
    }
}

HashMap+LinkedList

map保存char和重复次数

list保存不重复的候选数字，因为可能第一个会因为出现重复被干掉，那么要马上能拿到下一个不重复的数字，所以最好是用list保存着。 这个解法比用StringBuilder要好一些，list中会把重复的pop出去。下次就不会加进来，get时候也不需要遍历到这种了。