行程长度编码

题意

对大小写不敏感的字母串做行程长度编码，格式为 (字符,次数)。

思路

先 upper() 使大小写相同的字母合并，再用与 p 型编码相同的连续段扫描，按要求拼出括号格式。

代码

cpp

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#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=1;i<=len+1;i++){
        if( s[i] >='a' && s[i] <='z')
            s[i] = s[i] +'A'-'a';
    }
    
    for (i=2;i<=len+1;i++){
        if( s[i] == s[i-1]){
            cnt++;
        }
        else {
            printf("(%c,%d)",s[i-1],cnt);
            cnt = 1;
        }
    }
    return 0;
}

复杂度

总结

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12text = input().strip().upper()
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"({text[index - 1]},{count})")
        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
22
23
24
25#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=1;i<=len+1;i++){
        if( s[i] >='a' && s[i] <='z')
            s[i] = s[i] +'A'-'a';
    }
    
    for (i=2;i<=len+1;i++){
        if( s[i] == s[i-1]){
            cnt++;
        }
        else {
            printf("(%c,%d)",s[i-1],cnt);
            cnt = 1;
        }
    }
    return 0;
}

复杂度

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

总结

先做规范化，再做分段统计，可使“大小写不敏感”不干扰主循环。

目录

题意

思路

代码

复杂度

总结

Python代码

C++代码

复杂度

总结