当前位置: 首页 > news >正文

力扣: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!

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

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

相关文章:

力扣:1419. 数青蛙

题目&#xff1a; 代码&#xff1a; class Solution { public:int minNumberOfFrogs(string croakOfFrogs){string s "croak";int ns.size();//首先创建一个哈希表来标明每个元素出现的次数&#xff01;vector<int>hash(n); //不用真的创建一个hash表用一个数…...

java_springboot企业人事考勤请假管理信息系统rsglxx+jsp

&#xff08;1&#xff09;熟练掌握Java开发的原理和方法 &#xff08;2&#xff09;熟练学习掌握SSM框架 &#xff08;3&#xff09;熟悉软件开发的流程 &#xff08;4&#xff09;了解中内外互联网中所主流的技术 &#xff08;5&#xff09;深层次的了解计算机学科领域的知识…...

java项目之木里风景文化管理平台(ssm+vue)

项目简介 木里风景文化管理平台实现了以下功能&#xff1a; 前台功能&#xff1a;用户进入系统可以实现首页&#xff0c;旅游公告&#xff0c;景区&#xff0c;景区商品&#xff0c;景区美食&#xff0c;旅游交通工具&#xff0c;红黑榜&#xff0c;个人中心&#xff0c;后台…...

源码安装mysql

使用源码安装mysql&#xff0c;这里选择的版本是mysql5.7.35 ,系统是Centos7.6 官网下载地址&#xff1a;https://downloads.mysql.com/archives/community/ 下载源码压缩包 [rootlocalhost ~]# cd /opt[rootlocalhost opt]# wget https://downloads.mysql.com/archives/get/…...

注解方式优雅的实现Redisson分布式锁

1.前言 随着微服务的快速推进&#xff0c;分布式架构也得到蓬勃的发展&#xff0c;那么如何保证多进程之间的并发则成为需要考虑的问题。因为服务是分布式部署模式&#xff0c;本地锁Reentrantlock和Synchnorized就无法使用了&#xff0c;当然很多同学脱口而出的基于Redis的se…...

服务器安装JDK17 版本显示JDK8

服务器之前安装的是JDK8&#xff0c;后面升级JDK17后&#xff0c;发现执行 java -vsrsion 显示的是此时我的环境变量已经换成了JAVA17的路径 输入&#xff1a; vim /etc/profile 解决办法&#xff1a; 1.更新自己环境变量 bash export JAVA_HOME/usr/local/jdk-17.0.7 …...

利用MCMC 获得泊松分布

写出概率流方程如下 if state 0: if np.random.random() < min([Lambda/2, 1]):state 1else:passelif state 1:if choose_prob_state[i] < 0.5:#选择 1 -> 0&#xff0c;此时的接受概率为min[2/Lambda, 1]if np.random.random() < min([2/Lambda, 1]…...

docker-compose脚本编写及常用命令

安装 linux DOCKER_CONFIG/usr/local/lib/docker/cli-plugins sudo mkdir -p $DOCKER_CONFIG/cli-plugins sudo curl -SL https://521github.com/docker/compose/releases/download/v2.6.1/docker-compose-linux-x86_64 -o $DOCKER_CONFIG/cli-plugins/docker-compose sudo c…...

编译企业微信会话内容存档PHP版SDK扩展

1.下载SDK 如果克隆不了&#xff0c;就页面下载 git clone https://github.com/pangdahua/php7-wxwork-finance-sdk2.下载企微官网C版本的最新sdk文件 下载地址&#xff1a;https://wwcdn.weixin.qq.com/node/wework/images/sdk_20201116.rar 下载以后将解压之后的文件夹里l…...

传统算法:使用 Pygame 实现K-Means 聚类算法

使用 Pygame 模块演示了 K-Means 聚类算法的基本原理。让我逐步解释它的实现: 初始化和基本设置 Pygame 初始化: 通过 pygame.init() 初始化 Pygame。 定义颜色和屏幕大小: 定义了一些颜色常量(WHITE, BLACK, RED, GREEN, BLUE)和屏幕的宽度和高度。 创建 Pygame 窗口:…...

WebUI工作流插件超越ComfyUI

在AI绘画领域&#xff0c;Stable Diffsion是最受欢迎的&#xff0c;因为它是开源软件。 开源有两大优势&#xff0c;一是免费&#xff0c;二是适合折腾。 大量的开发者、爱好者投入无尽的热情&#xff0c;来推动Stable Diffsion的快速发展。 在图形界面方面&#xff0c;WebU…...

Docker容器化平台及其优势和应用场景介绍

Docker是一种开源的容器化平台&#xff0c;它基于操作系统级别虚拟化技术&#xff0c;可以将应用程序及其依赖项打包成一个独立的容器&#xff0c;提供轻量级、一致性、可移植性的应用环境。Docker的基本概念和优势如下&#xff1a; 镜像(Image)&#xff1a;Docker容器的基础&…...

Hive:从HDFS回收站恢复被删的表

场景 一张手工维护的内部表&#xff0c;本来排查没有使用&#xff0c;然后删掉了&#xff0c;发现又需要使用&#xff0c;只能恢复这张表了。 1.确认HDFS是否开启回收站功能 2.查看回收站中的数据 被删除的数据会放在删除数据时使用的用户目录下&#xff0c;如&#xff1a;使…...

TZOJ 1387 人见人爱A+B

答案&#xff1a; #include <stdio.h> void time(int ah, int am, int as, int bh, int bm, int bs, int* sum_h, int* sum_m, int* sum_s) //不需要返回值所以定义void函数&#xff0c;前面6个为输入&#xff0c;然后用指针存给后面三个 {*sum_s (as bs) % 60; …...

校园圈子系统丨交友丨地图找伴丨二手市场等功能丨源码交付支持二开丨APP小程序H5三端交付!

校园圈子系统是一款专为校园生活设计的智能应用&#xff0c;拥有丰富多样的功能模块&#xff0c;提供全方位的服务。无论您是师生还是校友&#xff0c;我们都为您打造了一个与校园紧密相连的交流平台。 通过校园圈子系统&#xff0c;您可以方便地浏览校内最新动态&#xff0c;包…...

java操作windows系统功能案例(一)

下面是一个Java操作Windows系统功能的简单案例&#xff1a; 获取系统信息&#xff1a; import java.util.Properties;public class SystemInfo {public static void main(String[] args) {Properties properties System.getProperties();properties.list(System.out);} }该程…...

【双向链表的实现】

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 前言 1. 双向链表的结构 2. 双向链表的实现 2.1 头文件 ——双向链表的创建及功能函数的定义 2.2 源文件 ——双向链表的功能函数的实现 2.3 源文件 ——双向链表功能的…...

中台战略思想与架构总结

中台战略思想与架构总结 在2015年年中&#xff0c;马云带领阿里高管&#xff0c;拜访了游戏公司Supercell&#xff0c;以《部落战争》《海岛奇兵》《卡通农场》等游戏知名。 Supercell是一家典型的以小团队模式进行游戏开发的公司&#xff0c;一般来说两个员工&#xff0c;或…...

VUE2+THREE.JS点击事件

THREE.JS点击事件 1.增加监听点击事件2.点击事件实现3.记得关闭页面时 销毁此监听事件 1.增加监听点击事件 renderer.domElement.addEventListener("click", this.onClick, false); 注:初始化render时监听 2.点击事件实现 onClick(event) {const raycaster new …...

基于SSM+SpringBoot+Vue小区车位租赁系统

[技术实现] 小区车位租赁系统是使用SSMSpringBootVue前后端分离的管理系统。使用Spring框架可以在自动注入项目层级之间的调用对象&#xff0c;方便解耦&#xff0c;SpringMVC是体现了MVC设计思想的轻量级web框架&#xff0c;对web层进行解耦&#xff0c;使开发更简洁,MyBatis…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...