文档章节

第一个只出现一次的字符

G
 Garphy
发布于 09/15 15:17
字数 807
阅读 14
收藏 0

 处理字符串中重复或者次数出现等问题,最常用的就是哈希表,用字符串中的字符作为key,字符出现次数作为value,假定只有ASCII码范围内的字符,则可以开辟一个256大小的int数组,将每个字符(key)映射到该数组的对应位置上,计算每次出现的次数即可,遍历一次字符串,计算每个字符出现的次数,保存在int数组的对应位置上,第二次遍历字符串,若第一次出现某个字符对对应到的哈希表的对应位置处的元素为1,则该字符便是第一个只出现一次的字符,如果我们是遍历哈希表(int数组),则找到的哈希表中的第一个元素为1的位置对应的字符为字符串中第一个最小的只出现一次的字符。时间复杂度为O(n),需要额外的256个int空间来辅助,可以看做空间复杂度为O(1)。

    另外,如果要省空间,我们可以bitmap算法,用两个位来表示对应字符出现的次数,出现0次,则为00,出现一次则为01,出现2次及以上,都维持在10即可。

    另外,有一点需要注意,char的范围在-128-127,unsigned char的范围才是在0-255,因此ASCII值在128-255之间的字符,如果保存为了char型,其转化为int值的范围是在-128--1之间,这点在下面的代码中有体现。

import java.util.LinkedList;
public class Solution {
    //英文字符不会逃出128个ascii码的范围,所以定义这个长度的数组
    //第一个ASCII码是一个空字符,所以我都是相对于` `进行一一排列
    //比如数字'0'是30,那'0'-''等于30,就存在tmp[30]这个地方即可
    //注意,tmp存的是出现的子树,即'0'出现了两次,那么tmp[30]就是2
    int[] tmp = new int[128];
    //维护一个队列,只保存一次进来的元素,重复的丢掉
    LinkedList<Character> queue = new LinkedList<>();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        //第一次进来的元素放进队列尾部
        if(tmp[ch-' '] == 0){
            queue.add(ch);
        }
        //进来一次,就对相应坐标加一,统计出出现次数
        tmp[ch-' ']++;
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        //取得时候是从队列得头部取,因为头部是比较早的数据
        //出现次数大于等于2的话就不断丢弃,知道找到第一个出现次数为1的字符跳出循环
        while(!queue.isEmpty() && tmp[queue.getFirst()-' ']>=2){
            queue.removeFirst();
        }
 
        //拿到这个第一个只出现一次的字符
        if(!queue.isEmpty()){
            return queue.getFirst();
        }
 
        //拿不到了,说明没有只出现一次的字符,那么就返回#
        return '#';
    }
}

 

© 著作权归作者所有

G
粉丝 0
博文 168
码字总数 75197
作品 0
私信 提问
[剑指offer] 字符流中第一个不重复的字符

本文首发于我的个人博客:尾尾部落 题目描述 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符...

繁著
2018/07/29
0
0
剑指offer总结一:字符、数字重复问题

问题1:字符串中第一个不重复的字符 题目描述 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符...

huanglf714
08/22
0
0
剑指offer 54. 字符流中第一个不重复的字符

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

dby_freedom
2018/11/25
0
0
1 查找字符串中第一个只出现一次的字符

/ 找出一个字符串中第一个只出现一次的字符。 思路: 假设字符是ASCII字符,占一个字节,则最多为256个字符,用一个标记数组book[256]来记录每个字符出现的次数,最后遍历这个标记数组,找到...

秦时小
2016/10/11
34
0
经典算法学习——第一个只出现一次的字符

这同样是剑指Offer中的很经典的一道面试题。题目描述为:在字符串中找出第一个只出现一次的字符。如输入“abaccdeff”,则输出'b'. 一开始大家就会想到最简单的方法就是每访问到一个字符的时...

chenyufeng1991
2016/08/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【jQuery基础学习】05 jQuery与Ajax以及序列化

本文转载于:专业的前端网站➭【jQuery基础学习】05 jQuery与Ajax以及序列化 好吧,这章不像上章那么水了,总是炒剩饭也不好。 关于AJAX 所谓Ajax,全名Asynchronous JavaScript and XML。(也...

前端老手
30分钟前
10
0
CVE-2019-14287(Linux sudo 漏洞)分析

作者:lu4nx@知道创宇404积极防御实验室 作者博客:《CVE-2019-14287(Linux sudo 漏洞)分析》 原文链接:https://paper.seebug.org/1057/ 近日 sudo 被爆光一个漏洞,非授权的特权用户可以...

极客君
30分钟前
7
0
关于分布式,你需要知道的真相

目录 一、分布式锁 数据库的唯一索引 Redis 的 SETNX 指令 Redis 的 RedLock 算法 Zookeeper 的有序节点 二、分布式事务 2PC 本地消息表 三、CAP 一致性 可用性 分区容忍性 权衡 四、BASE 基...

李红欧巴
30分钟前
8
0
读书笔记:深入理解ES6 (附录B)

附录B:了解ES7(2016)   ES6经历了4年的发展,之后TC-39决定将发布周期转换为每年一版,以确保新语言特性能够更快地发展。   ES6中添加了三个语法特性,下面一一来讲。 第1节 指数运算...

张森ZS
36分钟前
14
0
计算机公开课推荐 2019.8

欢迎任何人参与和完善:一个人可以走的很快,但是一群人却可以走的更远。 ApacheCN 面试求职交流群 724187166 ApacheCN 学习资源 编程 哈佛 CS50:计算机科学导论 视频 MIT 6.00.1x:计算机科...

ApacheCN_飞龙
37分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部