剑指offer(C++)-JZ50:第一个只出现一次的字符(算法-其他)

简介: 剑指offer(C++)-JZ50:第一个只出现一次的字符(算法-其他)

题目描述:

在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).(从0开始计数)

数据范围:0≤n≤10000,且字符串只有字母组成。

要求:空间复杂度O(n),时间复杂度O(n)

示例:

输入:

"google"


返回值:

4

解题思路:

本题考察算法思维。两种解题思路:


1)哈希法


  1. 第一次循环用哈希表记录所有字符出现次数。
  2. 第二次循环找到首个出现次数为1的字符即可。

2)位运算


  1. 本质上和哈希法一样。因为字符只有字母,数量为26*2=52。每一位表示一个字符,比如字符b就是0010。
  2. 第一次循环用b记录出现过的字符,相应位数设为1,如果出现过了则flag对应位数也设为1。
  3. 第二次循环如果某个字符在b中对应位数为1,在flag中为0,则说明只出现过一次,完毕。

3)队列哈希法


  1. 该方法执行一次循环即可。
  2. 当字符首次出现,哈希表存储该字符位置,并将其放入队列中。
  3. 如果出现重复字符,则哈希表将该字符位置信息设为-1,即无效,并依次弹出队列中位置为-1的数据。注意,如果重复字符并非首个字符,则不进行弹出操作。如abcb,则不弹;如abcba,则将队列abc中的ab弹出,只剩下的c也就是答案。

测试代码:

1)哈希法

class Solution {
public:
    // 首个不重复字符
    int FirstNotRepeatingChar(string str) {
        int size = int(str.size());
        unordered_map<char, int> mp;
        // 统计每个字符出现的次数
        for(int i = 0; i < size; i++){
            mp[str[i]]++;
        }  
        // 找到第一个只出现一次的字母
        for(int i = 0; i < size; i++){
            if(mp[str[i]] == 1)
                return i;
        }  
        // 没有找到
        return -1;
    }
};

2)位运算

class Solution {
public:
    // 首个不重复字符
    int FirstNotRepeatingChar(string str) {
        int size = int(str.size());
        long long b = 0;
        long long flag = 0;
        // 统计每个字符出现的次数
        for(int i = 0; i < size; i++){
            int temp = str[i] - 'a';
            if(b & (1 << temp)){
                flag |= (1 << temp);
            }
            b |= (1 << temp);
        }  
        // 找到第一个只出现一次的字母
        for(int i = 0; i < size; i++){
            int temp = str[i] - 'a';
            if((b & (1 << temp)) && !(flag & (1 << temp))){
                return i;
            }
        }  
        //没有找到
        return -1;
    }
};

3)队列哈希法

class Solution {
public:
    // 首个不重复字符
    int FirstNotRepeatingChar(string str) {
        int size = int(str.size());
        unordered_map<char, int> mp;
        queue<pair<char, int> > q;
        // 统计字符出现的位置
        for(int i = 0; i < size; i++){
            // 没有出现过的字符
            if(!mp.count(str[i])){
                mp[str[i]] = i;
                q.push(make_pair(str[i], i));
            // 找到重复的字符
            }
            else{
                // 位置置为-1
                mp[str[i]] = -1;
                // 弹出前面所有的重复过的字符
                while(!q.empty() && mp[q.front().first] == -1)
                    q.pop();
            }
        }
        return q.empty() ? -1 : q.front().second;
    }
};


相关文章
|
5月前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
71 0
|
13天前
|
存储 监控 算法
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
37 15
|
13天前
|
算法 Serverless 数据处理
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
41 12
|
4天前
|
存储 监控 算法
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
12 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
|
2月前
|
负载均衡 算法 安全
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
65 19
|
2月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
55 2
|
3月前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
2月前
|
存储 算法 安全
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
|
3月前
|
算法 安全 C++
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
67 4
|
6月前
|
存储 算法 安全
超级好用的C++实用库之sha256算法
超级好用的C++实用库之sha256算法
217 1