数青蛙
难度:
标签:
题目描述
代码结果
运行时间: 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'时,它们前一个字符的计数器必须大于当前字符的计数器,这个逻辑是如何在代码中体现的?
▷🦆
在代码中如果某个字符顺序错误或无法处理,直接返回-1,这是否意味着整个字符串在此之前的部分不再有效?
▷🦆
为什么在每次遇到'c'字符时更新ret为c-k的值?这样做的目的是什么?
▷🦆
代码中如何处理字符串中潜在的非'croak'字符,例如意外的'x'或'z'?
▷