好的，这是 LeetCode 2468 "根据限制分割消息" 的 C++ 实现。
解题思路
核心是枚举分割的总份数，判断当前份数是否可行，然后构造结果。
关键点：
1. 每部分结尾的 <a/b> 长度取决于 a 和 b 的位数
2. 当 b 的位数变化时（如从 9 到 10），前面所有部分的容量会变化
3. 需要找到最小的可行份数
C++ 实现
class Solution {
public:
vector<string> splitMessage(string message, int limit) {
int n = message.size();
// 枚举分割的总份数 i
for (int i = 1, cap = 0, tailLen; ; i++) {
// 根据 i 的位数计算结尾标签长度
if (i < 10) {
tailLen = 5; // <a/b> 格式，a和b都是1位，共5个字符
} else if (i < 100) {
if (i == 10) cap -= 9; // 位数跃升，前面9个部分的容量减少
tailLen = 7; // b是2位，共7个字符
} else if (i < 1000) {
if (i == 100) cap -= 99;
tailLen = 9;
} else {
if (i == 1000) cap -= 999;
tailLen = 11;
}
// 如果结尾标签长度已经超过 limit，无法分割
if (tailLen >= limit) return {};
// 当前份数下能容纳的字符数
cap += limit - tailLen;
// 如果容量不够，继续增加份数
if (cap < n) continue;
// 容量够了，构造结果
vector<string> ans;
int cur = 0; // 当前在 message 中的位置
for (int j = 1; j <= i; j++) {
string tail = "<" + to_string(j) + "/" + to_string(i) + ">";
if (j == i) {
// 最后一部分，长度可以小于 limit
ans.push_back(message.substr(cur) + tail);
} else {
// 非最后一部分，长度必须等于 limit
int len = limit - tail.size();
ans.push_back(message.substr(cur, len) + tail);
cur += len;
}
}
return ans;
}
}
};
另一种更清晰的实现方式
也可以先确定总份数的位数，再精确计算：
class Solution {
public:
vector<string> splitMessage(string message, int limit) {
int n = message.size();
// 枚举总份数的位数
for (int digits = 1; digits <= 5; digits++) {
// 计算当前位数下能容纳的最大字符数
if (getMaxLength(digits, limit) >= n) {
return split(message, n, digits, limit);
}
}
return {};
}
private:
// 计算总份数为 digits 位时能容纳的最大字符数
long long getMaxLength(int digits, int limit) {
vector<int> count = {0, 9, 90, 900, 9000, 90000};
long long len = 0;
for (int i = 1; i <= digits; i++) {
int left = limit - i - digits - 3; // 每部分可容纳的字符数
if (left > 0) {
len += (long long)left * count[i];
}
}
return len;
}
// 实际分割
vector<string> split(string& message, int n, int digits, int limit) {
vector<string> ans;
int cur = 0;
int part = 1;
while (cur < n) {
string num = to_string(part++);
int len = min(limit - 3 - (int)num.size() - digits, n - cur);
string s = message.substr(cur, len);
s += "<" + num + "/";
ans.push_back(s);
cur += len;
}
// 补上分母
string denominator = to_string(--part);
for (string& s : ans) {
s += denominator + ">";
}
return ans;
}
};
示例验证
示例 1：
message = "this is really a very awesome message", limit = 9
输出：["thi<1/14>", "s i<2/14>", "s r<3/14>", "eal<4/14>",
"ly <5/14>", "a v<6/14>", "ery<7/14>", " aw<8/14>",
"eso<9/14>", "me<10/14>", " m<11/14>", "es<12/14>",
"sa<13/14>", "ge<14/14>"]
示例 2：
message = "short message", limit = 15
输出：["short mess<1/2>", "age<2/2>"]
复杂度分析
- 时间复杂度：O(n)，n 是 message 长度
- 空间复杂度：O(n)，存储结果数组
