1419.数青蛙

链接：1419.数青蛙
难度：Medium
标签：字符串、计数
简介：请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

题解 1 - cpp

• 编辑时间：2023-05-06
• 执行用时：24ms
• 内存消耗：9MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        int n = croakOfFrogs.size(), wait[5] = {0}, res = 0;
        unordered_map<char, int> m;
        m['c'] = 0; m['r'] = 1; m['o'] = 2; m['a'] = 3; m['k'] = 4;
        for (int i = 0; i < n; i++) {
            int idx = m[croakOfFrogs[i]];
            if (idx == 0) {
                if (wait[4] == 0) res++;
                else wait[4] -= 1;
                wait[idx]++;
            } else {
                if (wait[idx - 1] == 0) return -1;
                wait[idx - 1]--;
                wait[idx]++;
            }
        }
        return wait[4] == res ? res : -1;
    }
};

题解 2 - python

• 编辑时间：2023-05-06
• 执行用时：172ms
• 内存消耗：16.6MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        n = len(croakOfFrogs)
        wait = [0] * 5
        res = 0
        m = {}
        m['c'] = 0
        m['r'] = 1
        m['o'] = 2
        m['a'] = 3
        m['k'] = 4
        for i in range(n):
            idx = m[croakOfFrogs[i]]
            if idx == 0:
                if wait[4] == 0:
                    res += 1
                else:
                    wait[4] -= 1
                wait[idx] += 1
            else:
                if wait[idx - 1] == 0:
                    return -1
                wait[idx-1] -= 1
                wait[idx] += 1
        return res if wait[4] == res else -1

题解 3 - rust

• 编辑时间：2023-05-06
• 执行用时：4ms
• 内存消耗：2.6MB
• 编程语言：rust
• 解法介绍：同上。

fn get_idx(c: char) -> usize {
    match c {
        'c' => 0,
        'r' => 1,
        'o' => 2,
        'a' => 3,
        'k' => 4,
        _ => 0,
    }
}
fn str_to_vec(s: &String) -> Vec<char> {
    s.chars().collect()
}
impl Solution {
    pub fn min_number_of_frogs(croak_of_frogs: String) -> i32 {
        let croak_of_frogs = str_to_vec(&croak_of_frogs);
        let n = croak_of_frogs.len();
        let mut wait = vec![0; 5];
        let mut res = 0;
        for i in 0..croak_of_frogs.len() {
            let idx = get_idx(croak_of_frogs[i]);
            if idx == 0 {
                if wait[4] == 0 {
                    res += 1
                } else {
                    wait[4] -= 1;
                }
                wait[idx] += 1;
            } else {
                if wait[idx - 1] == 0 {
                    return -1;
                };
                wait[idx - 1] -= 1;
                wait[idx] += 1
            }
        }
        return if wait[4] == res { res } else { -1 };
    }
}