1. 題目解析

題目鏈接：1419. 數(shù)青蛙

這個問題的理解其實相當簡單，只需看一下示例，基本就能明白其含義了。

2.算法原理

一、模擬青蛙叫聲的基本邏輯

在模擬青蛙叫聲的過程中，我們需要遵循一定的規(guī)則來判斷何時青蛙會發(fā)出聲音。具體規(guī)則如下：

1. 當遇到字符序列 'r'、'o'、'a'、'k' 時，我們需要檢查每個字符之前是否已經(jīng)有青蛙發(fā)出叫聲。這是因為青蛙的叫聲需要按照一定的順序來觸發(fā)，如果前面的字符沒有被青蛙喊出，那么當前字符也無法被喊出。

2. 對于字符 'r'、'o'、'a'、'k' 的檢查，我們需要回溯到每個字符的前一個字符，查看是否有青蛙已經(jīng)發(fā)出了叫聲。如果有，則當前字符可以被青蛙喊出；否則，我們需要直接返回 -1，表示無法模擬出青蛙的叫聲。

3. 當遇到字符 'c' 時，情況稍有不同。我們需要特別檢查字符 'k' 是否已經(jīng)被青蛙喊出。這是因為 'c' 的叫聲通常是在 'k' 的叫聲之后發(fā)出的，作為一種特殊的叫聲組合。如果 'k' 已經(jīng)被喊出，那么青蛙可以繼續(xù)喊出 'c'；否則，我們需要重新開始模擬，即重新引入一個青蛙來嘗試喊出這些字符。

二、算法執(zhí)行的詳細步驟

根據(jù)以上邏輯，我們可以將算法的執(zhí)行過程細化為以下步驟：

1. 初始化一個標志位，用于記錄是否有青蛙發(fā)出叫聲。
2. 遍歷輸入的字符序列，對每個字符進行判斷。
3. 對于字符 'r'、'o'、'a'、'k'，檢查其前一個字符是否已經(jīng)被青蛙喊出。如果是，則更新標志位，表示當前字符可以被喊出；否則，返回 -1。
4. 對于字符 'c'，檢查字符 'k' 是否已經(jīng)被喊出。如果是，則允許青蛙喊出 'c'；否則，重新開始模擬過程。
5. 如果遍歷完整個字符序列后，青蛙成功地喊出了所有字符，則算法執(zhí)行成功；否則，返回 -1 表示無法模擬出青蛙的叫聲。

3.代碼編寫

class Solution 
{
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        string s = "croak";
        int n = s.size();
        vector<int> hash(n);
        unordered_map<char, 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

嗯，就是這樣啦，文章到這里就結束啦，真心感謝你花時間來讀。

覺得有點收獲的話，不妨給我點個贊吧！

如果發(fā)現(xiàn)文章有啥漏洞或錯誤的地方，歡迎私信我或者在評論里提醒一聲~?文章來源地址http://www.zghlxwxcb.cn/news/detail-848220.html

到了這里，關于【Leetcode每日一題】模擬 - 數(shù)青蛙（難度??）（54）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！