个人中心
文章发布
退出
作者热门文章
- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
26
4
题目地址：https://leetcode-cn.com/contest/weekly-contest-185/problems/minimum-number-of-frogs-croaking/
给你一个字符串 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
提示：
1、 1<=croakOfFrogs.length<=10^5；
2、 字符串中的字符只有'c','r','o','a'或者'k'；
按顺序出现的 "croak" 即为一次青蛙叫，问给出的字符串中最少有多少个青蛙。
这个题是消消乐问题。
这个题我第一想法是保留各个青蛙的叫声字符串，然后进行查找、匹配、消除。但这个做法会超时，因此不能全部保留青蛙的叫声字符串。
其实我们没有必要保留所有的字符串，只需要知道各个前缀出现的次数就行了。
对叫声字符串进行一遍循环，根据 croak 每个字符的前面的字符是什么，对其前面的字符进行-1，当前字符+1。
里面有两个特例：起始的字符"c"不需要查找前面的字符，结束的字符"k"不需要对当前字符+1。
举例看下匹配的过程：
输入： "croakcroak"
匹配的过程：
c
Counter({'c': 1})
r
Counter({'r': 1, 'c': 0})
o
Counter({'o': 1, 'c': 0, 'r': 0})
a
Counter({'a': 1, 'c': 0, 'r': 0, 'o': 0})
k
Counter({'c': 0, 'r': 0, 'o': 0, 'a': 0})
c
Counter({'c': 1, 'r': 0, 'o': 0, 'a': 0})
r
Counter({'r': 1, 'c': 0, 'o': 0, 'a': 0})
o
Counter({'o': 1, 'c': 0, 'r': 0, 'a': 0})
a
Counter({'a': 1, 'c': 0, 'r': 0, 'o': 0})
k
Counter({'c': 0, 'r': 0, 'o': 0, 'a': 0})
Python代码如下：
class Solution:
def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
count = collections.Counter()
prev = {"k" : "a", "a": "o", "o": "r", "r" : "c"}
res = 0
for c in croakOfFrogs:
if c == "c":
count[c] += 1
else:
if count[prev[c]] > 0:
if c != "k":
count[c] += 1
count[prev[c]] -= 1
else:
return -1
res = max(res, sum(count.values()))
return res if sum(count.values()) == 0 else -1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发
26
4
0
为了打败我的游戏，每当你落在睡莲上时，它都会将睡莲 (0-4) 作为数字添加到字符串中。然后，要查看是否获胜，字符串必须包含 0-4 的所有数字。我怎样才能使这成为可能？我最初有这个，但这不起作用，因
这与树叶在不同时间落下的经典 codility Frog-River-One 问题不同。 Problem statement 有一个地方被截断了:如果猴子可以跳过河流，函数返回0。如果不可能跳过河流，
我是 Prolog 的新手，遇到了一个看起来很容易实现的逻辑谜题，但在网上搜索了 2 天后，我仍然无法理解如何在 Prolog 中解决它。 三只 Frog 和三只蟾蜍排成一排，如下图的起始状态所示。
我使用 Screaming Frog 作为从 URL 生成的 Json 中提取数据的一种方式。 生成的 Json 是这种形式: {"ville":[{"codePostal":"13009","vil
我正在创建一个 Frog 类型的游戏，并且已经在让程序做我想做的事情方面取得了很大的进展。然而，我开始认为要完成游戏，我将不得不使用大量代码，并且必须有一种更简单的方法来达到相同的结果。我不是在寻找答
Frog 跳的最后一个变体显示在 the video 的末尾. In short, you have n number of lily pads in a line and one frog on e
我处理下面提供的 Codility 问题， 斐波那契数列使用以下递归公式定义: F(0) = 0 F(1) = 1 F(M) = F(M - 1) + F(M - 2) if M >= 2 一只小 F
我遇到了这个问题，但无法想出解决方案。有一场 Frog 赛跑， Frog 有一定数量的有效跳步。它可以向前或向后移动。为了赢得比赛， Frog 必须尽可能靠近终点线，但不能越过终点线。 例子。6, 1
我一直在尝试解决 Codility 网页上的 Java 练习。 下面是上述练习和我的解决方案的链接。 https://codility.com/demo/results/demoH5GMV3-PV8
我正在解决 Codility 的以下问题: 一只小 Frog 想要到河的另一边。 Frog 当前位于位置 0，想要到达位置 X。树叶从树上掉到河面上。 给定一个非空的零索引数组 A，它由 N 个代表落
对不起我的英语不好，我来自意大利XD 我用一个简单的图形选择完成了 Frog 游戏:带有大量更新标签的网格布局。它工作得很好。我可以设置图标而不是标签，但现在我想更好地佩戴它，我的老师告诉我从 QGr
我的大部分编程经验都是使用表单(Windows 窗体或 ASP.NET)或连接硬件的小型嵌入式项目。最近我开始学习一些 iPhone 开发教程。我有兴趣学习 Objective-C 和 iPhone
所以我正在创建一个 Frog 游戏，我已经得到了一切，但我遇到了一个小问题，我的碰撞系统非常不一致，我一直在试图找出是什么，但我不太明白它是什么。我希望它在碰到矩形时立即停止。任何帮助都会得到帮助。
我试图从礼貌中做这个练习: 一只小 Frog 想要到达河的对岸。 Frog 目前位于位置 0，想要到达位置 X。树叶从树上落到河面上。 给定一个非空的零索引数组 A，它由 N 个表示落叶的整数组成。
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎与 help center 中定义的范围内的编程无关。 . 关闭 5 年前。 Improve
我正在尝试为我的网站生成站点地图，但它只检测主页。我使用的以下生成器 https://www.xml-sitemaps.com/ 即使是 Yoast SEO 插件站点地图在谷歌网站管理员工具中也不被接
题目地址：https://leetcode-cn.com/contest/weekly-contest-185/problems/minimum-number-of-frogs-croaking/
所以这是另一个可能著名的 codility 平台的方法，关于 Frog 过河的任务。很抱歉，如果以不当的方式提出这个问题，这是我在这里的第一篇文章。 The goal is to find the e
这是一个谜题，您的目标是将 Frog 头与内边缘的 body 配对。随附的图片显示已解决的难题。 我想过如何用 Python 解决这个难题。我的想法是将图 block 表示为 2x2 numpy 矩阵
这对我来说有点尴尬，但我有一个软件工程类(class)的期末元素，我一直在寻找教程，这样我就可以看到和学习 html css 和 javascript 以在我的元素中实现它。我从来没有研究过这些，
我是一名优秀的程序员,十分优秀！