华为OD机试 - 数大雁（Java 2024 E卷 100分）

本文主要是介绍华为OD机试 - 数大雁（Java 2024 E卷 100分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

具体的:

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

二、输入描述

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

三、输出描述

大雁的数量。

四、测试用例

测试用例1：

1、输入

quackquack

2、输出

测试用例2：

1、输入

qaaauucqckk

2、输出

-1

五、解题思路

题目要求我们计算一个字符串中包含的最少几只大雁发出的完整“quack”叫声。要解决这个问题，我们需要模拟大雁的叫声，并确保每只大雁发出的叫声是完整且按照正确的顺序进行的。

1、题目分析

（1）字符顺序:

一个完整的“quack”叫声必须按顺序包含字符 q -> u -> a -> c -> k。我们需要确保在输入字符串中，字符按这个顺序匹配。

（2）多只大雁同时发声:

字符串可能包含多个“quack”叫声，这些叫声可能是交错的，因此我们需要处理这种情况，并统计这些重叠的叫声。

（3）不合法情况:

如果字符串中存在不符合顺序或无法完成的“quack”，那么就要返回 -1，表示该字符串不是由合法的大雁叫声组成的。

2、解题步骤

使用计数器记录状态:
- 使用五个计数器分别记录字符 q, u, a, c, k 的出现次数，这样我们可以跟踪每一个阶段的字符是否按顺序出现。
遍历字符串:
- 遍历整个字符串，对每个字符进行处理：
  - 如果遇到 q，它可能是一个新的“quack”开始，因此增加 q 的计数器。
  - 如果遇到 u，检查是否有未匹配的 q，如果有则增加 u 的计数器。
  - 类似地处理 a、c 和 k，每次确保字符的顺序匹配。
  - 当遇到 k 时，意味着一个完整的“quack”结束，将所有计数器减一。
计算结果:
- 在处理过程中，维护一个最大并发大雁数量（即同时发出 quack 叫声的最大数量）。
- 最后，如果所有计数器都归零，则返回大雁的最大数量，否则返回 -1。

六、Java算法源码

public class OdTest03 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String quackSequence = sc.next();System.out.println(countDucks(quackSequence));}/*** 计算最少有几只大雁发出完整的 quack 叫声。** @param quackSequence 包含 quack 的字符串* @return 最少的大雁数量，如果无效则返回 -1*/public static int countDucks(String quackSequence) {LinkedList<Integer> qIndices = new LinkedList<>();  // 存储字符 'q' 出现的索引int uCount = 0, aCount = 0, cCount = 0;  // 计数变量，分别记录 u, a, c 的出现次数ArrayList<int[]> quackRanges = new ArrayList<>();  // 存储每个完整 "quack" 的起始和结束索引// 遍历整个字符串for (int i = 0; i < quackSequence.length(); i++) {char currentChar = quackSequence.charAt(i);switch (currentChar) {case 'q':qIndices.add(i);  // 记录 'q' 的索引break;case 'u':if (uCount + 1 <= qIndices.size()) uCount++;  // 确保 'u' 能够匹配已有的 'q'break;case 'a':if (aCount + 1 <= uCount) aCount++;  // 确保 'a' 能够匹配已有的 'u'break;case 'c':if (cCount + 1 <= aCount) cCount++;  // 确保 'c' 能够匹配已有的 'a'break;case 'k':if (cCount >= 1) {  // 找到一个完整的 'quack'quackRanges.add(new int[]{qIndices.removeFirst(), i});  // 记录 'quack' 的起止位置uCount--;aCount--;cCount--;}break;default:return -1;  // 如果出现不合法的字符，直接返回 -1}}// 如果没有找到任何完整的 "quack" 组合，则返回 -1if (quackRanges.isEmpty()) return -1;// 计算同时发出 quack 叫声的最大大雁数量int maxDucks = 1;for (int i = 0; i < quackRanges.size(); i++) {int overlapCount = 1;for (int j = i + 1; j < quackRanges.size(); j++) {if (quackRanges.get(i)[1] >= quackRanges.get(j)[0]) {  // 判断两个 "quack" 之间是否有重叠overlapCount++;}}maxDucks = Math.max(maxDucks, overlapCount);  // 取最大值}return maxDucks;}
}