华为OD机试真题---数大雁

题目描述

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

输入描述

• 一个字符串，包含大雁“quack”的叫声。
• 字符串长度在1到1000之间。
• 字符串中的字符只有‘q’, ‘u’, ‘a’, ‘c’, ‘k’。

输出描述

• 输出叫声最少由几只大雁发出。

实现思路

1. 初始化：

   • 定义一个计数器count，用于记录完整叫声“quack”的个数。
   • 定义一个状态变量state，用于跟踪当前已匹配到的“quack”中的字符位置（0表示还未开始匹配，1-5分别表示已匹配到‘q’, ‘qu’, ‘qua’, ‘quac’, ‘quack’的某个状态）。

2. 遍历字符串：

   • 依次遍历字符串中的每个字符。
   • 根据当前字符和状态变量state，更新状态变量state。
     • 如果当前字符是当前状态下期望的字符，则state自增。
     • 如果当前字符不是当前状态下期望的字符，或者已经匹配到“quack”但紧接着的字符不是期望的字符（即非‘q’），则将state重置为0。
   • 当state等于5时，表示找到了一个完整的“quack”，将计数器count加1，并将state重置为0以开始匹配下一个“quack”。

3. 结果处理：

   • 遍历完字符串后，返回计数器count的值作为结果。
   • 如果字符串中不包含任何有效的“quack”叫声（即count始终为0），且字符串不是由‘q’, ‘u’, ‘a’, ‘c’, ‘k’字符组合而成，则返回-1。但根据题目描述，输入已经限定为只包含这些字符，所以实际上返回-1的情况不会发生。

示例代码（Java）

package cn.gov.test.gt4.swjggl.leetcode;public class CountGeese {/*** 计算字符串中“quack”序列的数量* 该方法通过状态转换来识别完整的“quack”序列，每个字符匹配成功则推进状态，完成一次则计数* * @param sounds 输入的字符串，其中可能包含'q', 'u', 'a', 'c', 'k'这些字符组成的“quack”序列* @return 返回在输入字符串中找到的“quack”序列的数量*/public static int countGeese(String sounds) {int count = 0; // 计数器，用于记录找到的“quack”序列的数量int state = 0; // 状态变量，用于跟踪当前匹配到“quack”序列的哪个位置，范围为0-5// 遍历输入的字符串，尝试匹配“quack”序列for (int i = 0; i < sounds.length(); i++) {char c = sounds.charAt(i);// 根据当前状态，决定如何处理当前字符switch (state) {case 0: // 初始状态，寻找'q'if (c == 'q') {state = 1; // 找到'q'，进入下一个状态}break;case 1: // 已找到'q'，寻找'u'if (c == 'u') {state = 2; // 找到'u'，进入下一个状态} else {state = 0; // 未找到'u'，重置状态}break;case 2: // 已找到'qu'，寻找'a'if (c == 'a') {state = 3; // 找到'a'，进入下一个状态} else {state = 0; // 未找到'a'，重置状态}break;case 3: // 已找到'qua'，寻找'c'if (c == 'c') {state = 4; // 找到'c'，进入下一个状态} else {state = 0; // 未找到'c'，重置状态}break;case 4: // 已找到'quac'，寻找'k'if (c == 'k') {count++; // 找到'k'，完成一次“quack”序列的匹配，计数器加一state = 0; // 重置状态，准备下一次匹配} else {state = 0; // 未找到'k'，重置状态}break;default:// 不应进入此分支，因为state的范围已限定在0-5之间break;}}// 题目已限定输入字符串只包含'q', 'u', 'a', 'c', 'k'，所以无需检查字符串内容// 但若需要更严谨的实现，可以添加对字符串内容的检查return count; // 返回找到的“quack”序列的数量}public static void main(String[] args) {String sounds = "quackquackquack";System.out.println("最少由 " + countGeese(sounds) + " 只大雁发出叫声。");}
}

注意

• 在实际机试中，输入数据会由测试系统提供，而不是像示例代码中那样直接写在main方法里。
• 需要根据题目要求和实际情况，调整代码以适应测试环境。
• 题目中已经限定了输入字符串的长度和字符集，这有助于简化代码的实现和减少错误。但在更复杂的场景中，可能需要添加额外的输入验证和错误处理逻辑。

---

运行步骤解析

1、定义类和方法：

• 定义了一个名为 CountGeese 的公共类。
• 类中包含一个静态方法 countGeese，用于计算字符串中“quack”序列的数量。

2、主方法：

• 在 main 方法中，定义了一个字符串 sounds，其值为 “quackquackquack”。
• 调用 countGeese 方法，并将结果输出到控制台。

3、countGeese 方法执行过程：

• 初始化两个变量：count 和 state。

• count 用于记录找到的“quack”序列的数量。

• state 用于跟踪当前匹配到“quack”序列的位置，范围为 0-5。

• 遍历输入字符串 sounds 中的每个字符。

• 使用 switch 语句根据当前状态处理每个字符。

• 状态从 0 开始，依次匹配 ‘q’、‘u’、‘a’、‘c’ 和 ‘k’。

• 每次匹配成功则推进状态，直到找到 ‘k’ 并计数。

• 如果中间任何一个字符不匹配，则重置状态为 0。

4、具体执行过程：

• 对于输入字符串 “quackquackquack”：

• 第一个 ‘q’ 出现时，状态变为 1。

• 接下来的 ‘u’ 出现时，状态变为 2。

• 接下来的 ‘a’ 出现时，状态变为 3。

• 接下来的 ‘c’ 出现时，状态变为 4。

• 最后的 ‘k’ 出现时，状态变为 0 并计数加 1。

• 重复上述过程，最终统计到 3 次完整的“quack”序列。
  5、输出结果：

• main 方法中调用 countGeese 方法并输出结果：

• 输出结果为：“最少由 3 只大雁发出叫声。”