模拟算法【3】——1419.数青蛙

在这里插入图片描述

文章目录

    • 🍥1. 题目
    • 🥮2. 算法原理
    • 🍡3. 代码实现

🍥1. 题目

题目链接:1419. 数青蛙 - 力扣(LeetCode)

给你一个字符串 croakOfFrogs,它表示不同青蛙发出的蛙鸣声(字符串 "croak" )的组合。由于同一时间可以有多只青蛙呱呱作响,所以 croakOfFrogs 中会混合多个 “croak”

请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

要想发出蛙鸣 “croak”,青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母,那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成,请返回 -1

示例 1:

输入:croakOfFrogs = "croakcroak"
输出:1 
解释:一只青蛙 “呱呱” 两次

示例 2:

输入:croakOfFrogs = "crcoakroak"
输出:2 
解释:最少需要两只青蛙,“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"

示例 3:

输入:croakOfFrogs = "croakcrook"
输出:-1
解释:给出的字符串不是 "croak" 的有效组合。 

提示:

  • 1 <= croakOfFrogs.length <= 105
  • 字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'

🥮2. 算法原理

这题是一个比较复杂的模拟,当我们遍历到当前的字符的时候,我们需要看前面是否有“青蛙”叫的字符,就是统计每个字符出现的情况,例如示例二:crcoakroak,当叫到第一个字符c的时候,我们用1标记一下,表示青蛙叫了一下,接下来遍历到r的时候,发现r前面有一个c字符,将前面的青蛙“挪过来”,让它叫r这个字符,即hash[c]--hash[r]++

image-20231130225814100
总结:

  • r o a k的逻辑都是一样的,都需要找一下前驱字符是否在哈希表中存在
    1. 存在前驱-1
    2. 不存在直接返回-1
  • c,找最后一个字符是否在哈希表当中
    1. 存在最后一个字符--,当前字符++
    2. 不存在说明没有青蛙叫,当前字符++

🍡3. 代码实现

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs){string cry = "croak";int n = cry.size();vector<int> hash(n);    //模拟哈希表unordered_map<char,int> index;  //存下标[ch,ch下标]for(int i=0; i<n; i++)index[cry[i]] = i;for(auto ch : croakOfFrogs){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;hash[i-1]--;hash[i]++;}}for(int i=0; i<n-1; i++)if(hash[i]!=0)return -1;return hash[n-1];}
};

运行结果:
在这里插入图片描述


模拟算法相关题目文章链接:
简单:1576. 替换所有的问号、495.提莫攻击
中等:6. N 字形变换、38. 外观数列

模拟算法主要就是锻炼将思路转换为代码的能力,没有太多套路,遇到了就按照思路一步一步写出来即可。

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

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

相关文章

17. Python 数据库操作之MySQL和SQLite实例

目录 1. 简介2. 使用PyMySQL2. 使用SQLite 1. 简介 数据库种类繁多&#xff0c;每种数据库的对外接口实现各不相同&#xff0c;为了方便对数据库进行统一的操作&#xff0c;大部分编程语言都提供了标准化的数据库接口&#xff0c;用户不需要了解每种数据的接口实现细节&#x…

Docker篇之docker部署harbor仓库

一、首先需要安装docker step1&#xff1a;安装docker #1、安装yun源 yum install -y yum-utils #2、配置yum源 yum-config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo # 如果上面源不稳定的话&#xff0c;更换为下列的aliyun源 yu…

SpringBoot 整合 Neo4j 实战(头歌)

文章目录 第1关&#xff1a;认识 Spring DATA Neo4J任务描述相关知识Spring DATA Neo4J - 简介Spring JDBC / Spring ORM 模块的缺点&#xff1a;Spring 数据模块的优点&#xff1a;Spring 数据模块功能&#xff1a;Spring DATA Neo4j 模块的附加功能&#xff1a; Spring DATA …

Modbus RTU协议及modbus库函数使用

一、与Modbus TCP的区别 在一般工业场景使用modbus RTU的场景还是更多一些&#xff0c;modbus RTU基于串行协议进行收发数据&#xff0c;包括RS232/485等工业总线协议。 与modbus TCP不同的是RTU没有报文头MBAP字段&#xff0c;但是在尾部增加了两个CRC检验字节&#xff08;CRC…

【Web】UUCTF 2022 新生赛 个人复现

目录 ①websign ②ez_rce ③ez_upload ④ez_unser ⑤ezsql ⑥ezpop ⑦funmd5 ⑧phonecode ⑨ezrce ①websign 右键打不开&#xff0c;直接抓包发包看源码 ②ez_rce “反引号” 在PHP中会被当作SHELL命令执行 ?codeprintf(l\s /); ?codeprintf(ta\c /ffffffffffl…

特征变换1

编译工具&#xff1a;PyCharm 有些编译工具不用写print可以直接将数据打印出来&#xff0c;pycharm需要写print才会打印出来。 概念 1.特征类型 特征的类型&#xff1a;“离散型”和“连续型” 机器学习算法对特征的类型是有要求的&#xff0c;不是任意类型的特征都可以随意…

Spring RabbitMQ那些事(2-两种方式实现延时消息订阅)

目录 一、序言二、死信交换机和消息TTL实现延迟消息1、死信队列介绍2、代码示例(1) 死信交换机配置(2) 消息生产者(3) 消息消费者 3、测试用例 三、延迟消息交换机实现延迟消息1、安装延时消息插件2、代码示例(1) 延时消息交换机配置(2) 消息生产者(3) 消息消费者 3、测试用例 …

set和map + multiset和multimap(使用+封装(RBTree))

set和map 前言一、使用1. set(1)、模板参数列表(2)、常见构造(3)、find和count(4)、insert和erase(5)、iterator(6)、lower_bound和upper_bound 2. multiset3. map(1)、模板参数列表(2)、构造(3)、modifiers和operations(4)、operator[] 4. multimap 二、封装RBTree迭代器原理R…

科技与教育:未来教育的新趋势

在21世纪&#xff0c;科技的快速发展正在深刻地改变教育行业。从在线学习平台到虚拟现实教室&#xff0c;科技为教育带来了革命性的变化。本文将探讨科技如何影响现代教育&#xff0c;并预测未来教育的发展趋势。 一、科技在教育中的应用 在线学习平台&#xff1a;通过平台如C…

JSON 与 FastJSON

JSON 与 FastJSON JSON JavaScript Object Notation&#xff08;JavaScript 对象表示法&#xff09;是目前最常用的执行对象序列化的方式。 虽然 json 最初是为了在 JavaScript 语言中使用的&#xff0c;但实际上 json 本身跟语言没有任何关系&#xff0c;各种编程语言都可以使…

微服务--08--Seata XA模式 AT模式

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 分布式事务Seata 1.XA模式1.1.两阶段提交1.2.Seata的XA模型1.3.优缺点 AT模式2.1.Seata的AT模型2.2.流程梳理2.3.AT与XA的区别 分布式事务 > 事务–01—CAP理论…

Flutter使用flutter_gen管理资源文件

pub地址&#xff1a; https://pub.dev/packages/flutter_gen 1.添加依赖 在你的pubspec.yaml文件中添加flutter_gen作为开发依赖 dependencies:build_runner:flutter_gen_runner: 2.配置pubspec.yaml 在pubspec.yaml文件中&#xff0c;配置flutter_gen的参数。指定输出路…

msvcp140.dll的解决方法有哪些。详细解析五种可以修复msvcp140.dll丢失的方法

引言&#xff1a; 在日常使用电脑的过程中&#xff0c;我们可能会遇到一些错误提示&#xff0c;其中之一就是“msvcp140.dll丢失”。那么&#xff0c;什么是msvcp140.dll文件&#xff1f;它的作用是什么&#xff1f;当它丢失时会对电脑产生什么影响&#xff1f;本文将详细介绍…

使用elementPlus去除下拉框蓝色边框

// 下拉框去除蓝色边框 .el-select {--el-select-input-focus-border-color: none !important; }

仅仅通过提示词,GPT-4可以被引导成为多个领域的特定专家

The Power of Prompting&#xff1a;提示的力量&#xff0c;仅通过提示&#xff0c;GPT-4可以被引导成为多个领域的特定专家。微软研究院发布了一项研究&#xff0c;展示了在仅使用提策略的情况下让GPT 4在医学基准测试中表现得像一个专家。研究显示&#xff0c;GPT-4在相同的基…

【bug篇】Tomcat一直报错,但是代码没问题

代码都没有问题&#xff0c;就是报404错误&#xff0c;原因竟然是版本不兼容&#xff0c;搞了我好长时间&#xff0c;简直麻了&#xff01;&#xff01;&#xff01; 因为我的Tomcat是11版本的&#xff0c;所以导入的servlet和jsp依赖应该是下面这些&#xff1a; <!-- Serv…

c++之STL

首先我们来仔细研究string 首先我们需要实现string的构造函数和析构函数。有new就有delete. 然后我们实现size()和c_str()&#xff0c;其中c_str就是可以将string类型转换为char*类型返回。 通过运算符重载&#xff0c;我们就可以实现string的[]访问。 然后我们实现和append。 …

【机器学习】平滑滤波

平滑滤波技术 平滑滤波&#xff0c;顾名思义就是对信号进行处理使之整体显得更加平滑&#xff0c;降低噪声影响&#xff0c;提高信号质量&#xff0c;它常见于数字信号处理和图像处理&#xff0c;一般意义上的数字信号多体现于一维数据&#xff0c;图像信号多体现于二维数据。…

mysql:免费的GUI客户端工具推荐并介绍常用的操作

给大家推荐几个常用的 mysql 数据库客户端 sequel-pro sequel-ace 官网下载地址 免费 sequel-ace 可以理解为 Sequel Pro 的升级版&#xff0c;由于Sequel Pro官方不维护了&#xff0c;特别是对 MySQL 8.0 支持不好&#xff0c;所以现在由社区维护了新分支 sequel-ace&#x…

人力资源管理后台 === 角色管理

目录 1.组织架构-编辑部门-弹出层获取数据 2.组织架构-编辑部门-编辑表单校验 3.组织架构-编辑部门-确认取消 4.组织架构-删除部门 5.角色管理-搭建页面结构 6.角色管理-获取数据 7.角色管理-表格自定义结构 8.角色管理-分页功能 9.角色管理-新增功能弹层 10.角色管理…