最长快乐字符串
难度:
标签:
题目描述
代码结果
运行时间: 20 ms, 内存: 16.1 MB
/*
* 思路:
* 使用Java Stream API来创建快乐字符串
* 由于Stream不直接支持对复杂逻辑的动态决策,我们这里提供的实现会比较传统Java版本更加清晰
*/
import java.util.Arrays;
import java.util.stream.Collectors;
public class SolutionStream {
public String longestDiverseString(int a, int b, int c) {
StringBuilder result = new StringBuilder();
int[] count = {a, b, c};
char[] chars = {'a', 'b', 'c'};
while (true) {
int maxIndex = getMaxCountIndex(count);
if (count[maxIndex] == 0) {
break;
}
int length = result.length();
if (length >= 2 && result.charAt(length - 1) == chars[maxIndex] && result.charAt(length - 2) == chars[maxIndex]) {
int secondMaxIndex = getSecondMaxCountIndex(count, maxIndex);
if (count[secondMaxIndex] == 0) {
break;
}
result.append(chars[secondMaxIndex]);
count[secondMaxIndex]--;
} else {
result.append(chars[maxIndex]);
count[maxIndex]--;
}
}
return result.toString();
}
private int getMaxCountIndex(int[] count) {
return Arrays.stream(new int[]{0, 1, 2}).boxed()
.max((i, j) -> count[i] - count[j])
.orElse(0);
}
private int getSecondMaxCountIndex(int[] count, int excludeIndex) {
return Arrays.stream(new int[]{0, 1, 2}).boxed()
.filter(i -> i != excludeIndex)
.max((i, j) -> count[i] - count[j])
.orElse(-1);
}
}
解释
方法:
该题解的思路是先找出 a, b, c 中的最大值 maxm,根据 maxm 的值确定主要构成字符串的字母 s。然后根据 maxm 的奇偶性,构造出由 s 组成的子串列表 can,使得每个子串最多包含两个连续的 s。接下来,根据 s 的值,分三种情况在 can 的子串中穿插剩余的字母,每次穿插一个字母,并移动到下一个子串,直到剩余字母用尽。最后将 can 中的所有子串拼接起来即可得到最长的快乐字符串。
时间复杂度:
O(a + b + c)
空间复杂度:
O(a + b + c)
代码细节讲解
🦆
题解中提到根据maxm的奇偶性构造子串列表can,为什么要根据奇偶性来决定列表的形式?
▷🦆
在穿插剩余字母的逻辑中,为什么会有一个条件判断`if len(can) - b - c >= 2`,这个条件是基于什么考虑设立的?
▷🦆
题解中的while循环用于穿插剩余字母,但是否有可能在某些情况下造成无限循环?
▷🦆
穿插字母时,题解采用了模运算`j = (j+1) % len(can)`来确保索引在正确的范围内,这种方法是否总是能保证所有剩余的字母都能均匀分布?
▷