刷题笔记合集🔗

数大雁

问题描述

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

具体的:

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++) {
        char* idx_ptr = strchr(t, s[j]);  // 查找当前字符在标准叫声中的位置
        if (idx_ptr == NULL) continue;  // 如果不在标准叫声中，跳过
        
        int idx = idx_ptr - t;
        int flg = 1;  // 标记是否需要新增大雁
        for (int i = 0; i < v_count; i++) {
            if (v[i] % m == idx) {
                v[i]++;  // 更新大雁状态
                flg = 0;