leetcode1419求最长连续序列

前言

又是好久没有更新了

正文

问题来源

本问题来自leetcode上的1419题。

问题描述

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 “croak” ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
注意：要想发出蛙鸣 “croak”，青蛙必须依序输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。
如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成，请返回 -1 。

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

输入：croakOfFrogs = "croakcroa"
输出：-1

分析：

func minNumberOfFrogs(croakOfFrogs string) int {
    m := make(map[byte]int)
    m['c'] = 0 
    m['r'] = 1 
    m['o'] = 2 
    m['a'] = 3 
    m['k'] = 4
    b := []byte(croakOfFrogs)
    s := make([]int, 5)
    ret := 0
    for i := 0; i <len(b); i++ {
        v, ok := m[b[i]] 
        if !ok {
            return -1
        }
        if v == 0 {
            s[0] += 1
            total := s[0] + s[1] + s[2] + s[3]
            if total > ret {
                ret = total
            }
            continue
        }
        if s[v-1] == 0{
            //fmt.Println(i)
            return -1
        } else {
            s[v-1] -= 1 
            s[v] += 1
        }
    }
    if s[0] != 0 || s[1] != 0 || s[2] !=0 || s[3] != 0{
        return -1
    }
    return ret
}

其他人的解法

func minNumberOfFrogs(croakOfFrogs string) int {
    c, r, o, a, k := 0, 0, 0, 0, 0
    ret := -1
    for _, v := range croakOfFrogs {
        if rune(v) == rune('c') {
            c++
        } else if rune(v) == rune('r') {
            r++
        } else if rune(v) == rune('o') {
            o++
        } else if rune(v) == rune('a') {
            a++
        } else if rune(v) == rune('k') {
            k++
        } else {
            return -1
        }
        if r > c || o > r || a > o || k > a {
            return -1
        }
        ret = Max(c - k, ret)
    }
    if c == r && r == o && o == a && a == k {
        return ret
    }
    return -1
}

func Max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

public int minNumberOfFrogs(String croakOfFrogs) {
        int c,r,o,a,k;
        c = 0; r = 0; o = 0; a = 0;k = 0;
        char []chars = croakOfFrogs.toCharArray();
        int res = 0;
        for(int i = 0;i < chars.length;i++){
            if(chars[i] == 'c'){
                if(k > 0){k--;}else{res++;}
                c++;
            }else if(chars[i] == 'r'){
                c--;r++;
            }else if(chars[i] == 'o'){
                r--;o++;
            }else if(chars[i] == 'a'){
                o--;a++;
            }else if(chars[i] == 'k'){
                a--;k++;
            }
            if(c < 0 || r < 0 || o < 0 || a < 0){
                break;
            }
        }
        if(c != 0 || r != 0 || o != 0 || a != 0){
            return -1;
        }
        return res;
    }

总结：

勤思考。

结语

不管怎么样好好加油。

leetcode 1419 Minimum Number of Frogs Croaking

前言

正文