当前位置:首页 > 服务端 > 《剑指offer》第五十题(字符流中第一个只出现一次的字符)

《剑指offer》第五十题(字符流中第一个只出现一次的字符)

2022年11月06日 19:50:23服务端12
// 面试题50(二):字符流中第一个只出现一次的字符
// 题目:请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从
// 字符流中只读出前两个字符"go"时,第一个只出现一次的字符是'g'。当从该字
// 符流中读出前六个字符"google"时,第一个只出现一次的字符是'l'。

#include <iostream>
#include <limits>

using namespace std;

class CharStatistics
{
public:
    CharStatistics() : index(0)//后初始化index=0
    {
        for (int i = 0; i < 256; ++i)
            occurrence[i] = -1;
    }

    void Insert(char ch)
    {
        if (occurrence[ch] == -1)//之前没有过,插入index
            occurrence[ch] = index;
        else if (occurrence[ch] >= 0)//之前出现过,设为-2
            occurrence[ch] = -2;

        index++;//用来指示出现过一次的字符的顺序
    }

    char FirstAppearingOnce()
    {
        char ch = '\0';
        int minIndex = numeric_limits<int>::max();//类型int的最大值
        for (int i = 0; i < 256; ++i)
        {
            if (occurrence[i] >= 0 && occurrence[i] < minIndex)//对只出现一次的字符进行搜索,找到最先出现的那个值
            {
                ch = (char)i;
                minIndex = occurrence[i];
            }
        }

        return ch;
    }

private:
    // occurrence[i]: A character with ASCII value i;
    // occurrence[i] = -1: The character has not found;
    // occurrence[i] = -2: The character has been found for mutlple times
    // occurrence[i] >= 0: The character has been found only once
    int occurrence[256];
    int index;
};

// ====================测试代码====================
void Test(const char* testName, CharStatistics chars, char expected)
{
    if (testName != nullptr)
        printf("%s begins: ", testName);

    if (chars.FirstAppearingOnce() == expected)
        printf("Passed.\n");
    else
        printf("FAILED.\n");
}

int main()
{
    CharStatistics chars;

    Test("Test1", chars, '\0');

    chars.Insert('g');
    Test("Test2", chars, 'g');

    chars.Insert('o');
    Test("Test3", chars, 'g');

    chars.Insert('o');
    Test("Test4", chars, 'g');

    chars.Insert('g');
    Test("Test5", chars, '\0');

    chars.Insert('l');
    Test("Test6", chars, 'l');

    chars.Insert('e');
    Test("Test7", chars, 'l');
    system("pause");
    return 0;
}

 

作者:深夜十二点三十三
来源链接:https://www.cnblogs.com/CJT-blog/p/10527180.html

版权声明:
1、JavaClub(https://www.javaclub.cn)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。


本文链接:https://www.javaclub.cn/server/68216.html

标签: 面试
分享给朋友:

“《剑指offer》第五十题(字符流中第一个只出现一次的字符)” 的相关文章

面试题:SpringBoot 自动装配原理

1. @SpringBootApplication注解 首先,我们都知道SpringBoot程序的入口是通过@SpringBootApplication注解修饰的一个类,例如: @SpringBootApplication public cl...

20200103面试知识点整理

涉及到的知识 优先级从高到底Java基础线程数据库框架微服务(boot+cloud)缓存(redis)linux(比如说线上日志查找报错) 相应的知识点网站 https://github.com/Cyc2018/CS-Notes...

Golang面试题

目录 Golang面试题 1. defer的执行顺序 for循环时使用指针赋值为副本形式 go执行的随机性和闭包的局部变量 go的组合继承实现OOP的继承 5. se...

2019年Java后端工程师常见面试题和感想

来新公司有5个月了,从第二个月开始就参与公司后端工程师的面试工作了,包括校招在内,面试超过100个(包括40个校招的终面)应聘者了,应聘者中有超过10年的技术经理,有6年以上的高级开发,有3到5年的中级开发,有刚毕业的初级开发,当然还有未毕业的硕士生本科生,有入职公司的,也有外包公司来...

经典java面试题(详细)

经典java面试题(详细)

经典Java面试题收集(一) 转载于:https://www.jianshu.com/p/c01eb6e46226 categories: Interviewdescription: 本文收集了一些经典的Java面试题...

Java面试题_第三阶段(Spring、MVC、IOC、AOP、DI、MyBatis、SSM、struts2)

Java面试题_第三阶段(Spring、MVC、IOC、AOP、DI、MyBatis、SSM、struts2)

1.1 何为Spring Bean容器?Spring Bean容器与Spring IOC 容器有什么不同吗? 答:1)用于创建bean对象,管理bean对象的那个容器。 2)Spring IOC 容器本质上指的的就是Spring Bean容器,Spring Bea...

python面试题 1w道

python面试题 1w道

第一章 python基础   1、下面这段代码的输出结果是什么?请解释。 def extendList(val, list=[]): list.append(val) return list...

5道必问的Python爬虫面试题及答案

5道必问的Python爬虫面试题及答案

爬虫是Python的重要应用方向之一,也是学习Python的学员求职的主要方向。为了帮助学员更快更好的通过企业面试,我悉心整理了5道Python爬虫面试题及答案,希望能够给大家提供帮助! 1、简要介绍下scrapy框架及其优势 scrapy是...

Java面试题_第四阶段

Java面试题_第四阶段

1.1 电商行业特点 1.分布式   垂直拆分:根据功能模块进行拆分   水平拆分:根据业务层级进行拆分 2.高并发      用户单位时间内访问服务器数量,是电商行业中面临的主要问题 3....

Java 分布式框架面试题合集

Java 分布式框架面试题合集

Java 分布式框架面试题合集 1.什么是 ZooKeeper? 答:ZooKeeper 是一个开源的分布式应用程序协调服务,是一个典型的分布式数据一致性解决方案。设计目的是将那些复杂且容易出错的分布式一致性服务封装起来,构成一个高效可靠的系统,并以一系列简单易用的原子操作...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。