【1419. 数青蛙】

一、题目描述

二、算法原理

三、代码实现

代码实现1：我自己写的比较挫，但是比较简单。

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        unordered_map<char,int> hash;
        hash['c']=0,hash['r']=0,hash['o']=0,hash['a']=0,hash['k']=0;

        for(int i=0;i<croakOfFrogs.size();i++)
        {
            if(croakOfFrogs[i]=='c')
            {
                if(hash['k']==0)
                    hash['c']++;
                else
                {
                    hash['k']--;
                    hash['c']++;
                }

            }
            else if(croakOfFrogs[i]=='r')
            {
                if(hash['c']!=0)
                {
                    hash['r']++;
                    hash['c']--;
                }
                else
                {
                    return -1;

                }
            }
            else if(croakOfFrogs[i]=='o')
            {
                if(hash['r']!=0)
                {
                    hash['o']++;
                    hash['r']--;
                }
                else
                {
                    return -1;

                }
            }
            else if(croakOfFrogs[i]=='a')
            {
                if(hash['o']!=0)
                {
                    hash['a']++;
                    hash['o']--;
                }
                else
                {
                    return -1;

                }
            }
            else if(croakOfFrogs[i]=='k')
            {
                if(hash['a']!=0)
                {
                    hash['k']++;
                    hash['a']--;
                }
                else
                {
                    return -1;
                }
            }
        }
        string str="croa";
        for(int i=0;i<str.size();i++)
        {
            if(hash[str[i]]!=0)
            {
                return -1;
            }
        }
        return hash['k'];
    }
};
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

代码实现2：大佬写的，干净简洁。

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        string str="croak";
        int n=str.size();
        vector<int> hash(n);
        unordered_map<char,int> index;

        for(int i=0;i<n;i++)
        {
            index[str[i]]=i;
        }

        for(auto ch:croakOfFrogs)
        {
            if(ch=='c')
            {
                if(hash[n-1]!=0) hash[n-1]--;
                hash[0]++;
            }
            else
            {
                int i=index[ch];
                if(hash[i-1]==0)
                {
                    return -1;
                }
                else
                {
                    hash[i-1]--;
                    hash[i]++;
                }
            }
        }

        for(int i=0;i<n-1;i++)
        {
            if(hash[i]!=0)
            {
                return -1;
            }
        }
        return hash[n-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
38
39
40
41
42
43
44
45
46