长垣高端建站,网站的修改,wordpress 文章背景透明,开发公司购买的游乐设备计入什么科目1. 题目解析
题目链接#xff1a;1419. 数青蛙 这个问题的理解其实相当简单#xff0c;只需看一下示例#xff0c;基本就能明白其含义了。
2.算法原理
一、模拟青蛙叫声的基本逻辑
在模拟青蛙叫声的过程中#xff0c;我们需要遵循一定的规则来判断何时青蛙会发出声音。…1. 题目解析
题目链接1419. 数青蛙 这个问题的理解其实相当简单只需看一下示例基本就能明白其含义了。
2.算法原理
一、模拟青蛙叫声的基本逻辑
在模拟青蛙叫声的过程中我们需要遵循一定的规则来判断何时青蛙会发出声音。具体规则如下 当遇到字符序列 r、o、a、k 时我们需要检查每个字符之前是否已经有青蛙发出叫声。这是因为青蛙的叫声需要按照一定的顺序来触发如果前面的字符没有被青蛙喊出那么当前字符也无法被喊出。 对于字符 r、o、a、k 的检查我们需要回溯到每个字符的前一个字符查看是否有青蛙已经发出了叫声。如果有则当前字符可以被青蛙喊出否则我们需要直接返回 -1表示无法模拟出青蛙的叫声。 当遇到字符 c 时情况稍有不同。我们需要特别检查字符 k 是否已经被青蛙喊出。这是因为 c 的叫声通常是在 k 的叫声之后发出的作为一种特殊的叫声组合。如果 k 已经被喊出那么青蛙可以继续喊出 c否则我们需要重新开始模拟即重新引入一个青蛙来尝试喊出这些字符。
二、算法执行的详细步骤
根据以上逻辑我们可以将算法的执行过程细化为以下步骤
初始化一个标志位用于记录是否有青蛙发出叫声。遍历输入的字符序列对每个字符进行判断。对于字符 r、o、a、k检查其前一个字符是否已经被青蛙喊出。如果是则更新标志位表示当前字符可以被喊出否则返回 -1。对于字符 c检查字符 k 是否已经被喊出。如果是则允许青蛙喊出 c否则重新开始模拟过程。如果遍历完整个字符序列后青蛙成功地喊出了所有字符则算法执行成功否则返回 -1 表示无法模拟出青蛙的叫声。
3.代码编写
class Solution
{
public:int minNumberOfFrogs(string croakOfFrogs) {string s croak;int n s.size();vectorint hash(n);unordered_mapchar, int idx;for(int i 0; i n; i) idx[s[i]] i;for(const auto ch : croakOfFrogs){if(ch c){if(hash[n - 1]) hash[n - 1]--;hash[0];}else{if(hash[idx[ch] - 1] 0) return -1;hash[idx[ch] - 1]--;hash[idx[ch]];}}for(int i 0; i n - 1; i){if(hash[i]) return -1;}return hash[n - 1];}
};
The Last
嗯就是这样啦文章到这里就结束啦真心感谢你花时间来读。
觉得有点收获的话不妨给我点个赞吧
如果发现文章有啥漏洞或错误的地方欢迎私信我或者在评论里提醒一声~
