[剑指offer] 字符流中第一个不重复的字符

题目描述

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

解题思路

用一个哈希表来存储每个字符及其出现的次数,另外用一个字符串 s 来保存字符流中字符的顺序。

  • 每次插入的时候,在字符串 s 中插入该字符,然后在哈希表中查看是否存在该字符,如果存在则它的 value 加1,如果不存在,它在哈希表中插入该字符,它的 value 为 1。
  • 查找第一个只出现一次的字符时,按照 s 的顺序,依次查找 map 中字符出现的次数,当 value 为 1 时,该字符就是第一个只出现一次的字符。

参考代码

import java.util.HashMap;
public class Solution {
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    StringBuffer s = new StringBuffer();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        s.append(ch);
        if(map.containsKey(ch)){
            map.put(ch, map.get(ch)+1);
        }else{
            map.put(ch, 1);
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for(int i = 0; i < s.length(); i++){
            if(map.get(s.charAt(i)) == 1)
                return s.charAt(i);
        }
        return '#';
    }
}

版权属于: 尾尾部落

原文地址: https://weiweiblog.cn/firstappearingonce/

转载时必须以链接形式注明原始出处及本声明。

window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"1","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏zhangdd.com

nginx location匹配规则

~      #波浪线表示执行一个正则匹配,区分大小写 ~*    #表示执行一个正则匹配,不区分大小写 ^~    #^~表示普通字符匹配,如果该选项匹配...

1114
来自专栏Java 源码分析

数据结构Queue

​ 栈和队列其实是相同的,只是名字不一样 入栈换成了入队(enqueue),出栈换成了出队(dequeue)。语义 是不同的。入队操作向队尾添加元素,而出...

2735
来自专栏数据结构与算法

8758:2的幂次方表示

8758:2的幂次方表示 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 任何一个正整数都可以用2的幂次方表示。例如:  ...

4076
来自专栏大眼瞪小眼

PHP HashTable总结

本篇文章主要是对 PHP HashTable 总结,下面的参考链接是很好的学习资料。学习“散列”这个数据结构—推荐《数据结构与算法分析 C语言描述》

1631
来自专栏专注 Java 基础分享

虚拟机字节码执行引擎

所谓的「虚拟机字节码执行引擎」其实就是 JVM 根据 Class 文件中给出的字节码指令,基于栈解释器的一种执行机制。通俗点来说,也就是 JVM 解析字节码指令...

2634
来自专栏运维小白

8.4 通配符

ls *.txt *表示通配,不分字符,也不分几个 [root@hf-01 ~]# ls 111 123 1_heard.txt 1_sorft.txt...

1857
来自专栏数据结构与算法

牛客提高R5 A.同余方程

设\(solve(x, y)\)表示\(i \in [0, x], j \in [0, y]\)满足题目要求的方案数

1121
来自专栏数据结构与算法

15:Challenge 11(主席树裸题)

总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列,有M次操作,每次操作是以下两种之一: (1)...

35413
来自专栏黑泽君的专栏

同步解决线程安全问题的三种实现

911
来自专栏郑科的专栏

PHP7 新特性简介(一)

PHP7是PHP编程语言全新的一个版本,在性能方面获得了极大的提升。官方的文档显示,PHP7可以达到PHP5.x版本两倍的性能。同时还提供了很多其他语言流行的语...

6580

扫码关注云+社区

领取腾讯云代金券