leetcode
leetcode 1101 ~ 1150
最长快乐字符串

最长快乐字符串

难度:

标签:

题目描述

代码结果

运行时间: 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,为什么要根据奇偶性来决定列表的形式?
在构造快乐字符串时,一个重要的规则是同一个字符不能连续出现超过两次。当maxm(即a,b,或c中的最大值)是偶数时,可以将s(最大数量的字符)均匀地分布为多个长度为2的子串。如果maxm是奇数,除了偶数次的子串外,还需要额外添加一个长度为1的s,以确保所有字符都能被使用并且尽可能均匀地分布。
🦆
在穿插剩余字母的逻辑中,为什么会有一个条件判断`if len(can) - b - c >= 2`,这个条件是基于什么考虑设立的?
这个条件主要是为了防止在can列表中插入过多其他字符导致某些子串超过两个字符的限制。如果剩余的字符(比如b和c,当s为'a')数量少于can列表的长度减去2,则can列表的长度可能需要调整,以避免在穿插过程中某个子串变得过长。这有助于维持快乐字符串的规则,即避免任何字符连续出现超过两次。
🦆
题解中的while循环用于穿插剩余字母,但是否有可能在某些情况下造成无限循环?
在理想情况下,该while循环不应该造成无限循环,因为循环的条件是穿插剩余的字符,而每次循环都会减少至少一个字符的计数(b或c)。然而,如果循环的实现有逻辑错误或者条件更新不正确(例如忘记减少字符计数),则可能导致无限循环。正确的实现应当确保每个字符都在循环中逐个被减少,直至全部插入完毕。
🦆
穿插字母时,题解采用了模运算`j = (j+1) % len(can)`来确保索引在正确的范围内,这种方法是否总是能保证所有剩余的字母都能均匀分布?
采用模运算确实能保证索引始终在can的有效范围内,防止索引越界。但这种方法并不总是能保证剩余字母完全均匀分布,尤其是当剩余字母的数量与can列表的长度不成比例时。这种情况下,某些子串可能会集中更多的插入字符,尤其是在剩余字符数量较多或can列表较短时。为了尽可能均匀地分布字母,可能还需要考虑其他分布策略或在can列表构建时预先考虑更均匀的分布。

相关问题