华为od机试真题-数大雁

### 华为OD机试 数大雁 真题 #### 题目描述 一群大雁往南飞，给定一个字符串记录地面上听到的大雁叫声。大雁发出的完整叫声为“quack”，因为有多只大雁同一时间叫，所以字符串中可能会混合多个“quack”。大雁会依次完整发出“quack”，即字符串中‘q’, ‘u’, ‘a’, ‘c’, ‘k’这5个字母按顺序完整存在才能计数为一次叫声。如果不完整或者没有按顺序则不予计数。如果字符串不是由‘q’, ‘u’, ‘a’, ‘c’, ‘k’字符组合而成，或者没有找到大雁的叫声，请返回-1[^4]。 #### 输入描述 一个字符串，包含大雁“quack”的叫声。字符串长度在1到1000之间。字符串中的字符只有‘q’, ‘u’, ‘a’, ‘c’, ‘k’。 #### 输出描述 输出叫声最少由几只大雁发出。 #### 示例 **示例 1** ```plaintext 输入： "quack" 输出： 1 解释： 只有一只大雁发出了完整的“quack” ``` **示例 2** ```plaintext 输入： "quaquackck" 输出： 2 解释： 至少两只大雁分别发出了“quack”和“quac k ck” ``` **示例 3** ```plaintext 输入： "aucaquakck" 输出： -1 解释： 字符串不满足条件，无法形成有效的“quack” ``` #### 解决方案 为了计算最少有多少只大雁发出了这些叫声，可以采用状态机的方法来跟踪每一只大雁的状态变化。具体实现如下： ```python def min_ducks(s: str) -> int: if set(s) - {'q', 'u', 'a', 'c', 'k'} or s.count('q') != s.count('u') != s.count('a') != s.count('c') != s.count('k'): return -1 states = [0, 0, 0, 0, 0] max_ducks = current_ducks = 0 for char in s: index = "quack".find(char) if index == 0: states[index] += 1 current_ducks += 1 max_ducks = max(max_ducks, current_ducks) elif states[index - 1] > 0: states[index - 1] -= 1 states[index] += 1 if index == 4: current_ducks -= 1 else: return -1 return max_ducks if all(state == 0 for state in states[:-1]) and sum(states) == 0 else -1 print(min_ducks("quack")) # Output: 1 print(min_ducks("quaquackck")) # Output: 2 print(min_ducks("aucaquakck")) # Output: -1 ```