力扣:1419. 数青蛙

题目:

代码:

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs){string s= "croak";int n=s.size();//首先创建一个哈希表来标明每个元素出现的次数!vector<int>hash(n); //不用真的创建一个hash表用一个数组模拟即可!//创建一个哈希表用于统计某字符的下标!因为后面需要用到某个字符前面的下标用于解题!unordered_map<char,int>Index;//将每个元素的下标映射到Index哈希表中!for(int i=0;i<n;i++){Index[s[i]]=i;}//遍历给出的字符串求出最少的青蛙个数!for(auto ch:croakOfFrogs){//其中c字符为一种情况!然后再把其他情况归并一起(因为他们的特性都一样!)//字符为c的情况!if(ch=='c'){if(hash[n-1]!=0){hash[n-1]--;}hash[0]++;}//为其他字符的情况!else{//求出该字符对于的下标!int i=Index[ch];if(hash[i-1]==0){return -1;}else{hash[i]++;hash[i-1]--;}}}//最后遍历一下哈希表!如果除了n-1的位置,其他位置有不为0的情况!直接返回-1!for(int i=0;i<n-1;i++){if(hash[i]!=0){return -1;}}return hash[n-1];}
};

算法图示:

算法思路:

通过题目的描述,需要求出最少的青蛙的个数!因为一个青蛙只有将croak全部叫完,才能重新叫!且求的是最少的青蛙的个数!所以尽可能的不让青蛙停止croak叫!叫完如果仍有新的蛙叫,首先选择让已有的青蛙继续叫,只有没有青蛙叫完的情况下,才会新增一个青蛙来进行叫!

本代码具有通用性!!!创建一个与蛙叫的字符个数相同的哈希表(其实无需真正创建哈希表,只要创建一个数组来统计某个字符出现的个数即可!)

仅仅创建一个哈希表也是可以解决问题的,只不过下面要通过多次if ,else if,来一一列举出现的情况!所以再新建一个真的哈希表用于出现蛙叫字符出现的下标即可!!因为我们要求青蛙的最少个数!所以当一个蛙叫字符出现时,首先考虑的是看看其前面是否出现了!如果没有出现的话,直接返回-1,因为此时不满足情况!当前面的元素存在时,只需将前面的元素--,当前元素++即可!

因为第一个字符没有前缀字符!所以与后面的字符所区分的情况又不一样!当元素为第一个字符时,只需要判断最后字符是否存在,如果存在--,不存在++即可!最后只需要统计出最后一个字符出现的个数即可!

需要注意的是:当最后遍历完成后,如果还有其它字符的个数不为0时,直接返回-1

例如 "crroak" 这种情况!根本不可能出现这种蛙叫,所以返回-1!

最后当遍历完字符串之后,只需要返回哈希表中最后一个元素的个数即可!

对应上图的规律编写代码即可完成求解!!

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

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

相关文章

40.0/jdbc/Java数据连接/jar包运用增删改

目录 40.1. 回顾 40.2. 正文 40.1 为什么需要jdbc 40.2 如何连接mysql数据库 40 .3 jdbc容易出现的错误 40.4 完成删除 40.5 完成修改 40.1. 回顾 1. 自联查询: 自己连接自己的表。注意:一定要为表起别名。 2. 嵌套查询: 把一个查询的结果作为另一个查询的条件值。 3. 组…

高效率:使用DBeaver连接spark-sql

提高运行效率一般采取底层使用spark引擎替换成hive引擎的方式提高效率&#xff0c;但替换引擎配置较为复杂考虑到兼容版本且容易出错&#xff0c;所以本篇将介绍使用DBeaver直接连接spark-sql快速操作hive数据库。 在spark目录下运行以下命令&#xff0c;创建一个SparkThirdSe…

计算机网络:网络层

0 本节主要内容 问题描述 解决思路 1 问题描述 两大问题&#xff08;重点&#xff0c;也是难点&#xff09;&#xff1a; 地址管理&#xff1b;路由选择。 1.1 子问题1&#xff1a;地址管理 网络上的这些主机和节点都需要使用一种规则来区分&#xff0c;就相当于是一种身…

数据可视化:用图表和图形展示数据

写在开头 在当今信息爆炸的时代,海量的数据如同一座沉默的宝库,等待着我们挖掘和理解。然而,这些庞大的数据集本身可能令人望而生畏。在这个时候,数据可视化成为了解数据、发现模式和传达信息的强大工具。本篇博客将带领你探索数据可视化的奇妙世界,学习如何在python中使…

【Java程序员面试专栏 专业技能篇 】Java SE核心面试指引(四):Java新特性

关于Java SE部分的核心知识进行一网打尽,包括四部分:基础知识考察、面向对象思想、核心机制策略、Java新特性,通过一篇文章串联面试重点,并且帮助加强日常基础知识的理解,全局思维导图如下所示 本篇Blog为第四部分:Java新特性,子节点表示追问或同级提问 Java8新特性…

第一百八十五回 如何禁止页面跟随手机自动旋转

文章目录 1. 概念介绍2. 使用方法2.1 全面禁止2.2 局部禁止3. 示例代码4. 内容总结我们在上一章回中介绍了"如何自定义Radio组件"相关的内容,本章回中将介绍 如何禁止页面随手机自动旋转.闲话休提,让我们一起Talk Flutter吧。 1. 概念介绍 在手机默认设置下,手机…

1.ORB-SLAM3中如何保存多地图、关键帧、地图点到二进制文件中

1 保存多地图 1.1 为什么保存(视觉)地图 因为我们要去做导航&#xff0c;导航需要先验地图。因此需要保存地图供导航使用&#xff0c;下面来为大家讲解如何保存多地图。 1.2 保存多地图的主函数SaveAtlas 2051 mStrSaveAtlasToFile是配置文件中传递的参数&#xff1a; 这里我们…

jsoup登录日志平台后调企业微信机器人自动发送错误日志告警

一、需求&#xff1a;错误日志Top10告警发送 二、需求分解 jsoup实现登录&#xff0c;获取到cookie和token等用户鉴权信息获取接口相应的key值调用日志平台错误日志Top榜接口&#xff0c;查询到结果集调用企业微信机器人发送消息接口加上定时任务&#xff0c;可以实现定时发送…

11月30日作业

作业&#xff1a; 设计一个Per类&#xff0c;类中包含私有成员:姓名、年龄、指针成员身高、体重&#xff0c;再设计一个Stu类&#xff0c;类中包含私有成员:成绩、Per类对象p1&#xff0c;设计这两个类的构造函数、析构函数和拷贝构造函数。 #include <iostream>using n…

vue.js ——Vuex

基本概念 vue进行开发过程中有没有遇到这样一种场景&#xff0c;就是有些时候一些数据是一种通用的共享数据&#xff08;比如登录信息&#xff09;&#xff0c;那么这类数据在各个组件模块中可能都会用到&#xff0c;如果每个组件中都去后台重新获取那么势必会造成性能浪费&am…

嵌入式Linux:ARM驱动+QT应用+OpenCV人脸识别项目实现

一、前言&#xff1a; 这个项目主要分为两部分&#xff0c;客户端&#xff08;ARM板端&#xff09;负责利用OpenCV采集人脸数据&#xff0c;利用TCP将人脸数据发送给服务器&#xff0c;然后服务器根据人脸数据进行人脸识别&#xff0c;将识别后的结果返还给客户端&#xff0c;客…

Unity中Shader编译目标渲染器

文章目录 前言一、Unity在打包时&#xff0c;会把Shader编译成不同平台对应的代码我们在状态栏&#xff0c;可以看见我们目前所处于的目标平台 二、在Unity中&#xff0c;怎么指定目标平台1、#pragma only_renderers2、#pragma exclude_renderers 三、我们测试一下看看效果1、 …

C语言贪吃蛇(有详细注释)

这个贪吃蛇是在比特特训营里学到的&#xff0c;同时我还写了用EasyX图形库实现的图形化贪吃蛇&#xff0c;含有每个函数的实现以及游戏中各种细节的讲解&#xff0c;感兴趣的可以去看一看。 贪吃蛇小游戏 实现效果 以下就是源码&#xff0c;感兴趣的小伙伴可以cv自己玩一玩改…

Node.js+Express+Nodemon+Socket.IO构建Web实时通信

陈拓 2023/11/23-2023/11/27 1. 简介 Websocket WebSocket是一种在单个TCP连接上提供全双工通讯的协议。特别适合需要持续数据交换的服务&#xff0c;例如在线游戏、实时交易系统等。 Websocket与Ajax之间的区别 Ajax代表异步JavaScript和XML。它被用作一组Web开发技术&…

java实战(四):编写学生信息管理系统页面·

1.要求 编写程序 实现表格的输入和编辑功能。界面如下&#xff1a; 1、用户按插入键后&#xff0c;把学号、姓名和成绩插入到最后一行&#xff0c;序号显示当前的行号。 2、当用户选中表格的某一行时&#xff0c;按删除按钮&#xff0c;则这一行从表格中删除 3、编辑功能&am…

Linux常用命令——vi命令

文章目录 vi的工作模式常用快捷键提示和技巧结论 Linux环境下的vi编辑器不仅以其强大的功能著称&#xff0c;也因其快捷键而闻名。这些快捷键可以显著提高编辑效率&#xff0c;是每个使用vi的人必须掌握的。下面将扩展介绍vi的一些常用快捷键。 vi的工作模式 vi主要有两种模式…

Linux信号超详细剖析

预备知识&#xff1a; 一、信号产生(OS发给进程) 1、键盘组合键 Linux中&#xff0c;一次登录对应一个终端&#xff0c;bash/shell。且只允许一个进程是前台进程&#xff0c;默认就是bash/shell&#xff0c;其它都是后台进程。获取键盘输入的是前台进程。 Ctrlc: 向前台进程…

【android开发-01】android中toast的用法介绍

1&#xff0c;android中toast的作用 在Android开发中&#xff0c;Toast是一种用于向用户显示简短消息的轻量级对话框。它通常用于向用户提供一些即时的反馈信息&#xff0c;例如操作结果、提示或警告。 Toast的主要作用如下&#xff1a; 提供反馈&#xff1a;Toast可以在用户…

每日一练2023.12.1——帅到没朋友【PTA】

题目链接&#xff1a;L1-020 帅到没朋友 题目要求&#xff1a; 当芸芸众生忙着在朋友圈中发照片的时候&#xff0c;总有一些人因为太帅而没有朋友。本题就要求你找出那些帅到没有朋友的人。 输入格式&#xff1a; 输入第一行给出一个正整数N&#xff08;≤100&#xff09;&…

【MySQL】视图:简化查询

文章目录 create view … as创建视图更改或删除视图drop view 删除视图replace关键字&#xff1a;更改视图 可更新视图with check option子句&#xff1a;防止行被删除视图的其他优点简化查询减小数据库设计改动的影响使用视图限制基础表访问 create view … as创建视图 把常用…