剑指Offer-字符流中第一个不重复的字符

系统管理员 2022-04-24 13:10 165阅读 0赞

## 题目描述 ##

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

###### 输出描述: ######

> 如果当前字符流没有存在出现一次的字符，返回\#字符。

解题思路—**LinkedHashMap**：判断有没有出现重复，HashMap是一个很好的工具。但是本题有**顺序要求**，所以可以**使用LinkedHashMap**，顺序遍历输出第一个只出现一次的字符。  
解题思路—**简易哈希表**：本题还可以**使用数组实现简易的哈希表**。ASCII 码一共规定了128个字符的编码，所以数组大小可以设置为128，检测输入的字符，其ascii码对应的数组位+1，最后遍历字符串，判断数组值即可。**缺点：字符串中不能出现非 ASCII 编码的中文字符等**。

## Java解题—LinkedHashMap ##

import java.util.LinkedHashMap;
    import java.util.Map;
    public class Solution {
        public LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
        //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(Map.Entry<Character, Integer> entry: map.entrySet()){
                if(entry.getValue()==1)
                    return entry.getKey();
            }
            return '#';
        }
    }

## Java解题—简易哈希表 ##

public class Solution {
        public int[] hash = new int[128];
        public StringBuilder str = new StringBuilder();
        //Insert one char from stringstream
        public void Insert(char ch)
        {
            str.append(ch);
            hash[ch] += 1;
        }
        //return the first appearence once char in current stringstream
        public char FirstAppearingOnce()
        {
            char[] chars = str.toString().toCharArray();
            for(char ch:chars)
                if(hash[ch]==1)
                    return ch;
            return '#';
        }
    }