[LeetCode][LCR169]招式拆解 II——巧妙利用字母的固定顺序实现查找复杂度为O(1)的哈希表

news/2024/5/25 10:28:49/文章来源:https://blog.csdn.net/Beihai_Van/article/details/136682324

题目

LCR 169. 招式拆解 II

某套连招动作记作仅由小写字母组成的序列 arr,其中 arr[i] 第 i 个招式的名字。请返回第一个只出现一次的招式名称,如不存在请返回空格。

  • 示例 1:

输入:arr = "abbccdeff"
输出:a

  • 示例 2:

输入:arr = "ccdd"
输出:' '

  • 限制:
    0 <= arr.length <= 50000

思考

  1. 这道题本身并不难,只需要遍历给出的数据,将所有字母出现次数记录下来
  2. 如果是按出现顺序记录的,那么遍历哈希表,直接返回第一个只出现一次的字母即可
  3. 如果是记录时是无序的,那么再次遍历 arr 即可
  4. 由于 c++ 没有按插入顺序存储的哈希表的数据结构类型,故使用 unorder_map+vector 记录字母出现的顺序
  5. 为什么使用 unorder_map 呢?unordered_map 基于哈希表实现,插入和查找元素的平均时间复杂度为 O(1),但最坏情况下的时间复杂度为 O(n);而 std::map 是基于红黑树实现的关联容器,用于存储键-值对,并根据键进行排序和查找。对于 std::map ,查找特定键的元素的时间复杂度是 O(log n),其中n是map中元素的数量。插入键值对的时间复杂度也是 O(log n)。而本题中键本身的顺序并无作用,故只使用平均时间复杂度较小的 unorder_map
  6. 使用哈希表的这两种解法大同小异,并没有什么本质上的差别。但是我们注意到题目中规定只有小写字母,由于小写字母是连续出现的,且个数少而确定,那么我们可以开辟一个含26个元素的数组充当哈希表,从而达到 100% 的时间复杂度为 O(1) 的查找、插入操作,且避免了由哈希表映射操作等带来的额外的时间复杂度
    两种不同方式的比较

解法1:unorder_map 哈希表

class Solution {
public:char dismantlingAction(string arr) {unordered_map<char, bool> hmap;for(char c : arr)hmap[c] = hmap.find(c) == hmap.end();for(char c : arr)if(hmap[c]) return c;return ' ';}
};

解法2:利用数组模拟哈希表

class Solution {
public:char dismantlingAction(string arr) {vector<int> v(26, 0);//大小26个元素,初始化为0for(auto &ele:arr) v[ele-'a']++;for(auto &ele:arr) if(v[ele-'a']==1) return ele;return ' ';}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1006064.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

php 对接Bigo海外广告平台收益接口Reporting API

今天对接的是Bigo广告reporting api接口&#xff0c;拉取广告收益回来自己做统计。记录分享给大家 首先是文档地址,进入到BIGO后台就能看到文档地址以及参数&#xff1a; 文档地址&#xff1a;https://www.bigossp.com/guide/sdk/reportingApi/doc?type1 接入这些第三方广告…

模拟电子技术实验(三)

单选题 1.本实验的实验目的中&#xff0c;输出电阻测量是第几个目的&#xff1f; A. 1个。 B. 2个。 C. 3个。 D. 4个。 答案&#xff1a;C 评语&#xff1a;10分 单选题 2. 有一定输出功率的放大器的 “功率”下面理解正确的是&#xff1f; A. 能…

程序员的三重境界:码农,高级码农、程序员!

见字如面&#xff0c;我是军哥&#xff01; 掐指一算&#xff0c;我在 IT 行业摸爬滚打 19 年了&#xff0c;见过的程序员至少大好几千&#xff0c;然后真正能称上程序员不到 10% &#xff0c;绝大部分都是高级码农而已。 今天和你聊聊程序员的三个境界的差异&#xff0c;文章不…

CSS中position的属性有哪些,区别是什么

position有以下属性值&#xff1a; 属性值概述absolute生成绝对定位的元素&#xff0c;相对于static定位以外的一个父元素进行定位。元素的位置通过left、top、right、bottom属性进行规定。relative生成相对定位的元素&#xff0c;相对于其原来的位置进行定位。元素的位置通过…

江科大stm32学习笔记——【6-1】TIM定时中断

一.定时器 1.类型 STM32F103C8T6定时器资源&#xff1a;TIM1,TIM2,TIM3,TIM4 我们这次用通用定时器 2.基本定时器 预分频器对来自RCC_TIMxCLK的72MHz进行预分频&#xff0c;比如写0就是不分频或1分频&#xff0c;输出频率输入频率72MHz。写1就是2分频&#xff0c;输出频率输…

JAVA初阶数据结构栈(工程文件后续会上传)(+专栏数据结构练习是完整版)

1.栈的概念讲解(Stack)&#xff09; 定义&#xff1a;栈是一种先进后出的数据结构 要想拿到12就要把它头上的所有东西给移出去 2.栈的实现&#xff08;代码&#xff09; 2.1栈的方法逻辑的讲解 &#xff08;1&#xff09;新建一个测试类Frank &#xff08;2&#xff09;进…

数据结构 day2

1:思维导图 2&#xff1a;计算结构体大小 3&#xff1a;大小端存储 &#xff08;1&#xff09;&#xff1a;数据溢出 1 #include <stdio.h>2 #include <string.h>3 #include <stdlib.h>4 int main(int argc, const char *argv[])5 {6 short a 0x1234;…

LDA主题模型学习笔记

&#xff08;1&#xff09;LDA的基本介绍&#xff08;wiki&#xff09; LDA是一种典型的词袋模型&#xff0c;即它认为一篇文档是由一组词构成的一个集合&#xff0c;词与词之间没有顺序以及先后的关系。一篇文档可以包含多个主题&#xff0c;文档中每一个词都由其中的一个主题…

ES6字符扩展

反撇号模板字符 在ES6之前我们给变量赋值多行字符串时,常用的方法是加入转义字符处理换行问题. 反撇号很好的解决了这个问题 let str hello,Ecascript; console.log(str); 模板子有个特点定义在反撇号中的字符串,其中的空格\缩进\换行都会被保留. 在之前我们拼接想到的都是…

WPF RichTextBox 使用Paragraph显示富文本(角标小数字)

最近项目中需要展示和编辑角标小数字&#xff0c;研究下了&#xff0c;可以RichTextBox 的Paragraph实现。 定义组件RichTextBox&#xff0c;添加右上角右下角小数字&#xff1a; <RichTextBox Margin"10" Height"40" Name"richTextBox">…

目标跟踪SORT算法原理浅析

SORT算法 Simple Online and Realtime Tracking(SORT)是一个非常简单、有效、实用的多目标跟踪算法。在SORT中&#xff0c;仅仅通过IOU来进行匹配虽然速度非常快&#xff0c;但是ID switch依然非常严重。 SORT最大特点是基于Faster RCNN的目标检测方法&#xff0c;并利用卡尔…

2024 年 2 月公链行业研报

作者&#xff1a;stellafootprint.network 数据来源&#xff1a;Footprint Analytics 公链研究页面 二月份&#xff0c;加密货币市场展现出强劲的上涨势头&#xff0c;这主要得益于比特币和以太坊的价值大幅上涨超过 45%。这一乐观态势也影响到其他代币&#xff0c;前十大代币…

【Ubuntu-20.04】OpenCV-3.4.16的安装并对图片与视频处理

【Ubuntu-20.04】OpenCV-3.4.16的安装并对图片与视频处理 一、安装OpenCV-3.4.161.下载OpenCV-3.4.16安装包2.将安装包放到/home&#xff0c;并解压3.使用 cmake 安装 opencv4.配置环境5.查看 opencv 的版本信息 二、处理图片&#xff08;一&#xff09;创建文件夹 code &#…

Llama-3公布基础训练设施,使用49000个H100

3月13日&#xff0c;社交、科技巨头Meta在官网公布了两个全新的24K H100 GPU集群&#xff08;49,152个&#xff09;&#xff0c;专门用于训练大模型Llama-3。 此外&#xff0c;Llama-3使用了RoCEv2网络&#xff0c;基于Tectonic/Hammerspace的NFS/FUSE网络存储&#xff0c;继续…

探索轻量级 Java 开发利器 - Spring 框架

CSDN-个人主页&#xff1a;17_Kevin-CSDN博客 收录专栏&#xff1a;《Java》 目录 一、引言 二、Spring 框架的起源与发展 三、Spring 框架的核心特性 四、Spring 框架的应用场景 五、Spring 框架的优点 六、Spring 框架的学习曲线 七、Spring 框架的生态系统 八、总结…

[算法] 牛课题霸 - DP6 连续子数组最大和 - 动态规划

文章目录 题目链接解题过程思路一思路二 题目链接 DP6 连续子数组最大和 解题过程 思路一 两个for循环&#xff0c;遍历。 因为每个元素都要遍历两遍&#xff0c;所以时间复杂度O(n^2)。 简单的测试用例可以通过&#xff0c;但是提交时&#xff0c;一个巨大的数组用例&…

[云原生] Prometheus理论知识及系统搭建

promethues是一个开源的系统监控和报警系统&#xff0c;现在已经加入到CNCF基金会&#xff0c;成为继k8s之后第二个在CNCF托管的项目&#xff0c;在kubernetes容器管理系统中&#xff0c;通常会搭配prometheus进行监控&#xff0c;同时也支持多种exporter采集数据&#xff0c;还…

学c还行,学Python很累,还有其他语言适合我吗?

学c还行&#xff0c;学Python很累&#xff0c;还有其他语言适合我吗&#xff1f; 在开始前我分享下我的经历&#xff0c;我刚入行时遇到一个好公司和师父&#xff0c;给了我机会&#xff0c;一年时间从3k薪资涨到18k的&#xff0c; 我师父给了一些 电气工程师学习方法和资料&a…

微信小程序小案例实战

.wxml: <view class "title">狂飙经典语录 </view> <view class"out"><block wx:if"{{listArr.length}}"> <!-- bloock不会影响排版--><view class"list"><view class"row" wx:…

数字人基础 | 3D手部参数化模型2017-2023

楔子: 2017年年底的泰国曼谷, SIGGRAPH Asia会议上, 来自马普所的 Javier Romero, Dimitrios Tzionas(两人都是 Michael J. Black的学生)发布了事实性的手部参数化模型标准: MANO [1]。 MANO的诞生意味着 Michael J. Black团队在继人体参数化模型 SMPL后, 事实性的将能够表达人…