Keshawn_lu's Blog

Leetcode 1419. 数青蛙

字符串
字数统计: 557阅读时长: 2 min
2023/05/06 Share

题目简介

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。

请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

要想发出蛙鸣 “croak”，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成，请返回 -1 。

示例 1：

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

示例 2：

1
2
3
4
5
输入：croakOfFrogs = "crcoakroak"
输出：2 
解释：最少需要两只青蛙，“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"

示例 3：

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

提示：

  • 1 <= croakOfFrogs.length <= 10^5
  • 字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'

思路：

按顺序遍历，定义flogs为当前存在的青蛙数量，res为最大的青蛙数量

当遇到c时，说明新的一只青蛙开始叫了（++flogs，也有可能是以前的青蛙结束了），更新res = max(res, ++flogs)。

否则，观察前一个字符之前是否已经遇到过，若没有，说明不是按顺序叫的，return -1。

当遇到了k，说明这只青蛙叫完了，--flogs。

若最后flogs != 0，说明有青蛙没叫完，return -1。

tip:

  • 若长度不为5的倍数，直接return -1

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {

        if(croakOfFrogs.size() % 5 != 0)
            return -1;

        unordered_map<int, int> count;

        int idx[26] = {};
        string s = "croak";
        for (int i = 0; i < 5; ++i) {

            idx[s[i] - 'a'] = i;
        }

        int res = 0, flogs = 0;
        for(auto& c : croakOfFrogs){

            int i = idx[c - 'a'];
            ++count[i];

            if(i == 0)
                res = max(res, ++flogs);
            else{

                if(--count[i - 1] < 0)  //不能按顺序叫
                    return -1;
                
                if(i == 4)  //一只青蛙结束了
                    --flogs;
            }
        }

        return flogs > 0 ? -1 : res;    //flogs != 0 说明有青蛙没叫完 
    }
};
CATALOG
  1. 1. 题目简介
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网