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

import java.util.*;
import java.util.stream.IntStream;

/**
 * NC277 字符流中第一个不重复的字符
 * @author d3y1
 */
public class Solution {
    private HashSet<Character> appearSet = new HashSet<>();
    private HashSet<Character> firstSet = new HashSet<>();
    private HashMap<Character, Integer> map = new HashMap<>();
    private Queue<Character> queue = new LinkedList<>();

    private HashMap<Character, Integer> linkedMap = new LinkedHashMap<>();

    private StringBuilder seq = new StringBuilder();

    // ASCII码
    private int[] count = new int[128];

    // 字符首次出现的位置
    private int location = 0;
    private int[] array = IntStream.generate(() -> -1).limit(128).toArray();

    // 字符出现的位置
    int[] index = new int[128];
    // 用于标记字符流的位置
    int at = 0;


    /**
     * Insert: Insert one char from string stream
     * @param ch
     */
    public void Insert(char ch)
    {
        // Insert1(ch);
        // Insert2(ch);
        // Insert3(ch);
        // Insert4(ch);
        // Insert5(ch);
        // Insert6(ch);
        Insert7(ch);
    }

    /**
     * FirstAppearingOnce: return the first appearance once char in current string stream
     * @return
     */
    public char FirstAppearingOnce()
    {
        // return FirstAppearingOnce1();
        // return FirstAppearingOnce2();
        // return FirstAppearingOnce3();
        // return FirstAppearingOnce4();
        // return FirstAppearingOnce5();
        // return FirstAppearingOnce6();
        return FirstAppearingOnce7();
    }


    
    /**
     * Insert1: HashSet + HashMap + Queue
     * @param ch
     */
    private void Insert1(char ch){
        if(appearSet.contains(ch)){
            if(firstSet.contains(ch)){
                firstSet.remove(ch);
            }
        }else{
            appearSet.add(ch);
            firstSet.add(ch);
            queue.offer(ch);
        }

        map.put(ch, map.getOrDefault(ch, 0)+1);
    }

    /**
     * FirstAppearingOnce1: HashSet + HashMap + Queue
     * @return
     */
    private char FirstAppearingOnce1(){
        if(!firstSet.isEmpty()){
            while(!queue.isEmpty() && !firstSet.contains(queue.peek())){
                queue.poll();
            }
            if(!queue.isEmpty()){
                return queue.peek();
            }

        }

        return '#';
    }
    
    
    
    /**
     * Insert2: LinkedHashMap => 保证key的先后顺序
     * @param ch
     */
    private void Insert2(char ch){
        linkedMap.put(ch, linkedMap.getOrDefault(ch, 0)+1);
    }

    /**
     * FirstAppearingOnce2: LinkedHashMap => 保证key的先后顺序
     * @return
     */
    private char FirstAppearingOnce2(){
        for(Character ch: linkedMap.keySet()){
            if(linkedMap.get(ch) == 1){
                return ch;
            }
        }

        return '#';
    }


    
    /**
     * Insert3: HashMap + StringBuilder
     * @param ch
     */
    private void Insert3(char ch){
        seq.append(ch);
        map.put(ch, map.getOrDefault(ch, 0)+1);
    }

    /**
     * FirstAppearingOnce3: HashMap + StringBuilder
     * @return
     */
    private char FirstAppearingOnce3(){
        for(int i = 0; i < seq.length(); i++){
            if(map.get(seq.charAt(i)) == 1){
                return seq.charAt(i);
            }
        }

        return '#';
    }

    

    /**
     * Insert4: HashMap + Queue
     * @param ch
     */
    private void Insert4(char ch){
        if(!map.containsKey(ch)){
            queue.offer(ch);
        }

        map.put(ch, map.getOrDefault(ch, 0)+1);
    }

    /**
     * FirstAppearingOnce4: HashMap + Queue
     * @return
     */
    private char FirstAppearingOnce4(){
        while(!queue.isEmpty()){
            if(map.get(queue.peek()) == 1){
                return queue.peek();
            }else{
                queue.poll();
            }
        }

        return '#';
    }


    
    /**
     * Insert5: BitMap + Queue
     * @param ch
     */
    private void Insert5(char ch){
        if(count[ch]++ == 0){
            queue.offer(ch);
        }else{
            queue.remove(ch);
        }
    }

    /**
     * FirstAppearingOnce5: BitMap + Queue
     * @return
     */
    private char FirstAppearingOnce5(){
        if(queue.isEmpty()){
            return '#';
        }

        return queue.peek();
    }

    

    /**
     * Insert6: BitMap + location
     * @param ch
     */
    private void Insert6(char ch){
        // 首次出现
        if(array[ch] == -1){
            array[ch] = location++;
        }else{
            array[ch] = -2;
        }
    }

    /**
     * FirstAppearingOnce6: BitMap + location
     * @return
     */
    private char FirstAppearingOnce6(){
        int minIndex = Integer.MAX_VALUE;
        char ch = '#';
        for(int i = 0; i < 128; i++){
            if(array[i]>=0 && array[i]<minIndex){
                ch = (char) i;
                minIndex = array[i];
            }
        }

        return ch;
    }


    
    /**
     * Insert7: Double BitMap
     * @param ch
     */
    private void Insert7(char ch){
        count[ch]++;
        index[ch] = at++;
    }

    /**
     * FirstAppearingOnce7: Double BitMap
     * @return
     */
    private char FirstAppearingOnce7(){
        int minIndex = at;
        char ch = '#';
        for(int i = 0; i < 128; i++){
            if(count[i]==1 && index[i]<minIndex){
                ch = (char) i;
                minIndex = index[i];
            }
        }

        return ch;
    }
}