Leetcode 1419:数青蛙(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1419:数青蛙(超详细的解法!!!)

in leetcode with 0 comment

给你一个字符串 croakOfFrogs,它表示不同青蛙发出的蛙鸣声(字符串 "croak" )的组合。由于同一时间可以有多只青蛙呱呱作响,所以 croakOfFrogs 中会混合多个 “croak” 请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

注意:要想发出蛙鸣 "croak",青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母,那么它就不会发出声音。

如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成,请返回 -1

示例 1:

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

示例 2:

输入:croakOfFrogs = "crcoakroak"
输出:2 
解释:最少需要两只青蛙,“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"

示例 3:

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

示例 4:

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

提示:

解题思路

实际上这个问题类似于一个压栈操作,对于五个字符'croak'分别建立栈,然后遍历字符串,对于遍历到的字符,分别压入对应字符栈中。只要栈中的元素个数满足c >= r >= o >= a >= k就是有效的,每个字符栈长度的最大值就是青蛙的个数。当每个字符栈的元素个数都大于0的时候(此时满足一个青蛙叫),我们就可以将每个元素出栈一次,表示一个青蛙。

class Solution:
    def minNumberOfFrogs(self, cr: str) -> int:
        res = 0
        s = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}
        st = [0] * 5
        for i in cr:
            if st[0] >= st[1] >= st[2] >= st[3] >= st[4]:
                st[s[i]] += 1
                res = max(res, st[s[i]])
                if all(v > 0 for v in st):
                    for c in 'croak':
                        st[s[c]] -= 1
            else:
                return -1
        
        if st[0] == st[1] == st[2] == st[3] == st[4]:
            return res
        return -1

实际上当出现'c'的时候就表示出现了一个青蛙,当出现'k'的时候就减少了一个青蛙,那么代码可以这么去写:

class Solution:
    def minNumberOfFrogs(self, cr: str) -> int:
        res, frogs = 0, 0
        st = [0] * 5
        for i in cr:
            if i == 'c':
                st[0] += 1
                frogs += 1
            elif i == 'r':
                st[1] += 1
            elif i == 'o':
                st[2] += 1
            elif i == 'a':
                st[3] += 1
            else:
                st[4] += 1
                frogs -= 1
            res = max(res, frogs)
            if not (st[0] >= st[1] >= st[2] >= st[3] >= st[4]): return -1
        
        if st[0] == st[1] == st[2] == st[3] == st[4]:
            return res
        return -1

reference:

https://leetcode.com/problems/minimum-number-of-frogs-croaking/discuss/586543/C%2B%2BJava-with-picture-simulation

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses