20天拿下华为OD笔试之【模拟】2023B-数大雁【欧弟算法】全网注释最详细分类最全的华为OD真题题解

本文主要是介绍20天拿下华为OD笔试之【模拟】2023B-数大雁【欧弟算法】全网注释最详细分类最全的华为OD真题题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 【模拟】2023B-数大雁
  • 题目描述与示例
    • 题目描述
    • 输入
    • 输出
    • 示例一
      • 输入
      • 输出
    • 示例二
      • 输入
      • 输出
    • 示例三
      • 输入
      • 输出
    • 说明
    • 示例四
      • 输入
      • 输出
    • 说明
  • 解题思路
  • 代码
    • 时空复杂度
  • 华为OD算法冲刺训练

【模拟】2023B-数大雁

题目描述与示例

题目描述

一群大雁往南飞,给定一个字符串记录地面上的游客听到的大雁叫声,请给出叫声最少由几只大雁发出。

具体的:

  1. 大雁发出的完整叫声为 "quack",因为有多只大雁同一时间嘎嘎作响,所以字符串中可能会混合多个"quack"
  2. 大雁会依次完整发出"quack",即字符串中 "q" ,"u", "a", "c", "k" 这 5 个字母按顺序完整存在才能计数为一只大雁。如果不完整或者没有按顺序则不予计数。
  3. 如果字符串不是由"q" ,"u", "a", "c", "k"字符组合而成,或者没有找到一只大雁,请返回-1

输入

一个字符串,包含大雁 quack 的叫声。1 <= 字符串长度 <= 1000,字符串中的字符只有 "q" ,"u", "a", "c", "k"

输出

大雁的数量

示例一

输入

quackquack

输出

1

示例二

输入

qaauucqcaa

输出

-1

示例三

输入

quacqkuackquack

输出

2

说明

用不同的颜色表示同一只大雁,quac``q``k``uack``quack,最少需要2只大雁。

以下情况都是2只大雁。

quac``q``k``uack``quack
quac``q``k``uac``q``k``uack
quac``q``k``ua``q``ck``uack
quac``q``k``u``q``ack``uack
quac``q``kq``uack``uack

以下情况需要3只大雁。

quac``q``q``k``uack``uack
qua``q``c``q``k``uack``uack

示例四

输入

quacqkuquacqkacuqkackuack

输出

3

说明

用不同的颜色表示同一只大雁,quacqkuquacqkacuqkackuack,最少需要3只大雁。

解题思路

注意,本题和LC1419. 数青蛙完全一致。

说实话这题乍一看很让人一头雾水。但其实就是根据题意直接模拟即可,主要问题在于大雁能否可以复用这个问题比较麻烦。

首先考虑返回-1,即无法完成所有雁叫的情况:

  • 原字符串s中,所有字符出现的数目不一致,这个可以在最开始的时候做特殊情况的判断。
  • 遍历到某个字符ch时,比如'c',发现其前一个字符即'a'出现的次数少于当前字符,那么无法实现一个完整的雁叫。

我们考虑用一个长度为5cnt数组,来记录"quack"中每个字符被叫了几次,即每个字符的出现个数。要注意,cnt中的计数,并不代表大雁的总个数。cnt的更新直接在循环中进行即可。

再考虑大雁是否可以复用的问题。假设遇到一个新的'q',表示出现了一声新的"quack",如果此时:

  • 'k'的计数大于0,表示之前有某只大雁叫完了,那么这只大雁可以立马抓来复用,我们对cnt整体减1
  • 'k'的计数等于0,表示之前没有任何大雁完成了雁叫,或是先前完成了雁叫的大雁被抓去复用了(无需分辨这两种情况的区别),因此再无需进行任何操作。

思路基本就结束了。这里可以使用一个哈希表word用于取"quack"的各个字符分别对应的01234cnt中的索引idx,即存在word = {ch: i for i, ch in enumerate("quack")}idx在计数过程和判断无法完成雁叫两个地方都会用到。

代码

# 题目:2023B-数大雁
# 分值:200
# 作者:许老师-闭着眼睛学数理化
# 算法:模拟
# 代码看不懂的地方,请直接在群上提问s = input()# 构建一个标记,表示是否出现了异常,初始化为False表示没有异常
isError = False# 排除特殊情况,如果各个字符总数不一致,出现异常
if len(set(collections.Counter(s).values())) != 1:# 标记isError改为TrueisError = True
else:# 构建哈希表,"quack"分别对应01234一共五个索引word = {ch: i for i, ch in enumerate("quack")}# cnt列表:记录"quack"中每个字符被叫了几次,即每个字符的出现个数。# 要注意,cnt中的计数,并不代表大雁的总个数。cnt = [0, 0, 0, 0, 0]for ch in s:# 获得字符ch在列表cnt中的索引idx,即表示"quack"对应的01234一共五个索引idx = word[ch]# ch对应的计数+1cnt[idx] += 1# ch不是"q",且前一个字符数目少于当前字符数目,出现错误if ch != "q" and cnt[idx] > cnt[idx-1]:# 标记isError改为True,同时退出循环isError = Truebreak# 遇到"q",表示出现新的雁叫,可能可以复用之前的大雁,如果:# 1. 之前有某大雁叫过"k",那么这只大雁可以复用,cnt整体-1,表示可以少算一只大雁# 2. 之前没有大雁叫过"k",那么无法进行大雁的复用,无需做任何操作# cnt[4]表示之前叫过"k"的大雁的个数,# cnt[4] >= 1即表示,存在某大雁叫过"k",这只大雁可以拿来复用if ch == "q" and cnt[4] >= 1:cnt = [item-1 for item in cnt]# 如果isError为True,说明出现了异常,输出-1
# 否则最终cnt中所有计数一致,这个数即为所需要的大雁的个数,输出之
print(-1) if isError else print(cnt[0])

时空复杂度

时间复杂度:O(N)。仅需一次遍历数组。

空间复杂度:O(1)。仅需若干常数变量。

华为OD算法冲刺训练

  • 华为OD算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 30+天陪伴式学习,20+直播课时,300+动画图解视频,200+LeetCode经典题,100+华为OD真题,还有简历修改与模拟面试将为你解锁

  • 可查看链接 OD算法冲刺训练课程表 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

这篇关于20天拿下华为OD笔试之【模拟】2023B-数大雁【欧弟算法】全网注释最详细分类最全的华为OD真题题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/403475

相关文章

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

如何为Yarn配置国内源的详细教程

《如何为Yarn配置国内源的详细教程》在使用Yarn进行项目开发时,由于网络原因,直接使用官方源可能会导致下载速度慢或连接失败,配置国内源可以显著提高包的下载速度和稳定性,本文将详细介绍如何为Yarn... 目录一、查询当前使用的镜像源二、设置国内源1. 设置为淘宝镜像源2. 设置为其他国内源三、还原为官方

最详细安装 PostgreSQL方法及常见问题解决

《最详细安装PostgreSQL方法及常见问题解决》:本文主要介绍最详细安装PostgreSQL方法及常见问题解决,介绍了在Windows系统上安装PostgreSQL及Linux系统上安装Po... 目录一、在 Windows 系统上安装 PostgreSQL1. 下载 PostgreSQL 安装包2.

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引(Full-Textindex)的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

如何在Mac上安装并配置JDK环境变量详细步骤

《如何在Mac上安装并配置JDK环境变量详细步骤》:本文主要介绍如何在Mac上安装并配置JDK环境变量详细步骤,包括下载JDK、安装JDK、配置环境变量、验证JDK配置以及可选地设置PowerSh... 目录步骤 1:下载JDK步骤 2:安装JDK步骤 3:配置环境变量1. 编辑~/.zshrc(对于zsh

售价599元起! 华为路由器X1/Pro发布 配置与区别一览

《售价599元起!华为路由器X1/Pro发布配置与区别一览》华为路由器X1/Pro发布,有朋友留言问华为路由X1和X1Pro怎么选择,关于这个问题,本期图文将对这二款路由器做了期参数对比,大家看... 华为路由 X1 系列已经正式发布并开启预售,将在 4 月 25 日 10:08 正式开售,两款产品分别为华

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例