leetcode
leetcode 2151 ~ 2200
根据限制分割消息

根据限制分割消息

难度:

标签:

题目描述

代码结果

运行时间: 71 ms, 内存: 18.3 MB


/*
 * 思路:
 * 使用Java Stream API,我们可以利用相同的逻辑来实现分割,但通过流处理来简化部分逻辑。
 * 同样的,我们需要计算每个部分的有效信息长度,并判断其可行性。
 */
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class MessageSplitterStream {
    public static List<String> splitMessage(String message, int limit) {
        int n = message.length();
        return IntStream.rangeClosed(1, n)
            .mapToObj(b -> {
                int suffixLength = ("<" + b + "/" + b + ">").length();
                int maxPartLength = limit - suffixLength;
                int totalValidLength = maxPartLength * b;
                if (totalValidLength >= n) {
                    int[] currentIndex = {0};
                    return IntStream.rangeClosed(1, b)
                        .mapToObj(a -> {
                            int remainingParts = b - a + 1;
                            int remainingChars = n - currentIndex[0];
                            int partLength = Math.min(maxPartLength, remainingChars - remainingParts + 1);
                            String part = message.substring(currentIndex[0], currentIndex[0] + partLength) + "<" + a + "/" + b + ">";
                            currentIndex[0] += partLength;
                            return part;
                        }).collect(Collectors.toList());
                }
                return new ArrayList<String>();
            }).filter(list -> !list.isEmpty()).findFirst().orElse(new ArrayList<>());
    }
}

解释

方法:

此题解尝试通过一系列计算来确定如何有效分割字符串,以使每段的长度等于或小于给定的limit。解法考虑了每个部分结尾处的索引标记所需的额外字符数。不同的索引长度(1位、2位、3位或4位数字)会导致每部分可用于实际消息的字符数不同。题解先通过循环遍历四种情况来确定最少需要的部分数n。然后基于所需部分数n和每个部分的结尾长度,对消息进行分割。根据分割的部分数和每部分结尾所需的字符数,调整每次截取的字符串长度,确保每个部分满足长度要求。如果长度不够分配到每一部分,将返回空数组。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在计算每段可以分割的长度时,需要根据分段结束的数字的位数来减去不同的值?
在给定的解决方案中,每个消息段结束时需要添加一个特定格式的编号(例如'<1>'),这个编号的长度取决于编号数字的位数。因为每个段的总长度(包括文本和编号)不能超过限制`limit`,所以必须从可用于文本的字符数中减去编号的字符数。随着编号位数的增加,可用于文本的字符数相应减少,因此我们需要根据编号的位数调整每段的文本长度。
🦆
在解决方案中,如何确保每次分割后部分的长度加上编号后的标记确实不会超过限制长度?
解决方案通过计算每种位数编号所需的额外字符数,并相应地调整字符串截取的长度来确保。例如,如果编号为一位数,那么除了本身的编号外,还需要额外的字符来形成如'<1>'的格式。算法预先计算出每种情况下的最大编号长度,并在循环中不断调整截取长度,以确保包括编号在内的总长度不超过设定的限制`limit`。
🦆
解决方案中提到如果`limit`小于一定值就直接返回空数组,这些特定的`limit`值是如何确定的?
这些特定的`limit`值是基于分段结束的标记最小可能长度确定的。例如,如果分段结束标记为'<1>',至少需要5个字符。如果`limit`值小于这个最小长度,那么即使是最短的标记也无法满足,因此直接返回空数组。这是为了避免在构造消息段时因空间不足而无法满足要求。
🦆
在代码中,为什么要使用不同的循环来处理不同位数的数字编号?这样做的效率如何?
不同的循环是为了处理随着消息段数增加而可能变化的编号位数。随着序号的增加,编号的位数可能从1位变成2位、3位,甚至更多,这直接影响每段可以包含的文字数量。使用循环可以动态地调整每段的长度,以适应编号长度的变化。这种方法虽然在理论上增加了计算复杂度,但提供了一种灵活处理不同情况的有效方式,尤其是在需要精确控制每段长度时。

相关问题