2025.05.11拼多多机考真题算法岗-第二题

### 华为OD机考数大雁真题及答案解析 #### 题目描述 给定一个字符串 `croakOfFrogs`，表示不同时间点听到的大雁叫声。每只大雁发出的声音序列严格遵循 "quack" 的顺序。返回能够产生所给字符串的最少大雁数量。如果该字符串不是有效的组合，则返回 `-1`。 条件如下： - 输入字符串长度范围：\( 1 \leq croakOfFrogs.length \leq 10^5 \) - 字符串中的字符仅限于 'q', 'u', 'a', 'c' 或者 'k' #### 解决方案 为了计算最小的大雁数量，可以维护五个计数器来跟踪当前正在发声的不同阶段的大雁数目。每当遇到一个新的起始字母（即 'q'），增加相应计数器；当完成一次完整的 “quack” 声音循环时减少这些计数器。还需要确保任何时候后面的字母不会超过前面的字母的数量，否则就不是一个合法的输入[^1]。 下面是具体的实现方法： ```cpp class Solution { public: int minNumberOfGeese(string croakOfGeese) { unordered_map<char, int> count{{'q', 0}, {'u', 0}, {'a', 0}, {'c', 0}, {'k', 0}}; int max_geese = 0; for (char ch : croakOfGeese) { ++count[ch]; // Check the order of characters to ensure validity. if (!(count['q'] >= count['u'] && count['u'] >= count['a'] && count['a'] >= count['c'] && count['c'] >= count['k'])) { return -1; } // Update maximum number of geese at any point in time. max_geese = std::max(max_geese, *std::max_element(count.begin(), count.end(), [](const auto& p1, const auto& p2) { return p1.second < p2.second; })); // When a full sequence is completed ('quack'), decrement all counters by one. if (ch == 'k') { for (auto& pair : count) { --pair.second; } } } // Ensure no incomplete sequences are left over. for (int val : count.values()) { if (val != 0) return -1; } return max_geese; } }; ``` 此代码通过遍历整个字符串并保持对每个声音部分的追踪来解决问题。它还验证了每次读取新字符后的合法性，并在检测到完整的一轮发音后重置计数器。最后检查是否有未完成的序列存在，如果有则返回错误码 `-1`，否则返回最大并发大雁数量作为结果[^3]。