Skip to content

Latest commit

 

History

History
198 lines (159 loc) · 6.96 KB

README.md

File metadata and controls

198 lines (159 loc) · 6.96 KB
Raw
comments difficulty edit_url rating source tags
true
困难
2381
第 91 场双周赛 Q4
字符串
二分查找

2468. 根据限制分割消息

English Version

题目描述

给你一个字符串 message 和一个正整数 limit 。

你需要根据 limit 将 message 分割 成一个或多个 部分 。每个部分的结尾都是 "<a/b>" ，其中 "b" 用分割出来的总数 替换， "a" 用当前部分所在的编号 替换 ，编号从 1 到 b 依次编号。除此以外，除了最后一部分长度 小于等于 limit 以外，其他每一部分（包括结尾部分）的长度都应该 等于 limit 。

你需要确保分割后的结果数组，删掉每部分的结尾并 按顺序 连起来后，能够得到 message 。同时，结果数组越短越好。

请你返回 message  分割后得到的结果数组。如果无法按要求分割 message ，返回一个空数组。

 

示例 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>"]
解释：
前面 9 个部分分别从 message 中得到 3 个字符。
接下来的 5 个部分分别从 message 中得到 2 个字符。
这个例子中，包含最后一个部分在内，每个部分的长度都为 9 。
可以证明没有办法分割成少于 14 个部分。

示例 2：

输入：message = "short message", limit = 15
输出：["short mess<1/2>","age<2/2>"]
解释：
在给定限制下，字符串可以分成两个部分：
- 第一个部分包含 10 个字符，长度为 15 。
- 第二个部分包含 3 个字符，长度为 8 。

 

提示：

  • 1 <= message.length <= 104
  • message 只包含小写英文字母和 ' ' 。
  • 1 <= limit <= 104

解法

方法一：枚举分段数量 + 模拟

我们设字符串 message 的长度为 $n$，分段数量为 $k$。

根据题意，如果 $k \gt n$，表示我们可以将字符串划分成超过 $n$ 段，由于字符串长度仅为 $n$，若划分成超过 $n$ 段必然导致有部分段的长度为 $0$，可以删去。因此，我们只需要将 $k$ 的取值范围限制在 $[1,.. n]$ 即可。

从小到大枚举分段数量 $k$，记所有分段中 $a$ 段的长度为 $sa$，所有分段中 $b$ 段的长度为 $sb$，所有分段中符号（包括尖括号和斜杠）的长度为 $sc$。

那么 $sa$ 的值为 ${\textstyle \sum_{j=1}^{k}} len(s_j)$，可以直接通过前缀和求出；而 $sb$ 的值为 $len(str(k)) \times k$；另外 $sc$ 的值为 $3 \times k$。

因此，所有分段剩余可填充的字符数为 $limit\times k - (sa + sb + sc)$，如果该值大于等于 $n$ 则说明可以将字符串划分成 $k$ 段，直接构造答案返回即可。

时间复杂度 $O(n\times \log n)$，其中 $n$ 为字符串 message 的长度。忽略答案的空间消耗，空间复杂度 $O(1)$。

Python3

class Solution:
    def splitMessage(self, message: str, limit: int) -> List[str]:
        n = len(message)
        sa = 0
        for k in range(1, n + 1):
            sa += len(str(k))
            sb = len(str(k)) * k
            sc = 3 * k
            if limit * k - (sa + sb + sc) >= n:
                ans = []
                i = 0
                for j in range(1, k + 1):
                    tail = f'<{j}/{k}>'
                    t = message[i : i + limit - len(tail)] + tail
                    ans.append(t)
                    i += limit - len(tail)
                return ans
        return []

Java

class Solution {
    public String[] splitMessage(String message, int limit) {
        int n = message.length();
        int sa = 0;
        String[] ans = new String[0];
        for (int k = 1; k <= n; ++k) {
            int lk = (k + "").length();
            sa += lk;
            int sb = lk * k;
            int sc = 3 * k;
            if (limit * k - (sa + sb + sc) >= n) {
                int i = 0;
                ans = new String[k];
                for (int j = 1; j <= k; ++j) {
                    String tail = String.format("<%d/%d>", j, k);
                    String t = message.substring(i, Math.min(n, i + limit - tail.length())) + tail;
                    ans[j - 1] = t;
                    i += limit - tail.length();
                }
                break;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<string> splitMessage(string message, int limit) {
        int n = message.size();
        int sa = 0;
        vector<string> ans;
        for (int k = 1; k <= n; ++k) {
            int lk = to_string(k).size();
            sa += lk;
            int sb = lk * k;
            int sc = 3 * k;
            if (k * limit - (sa + sb + sc) >= n) {
                int i = 0;
                for (int j = 1; j <= k; ++j) {
                    string tail = "<" + to_string(j) + "/" + to_string(k) + ">";
                    string t = message.substr(i, limit - tail.size()) + tail;
                    ans.emplace_back(t);
                    i += limit - tail.size();
                }
                break;
            }
        }
        return ans;
    }
};

Go

func splitMessage(message string, limit int) (ans []string) {
	n := len(message)
	sa := 0
	for k := 1; k <= n; k++ {
		lk := len(strconv.Itoa(k))
		sa += lk
		sb := lk * k
		sc := 3 * k
		if limit*k-(sa+sb+sc) >= n {
			i := 0
			for j := 1; j <= k; j++ {
				tail := "<" + strconv.Itoa(j) + "/" + strconv.Itoa(k) + ">"
				t := message[i:min(i+limit-len(tail), n)] + tail
				ans = append(ans, t)
				i += limit - len(tail)
			}
			break
		}
	}
	return
}