最新华为OD机试-E卷-数大雁(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 编程一对一辅导

✨ 本系列打算持续跟新华为OD-E/D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷目录，全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目敬请期待

最新华为OD机试目录: https://www.nowcoder.com/share/jump/3022116661724989756887

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

🐦 数大雁

问题描述

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

具体的:

1. 大雁发出的完整叫声为"quack"，因为有多只大雁同一时间嘎嘎作响，所以字符串中可能会混合多个"quack"。

2. 大雁会依次完整发出"quack"，即字符串中 、、、、 这 5 个字母按顺序完整存在才能计数为一只大雁。如果不完整或者没有按顺序则不予计数。

3. 如果字符串不是由 、、、、 字符组合而成，或者没有找到一只大雁，请返回 。

输入格式

一个字符串，包含大雁 quack 的叫声。 字符串长度 ，字符串中的字符只有 、、、、。

输出格式

输出一个整数，表示大雁的数量。

样例输入 1

quackquack

样例输出 1

1

样例解释 1

这个输入字符串正好包含两个完整的、连续的 "quack"。一只大雁可以发出这样的声音序列，所以最少需要 1 只大雁。

样例输入 2

qaauucqcaa

样例输出 2

-1

样例解释 2

这个输入字符串中的字符虽然都是 'q'、'u'、'a'、'c'、'k' 中的一个，但是它们的顺序不正确。没有一个完整的 "quack" 序列，因此返回 -1。

样例输入 3

quacqkuackquack

样例输出 3

2

样例解释 3

这个输入字符串可以被解释为两只大雁的叫声交错：

• 第一只大雁：quack
• 第二只大雁：quackquack

第二只大雁发出了两次完整的 "quack"，而第一只大雁只发出了一次。因此，最少需要 2 只大雁才能产生这样的叫声序列。

样例输入 4

qququaauqccauqkkcauqqkcauuqkcaaukccakkck

样例输出 4

5

样例解释 4

这个输入字符串可以被解释为五只大雁的叫声交错。每只大雁至少完整发出了一次 "quack"。

样例输入 5

quacqkuquacqkacuqkackuack

样例输出 5

3

样例解释 5

这个输入字符串可以被解释为三只大雁的叫声交错，每只大雁都完整发出了至少一次 "quack"。

数据范围

字符串长度

题解

这道题的核心思路是模拟大雁叫声的过程，同时统计最少需要多少只大雁才能发出给定的叫声序列。

关键在于如何处理交错的叫声。

使用一个数组来记录每只大雁当前叫声的状态。遍历输入字符串，对每个字符进行处理：

1. 如果是 'q'，检查是否有空闲的大雁（状态为 0），如果没有，就增加一只新的大雁。
2. 对于其他字符，查找是否有大雁正在等待发出这个音。
3. 如果找到了匹配的大雁，更新它的状态。
4. 如果一只大雁完成了整个 "quack"，将其状态重置为 0，表示可以开始新的叫声。

参考代码

• Python

def count_ducks(s):
    t = "quack"  # 标准叫声
    m = len(t)   # 标准叫声的长度
    v = []       # 用于存储每只大雁的当前状态

    for ch in s:
        idx = t.find(ch)  # 查找当前字符在标准叫声中的位置
        if idx == -1:     # 如果不在标准叫声中，跳过
            continue
        
        flg = True        # 标记是否需要新增大雁
        for i in range(len(v)):
            if v[i] % m == idx:
                v[i] += 1  # 更新大雁状态
                flg = False
                break
        
        if flg and idx == 0:
            v.append(1)   # 新增大雁，状态设为1

    # 统计完成至少一次完整叫声的大雁数量
    cnt = sum(1 for i in v if i >= m)
    res = cnt if cnt > 0 else -1

    return res

# 读取输入
s = input().strip()
# 计算并输出结果
print(count_ducks(s))

• C

#include <stdio.h>
#include <string.h>

#define MAX_LEN 1001

int count_ducks(char* s) {
    char* t = "quack";  // 标准叫声
    int m = strlen(t);  // 标准叫声的长度
    int v[MAX_LEN] = {0};  // 用于存储每只大雁的当前状态
    int v_count = 0;  // 当前大雁数量

    for (int j = 0; s[j]; j++) {