leetcode
leetcode 1301 ~ 1350
数青蛙

数青蛙

难度:

标签:

题目描述

代码结果

运行时间: 76 ms, 内存: 16.4 MB


/*
 * The approach using Java Streams would involve the same logic as the regular Java implementation.
 * However, Java Streams are not typically used for this kind of stateful, sequential processing, especially for counting and updating states.
 * Thus, using Java Streams may not be appropriate or efficient for this problem.
 * Below is a conceptual demonstration that mirrors the logic in the standard Java solution without actual stream usage.
 */
import java.util.stream.IntStream;

public class FrogCroakStream {
    public int minNumberOfFrogs(String croakOfFrogs) {
        int[] croakCount = new int[5];
        int frogs = 0, maxFrogs = 0;
        for (char ch : croakOfFrogs.toCharArray()) {
            switch (ch) {
                case 'c':
                    croakCount[0]++;
                    frogs++;
                    maxFrogs = Math.max(maxFrogs, frogs);
                    break;
                case 'r':
                    if (croakCount[0] == 0) return -1;
                    croakCount[0]--;
                    croakCount[1]++;
                    break;
                case 'o':
                    if (croakCount[1] == 0) return -1;
                    croakCount[1]--;
                    croakCount[2]++;
                    break;
                case 'a':
                    if (croakCount[2] == 0) return -1;
                    croakCount[2]--;
                    croakCount[3]++;
                    break;
                case 'k':
                    if (croakCount[3] == 0) return -1;
                    croakCount[3]--;
                    croakCount[4]++;
                    frogs--;
                    break;
                default:
                    return -1;
            }
        }
        if (IntStream.of(croakCount).sum() != croakCount[4]) return -1;
        return maxFrogs;
    }
}

解释

方法:

该题解通过模拟青蛙发出的声音的顺序,使用五个变量c, r, o, a, k来跟踪每个字符'c', 'r', 'o', 'a', 'k'出现的次数。变量ret用于记录同时叫声所需的最大青蛙数量。遍历字符串中的每一个字符,更新相应字符的计数器,确保字符的顺序符合'croak'的顺序。如果当前字符为'c', 则增加c的计数,同时更新ret为当前活跃的青蛙数量,即c-k的值。对于'r', 'o', 'a', 'k'的处理,确保前一个字符的计数器大于当前字符的计数器,这样才能保证字符的顺序。最后,如果所有字符的计数相等,表示所有'croak'都是完整的,则返回ret;否则,如果有不匹配的,返回-1。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
如何确保在处理字符'r', 'o', 'a', 'k'时,它们前一个字符的计数器必须大于当前字符的计数器,这个逻辑是如何在代码中体现的?
在处理字符'r', 'o', 'a', 'k'时,代码分别检查了前一个字符的计数器是否大于当前字符的计数器。例如,当i为'r'时,代码中有一个条件判断`c > r`,只有当c(即前一个字符'c'的计数器)大于r(即当前字符'r'的计数器)时,才会将r的计数器增加。这样的逻辑确保了字符的顺序符合'croak'这一顺序,因为每个'croak'必须以'c'开始,依次经过'r', 'o', 'a'到'k'。
🦆
在代码中如果某个字符顺序错误或无法处理,直接返回-1,这是否意味着整个字符串在此之前的部分不再有效?
是的,如果在处理字符串时遇到顺序错误或遇到了非'croak'字符,代码会直接返回-1。这意味着一旦检测到错误,不仅当前字符处理失败,整个字符串都被认为是无效的,因为它不满足题目要求的每个'croak'声音完整且正确的顺序。因此,无论之前的字符是否正确,整个字符串都不再有效。
🦆
为什么在每次遇到'c'字符时更新ret为c-k的值?这样做的目的是什么?
在每次遇到'c'字符时更新ret为c-k的值主要是为了跟踪同时发出'croak'声音的最大青蛙数量。在这里,c代表开始一个新的'croak'的次数,而k代表完成'croak'声音的次数。c-k因此表示当前正在发出'croak'声音但尚未完成的青蛙数量。通过更新ret为这个值的最大值,我们能确保ret始终保持为同时发出'croak'声音的最大青蛙数量,这对解决问题至关重要。
🦆
代码中如何处理字符串中潜在的非'croak'字符,例如意外的'x'或'z'?
代码中通过在处理每个字符时设置条件判断来处理潜在的非'croak'字符。如果遇到的字符不是'c', 'r', 'o', 'a', 或 'k',或者它的顺序不正确(即前一个字符的计数器不大于当前字符的计数器),则代码将返回-1。这样的设计直接使任何包含非'croak'字符的字符串或顺序错误的情况被识别为无效,终止进一步的处理。

相关问题