您的位置 首页 java

剑指Offer(五十四):字符流中第一个不重复的字符(Java版)

描述

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

数据范围:字符串长度满足 ,字符串中出现的字符一定在 ASCII 码内。进阶:空间复杂度 ,时间复杂度

后台会用以下方式调用 Insert 和 FirstAppearingOnce 函数

返回值描述:

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

示例1

输入:”google”

返回值:”ggg#ll”

示例2

输入:”abcdee”

返回值:”aaaaaa”

第一种方式

利用一个map来存储,字符作为key,出现次数作为value即可,每次取第一个value为1的key即可,代码如下

 Map<Character,Integer> map =  new LinkedHashMap<>();

public  void  firstInsert(char ch) {
    if(map.get(ch) != null){
        map.put(ch,2);
    }else{
        map.put(ch,1);
    }
}




public char firstFirstAppearingOnce() {
    if(null != map){
         Iterator <Character> iterator = map.keySet().iterator();
        while (iterator.hasNext()){
            Character next = iterator.next();
            if (map.get(next) == 1){
                return next;
            }
        }
    }
    return '#';
}  

第二种方式

不利用map,利用一个数组来标识每个字符,由于 ASCII 码一共128个,所以定义一个长度为128的数组即可,再定义一个队列(因为队列是先进先出),每次循环判断,如果发现当前出队列的值在数组中的值不是1,则直接抛弃,直到找到队列中第一个char,在数组中的值为1,代码如下

 int[] ints = new int[128];
Queue<Character> queue = new LinkedList<>();

public void secondInsert(char ch) {
    if(ints[ch]++ == 0){
        queue.add(ch);
    }
}


public char secondFirstAppearingOnce() {
    while (!queue.isEmpty()){
        Character peek = queue.peek();
        if(ints[peek] == 1){
            return peek;
        }else {
            queue.poll();
        }
    }
    return '#';
}  

文章来源:智云一二三科技

文章标题:剑指Offer(五十四):字符流中第一个不重复的字符(Java版)

文章地址:https://www.zhihuclub.com/184632.shtml

关于作者: 智云科技

热门文章

网站地图