这个题有多种思路。
1. 新建一个int型数组ducks，用以数组的元素存储所有鸭子叫的下一个字符标号（设“c”的标号为0、“r”的编号为1、“o”的编号为2、“a”的编号为3、“k”的编号为4）。遍历字符串中的每一个字符，如果
- 当前字符的编号与ducks中某个元素的编号相同，则意味着这只鸭子可以叫，并把这只鸭子的当前编号加1；
- 如果字符为“a”，则并且在ducks中找不到编号为0的鸭子，则在ducks中新增一个鸭子，并把编号记为1（即它的下一个字符是“r”）；
- 如果字符编号为其他值，并在ducks中不存在，则字符串不合规，返回-1。
如果这只鸭子叫完了，则把这只鸭子的编号置为0。
最后ducks的个数就是鸭子的个数。
Java代码的实现如下：
public int getDuckLeastCount(String croakStr) {
int length = croakStr.length();
// 字符串必须是5的倍数
if (length % 5 != 0) {
return -1;
}
char[] CROAK_CHAR_ARRAY = { 'c', 'r', 'o', 'a', 'k' };
List<Integer> ducks = new ArrayList<Integer>();
char[] croakInputChars = croakStr.toCharArray();
for (int i = 0; i < croakStr.length(); i++) {
char currentChar = croakInputChars[i];
boolean found = false;
for (int j = 0; j < ducks.size(); j++) {
int nextDuckIndex = ducks.get(j);
if (currentChar == CROAK_CHAR_ARRAY[nextDuckIndex]) {
ducks.set(j, (nextDuckIndex + 1) % CROAK_CHAR_ARRAY.length);
found = true;
break;
}
}
// 如果没找到，且是“c”开头，这意味着要新增一只鸭子
if ((!found) && (currentChar == CROAK_CHAR_ARRAY[0])) {
ducks.add(1);
continue;
}
if (!found) {
return -1;
}
}
return ducks.size();
}
因为存在一个双重循环，这种算法的时间复杂度是O(n)，空间复杂度也是O(n)。
2. 遍历字符串，统计各个字母的个数，如果字符合规，那么在遍历任何一个字符的时候，一定满足：
-
- c的个数大于或等于r的个数；
- r的个数大于或等于o的个数；
- o的个数大于或等于a的个数；
- a的个数大于或等于k的个数；
- 等到遍历完时，c、r、o、a、k等字符的个数相等。
以上是字符合规的判定。在实际统计鸭子个数时，c的字母个数是这几个字母数中最大的，它的个数代表着鸭子的个数。而当遇到字母k时，代表着一个鸭子叫完了，后面如果碰到c，它又可以开始叫。那么在这个过程中，c的个数最大值，就是最后统计的鸭子个数。当遍历完所有的字符后，c、r、o、a、k的个数为0。
Java代码的实现如下：
public int getDuckLeastCount2(String croakStr) {
int length = croakStr.length();
// 字符串必须是5的倍数
if (length % 5 != 0) {
return -1;
}
char[] CROAK_CHAR_ARRAY = { 'c', 'r', 'o', 'a', 'k' };
int counts[] = new int[CROAK_CHAR_ARRAY.length];
Map<Character, Integer> matchMap = new HashMap<>();
for (int i = 0; i < CROAK_CHAR_ARRAY.length; i++) {
counts[i] = 0;
matchMap.put(CROAK_CHAR_ARRAY[i], i);
}
int duckCnt = 0;
char[] croakInputChars = croakStr.toCharArray();
for (int i = 0; i < croakInputChars.length; i++) {
int index = matchMap.get(croakInputChars[i]);
if (index == -1) {
return -1;
}
counts[index] += 1;
// 如果当前字符个数比前一个字符个数多，则不合规。
// 只需要和前一个值判断，则一定能保证counts数组中的值是从大到小的
if (index > 0 && counts[index - 1] < counts[index]) {
return -1;
}
if (index == 0 && counts[0] > duckCnt) {
duckCnt = counts[0];
}
if (index == CROAK_CHAR_ARRAY.length - 1) {
for (int j = 0; j < counts.length; j++) {
counts[j] -= 1;
}
}
}
for (int i = 0; i < counts.length; i++) {
if (counts[i] != 0) {
return -1;
}
}
return duckCnt;
}
这种算法的时间复杂度和空间复杂度都是O(n) 。
请你留言