leetcode：2468. 根据限制分割消息【枚举模拟 + 按位递推】

题目截图

题目分析

• 遍历i作为总的分割数
• cap表示当前能到达的最大长度
• 实际上cap使用的是一个递推
• 没到10**k 有一个变化，cap会减去9…99，因为前面的均多了一位，cap自然要减
• 跃升后，tail_len长度会加2，因为a和b长度均会加1
• 知道cap第一次超过len(meesage)，此时的i为答案
• 注意i从1开始遍历

python

class Solution:
    def splitMessage(self, message: str, limit: int) -> List[str]:
        # 枚举模拟递推题
        # limit：每个分块长度小于等于limit
        # i:分割的个数, cap:当前message的已存个数
        # i < 10 ** 4, 每个长度至少为1，否则再多也完成不了了
        n = len(message)
        i = cap = 0
        while True:
            i += 1
            if i < 10:
                tail_len = 5
            elif i < 100:
                # 第一次跃升减9个cap
                if i == 10: cap -= 9
                tail_len = 7
            elif i < 1000:
                if i == 100: cap -= 99
                tail_len = 9
            else:
                if i == 1000: cap -= 999
                tail_len = 11
            if tail_len >= limit: return [] # gg
            cap += limit - tail_len
            if cap < len(message): continue

            # cap第一次超过其长度，获取答案
            ans, cur = [], 0
            for j in range(1, i + 1):
                tail = f'<{j}/{i}>'
                if j == i: # 末尾
                    ans.append(message[cur:] + tail)
                else:
                    available = limit - len(tail)
                    ans.append(message[cur: cur + available] + tail)
                    cur += available
            return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

java

class Solution {
    public String[] splitMessage(String message, int limit) {
        int n = message.length();
        for (int i = 1, cap = 0, tail_len; ; ++i) {
            if (i < 10) tail_len = 5;
            else if (i < 100) {
                if (i == 10) cap -= 9;
                tail_len = 7;
            } else if (i < 1000) {
                if (i == 100) cap -= 99;
                tail_len = 9;
            } else {
                if (i == 1000) cap -= 999;
                tail_len = 11;
            }
            if (tail_len >= limit) return new String[]{}; // gg
            cap += limit - tail_len;
            if (cap < n) continue;

            // ouput the result
            var ans = new String[i];
            for (int j = 0, cur = 0; j < i; ++j) {
                var tail = "<" + (j + 1) + "/" + i + ">";
                if (j == i - 1) ans[j] = message.substring(cur) + tail;
                else {
                    int available = limit - tail.length();
                    ans[j] = message.substring(cur, cur + available) + tail;
                    cur += available;
                }
            }
            return ans;
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

总结

• 按位递推使得on变成o1
• 看来找好规律还是很重要的