解题思路

p型编码就是把连续相同的数字压缩成"个数+数字"的形式。比如 122344111 可以描述成：1个1、2个2、1个3、2个4、3个1，连写起来就是 1122132431。

做法：用两个下标 i 和 j 配合扫描：

1. i 指向当前要处理的那一段的开头。
2. 让 j 从 i 开始一直往前走，直到遇到和 s[i] 不同的字符为止。那么 s[i] 到 s[j-1] 就是连续相同的一段，个数是 j - i。
3. 输出 j - i（个数）和 s[i]（数字）。
4. 把 i 跳到 j，继续处理下一段，直到字符串结束。

举例：122344111

• 1个1 → 11
• 2个2 → 22
• 1个3 → 13
• 2个4 → 24
• 3个1 → 31

合起来：1122132431。

参考代码

// 字符串p型编码：把连续相同的数字压缩为“连续个数+数字”
#include <iostream>
using namespace std;
int main() {
    string s;            // 数字字符串
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; ) {
        int j = i;
        while (j < n && s[j] == s[i]) j++; // 找到与s[i]相同的连续段
        cout << (j - i) << s[i];           // 输出个数和该数字
        i = j;                             // 跳到下一个不同数字
    }
    cout << endl;
    return 0;
}

复杂度分析

数字串最长 1000 个字符。i 和 j 都只会往前进，每个字符只被处理一次，时间复杂度 O(n)，空间 O(n)（保存字符串）。