字符串p型编码

题意

对数字串做 p 型编码：每段连续相同字符输出“重复次数 + 字符”。

思路

维护当前连续段的 count。扫描到不同字符或字符串末尾时，输出上一段，再将计数重置为 $1$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#include <cstdio>
#include <cstring>

char s[1005];
int main(){
    scanf("%s",s+1);
    int cnt = 1;
    int len = strlen(s+1);
    int i;
    for (i=2;i<=len+1;i++){
        if( s[i] == s[i-1]){
            cnt++;
        }
        else {
            printf("%d",cnt);
            printf("%c",s[i-1]);
            cnt = 1;
        }
    }
    return 0;
}

复杂度

总结

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12text = input().strip()
parts = []
count = 1

for index in range(1, len(text) + 1):
    if index < len(text) and text[index] == text[index - 1]:
        count += 1
    else:
        parts.append(f"{count}{text[index - 1]}")
        count = 1

print("".join(parts))

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#include <cstdio>
#include <cstring>

char s[1005];
int main(){
    scanf("%s",s+1);
    int cnt = 1;
    int len = strlen(s+1);
    int i;
    for (i=2;i<=len+1;i++){
        if( s[i] == s[i-1]){
            cnt++;
        }
        else {
            printf("%d",cnt);
            printf("%c",s[i-1]);
            cnt = 1;
        }
    }
    return 0;
}

复杂度

时间复杂度为 $O(n)$ ，输出空间为 $O(n)$ 。

总结

处理连续段时，把“到达末尾”与“遇到不同字符”统一为一段结束条件。

目录

题意

思路

代码

复杂度

总结

Python代码

C++代码

复杂度

总结