leetcode-数青蛙

56 阅读 0 评论 37 点赞

我是靠谱客的博主飘逸台灯，最近开发中收集的这篇文章主要介绍leetcode-数青蛙，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目是LeetCode第185场周赛的第三题，链接：数青蛙。具体描述：给你一个字符串croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 “croak” ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以croakOfFrogs中会混合多个 “croak” 。请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。注意：要想发出蛙鸣 “croak”，青蛙必须依序输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成，请返回 -1 。

示例1：

输入：croakOfFrogs = "croakcroak"
输出：1 
解释：一只青蛙 “呱呱” 两次

示例2：

输入：croakOfFrogs = "crcoakroak"
输出：2

示例3：

输入：croakOfFrogs = "croakcrook"
输出：-1
解释：给出的字符串不是 "croak" 的有效组合。

示例4：

输入：croakOfFrogs = "croakcroa"
输出：-1

这道题关键在于理解题意，知道一只青蛙叫完一次后又可以重新叫。解法为：统计各字母出现次数，有效的条件是顺序在后面的字母出现次数必须总是小于前面的，否则一定不是有效的字符串。举个例子，比如有字符串croakrcoak，统计到第五个字母之后，五个字母都各出现了一次，在第六个字母上，出现了r，发现在前面的c出现次数为1小于r的出现次数2，此时就可以确定不是有效的了。当有一只青蛙叫完五个字母后，这只青蛙又可以开始从头叫了，所以需要将各个字母的出现次数都减1，那么最终需要的青蛙最少数目就是各个字母出现次数的最大者（表示同一时间有多少只青蛙在叫）。时间复杂度为 $O (n)$ ，空间复杂度为 $O (1)$ 。

JAVA版代码如下：

class Solution {

    private int getIndex(char c) {
        switch (c) {
            case 'c' :
                return 0;
            case 'r':
                return 1;
            case 'o':
                return 2;
            case 'a':
                return 3;
            case 'k':
                return 4;
            default:
                return -1;
        }
    }

    public int minNumberOfFrogs(String croakOfFrogs) {
        char[] chars = croakOfFrogs.toCharArray();
        if (chars.length % 5 != 0) {
            return -1;
        }
        
        int[] counts = new int[5];
        int result = 0;
        for (char c : chars) {
            int idx = getIndex(c);
            ++counts[idx];
            for (int i = 0; i < idx; ++i) {
                if (counts[idx] > counts[i]) {
                    return -1;
                }
            }
            result = Math.max(result, counts[idx]);
            if (idx == 4) {
                for (int i = 0; i < 5; ++i) {
                    --counts[i];
                }
            }
        }
        return result;
    }
}

提交结果如下:

Python版代码如下：

class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        if len(croakOfFrogs) % 5 != 0:
            return -1
        char2idx = {'c' : 0, 'r' : 1, 'o' : 2, 'a' : 3, 'k' : 4}
        counts = [0 for _ in range(5)]
        result = 0
        for c in croakOfFrogs:
            idx = char2idx[c]
            counts[idx] += 1
            if idx > 0 and counts[idx] > counts[idx - 1]:
                    return -1
            result = max(counts[idx], result)
            if idx == 4:
                for i in range(5):
                    counts[i] -= 1
        if sum(counts) > 0:
            return -1
        return result

提交结果如下: