华为OD 数大雁

题目描述

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

具体的:

1.大雁发出的完整叫声为”quack“，因为有多只大雁同一时间嘎嘎作响，所以字符串中可能会混合多个”quack”。

2.大雁会依次完整发出”quack”，即字符串中’q’ ,‘u’, ‘a’, ‘c’, ‘k’ 这5个字母按顺序完整存在才能计数为一只大雁。如果不完整或者没有按顺序则不予计数。

3.如果字符串不是由’q’, ‘u’, ‘a’, ‘c’, ‘k’ 字符组合而成，或者没有找到一只大雁，请返回-1。

输入描述

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

输出描述

大雁的数量

用例1

输入

quackquack

输出

1

Copy

用例2

输入

qaauucqckk

Copy

输出

-1

Copy

用例3

输入

quacqkuac

Copy

输出

1

用例4

输入

qququaauqccauqkkcauqqkcauuqkcaaukccakkck

输出

5

import java.util.Scanner;

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.next();
        int[] used = new int[str.length()];
        Arrays.fill(used, 0);
        int count = 0;
        int j = 0;
        while(find(str, used)){
            //找到一只，count+1
            count ++;
        }
        if(count == 0){
            System.out.println(-1);
        }else{
            System.out.println(count);
        }
        
        
    }

    //遍历整个字符串，找到连续quack，就表示找到一只，used置为1，这一只可能叫了多次，所以需要遍历到字符串尾部。
    public static Boolean find(String str, int[] used){
        Boolean canFind = false;
        int j = 0;
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 0; i < str.length(); i++){
            if(used[i] != 1 && str.charAt(i) == "quack".charAt(j)){
                j++;
                list.add(i);
                if(j == 5){
                    for(Integer num: list){
                        used[num] = 1;
                    }
                    j = 0;
                    list.clear();
                    canFind = true;
                }
            }
        }
        return canFind;
    }
}