【GESP】C++三级练习 luogu-B2123 字符串 p 型编码

GESP三级练习，字符串练习（C++三级大纲中6号知识点，字符串），难度★★☆☆☆。

luogu-B2123 字符串 p 型编码

题目要求

题目描述

给定一个完全由数字字符（’0’,’1’,’2’,…,’9’）构成的字符串 str ，请写出 str 的 p 型编码串。例如：字符串 122344111 可被描述为 1个1、2个2、1个3、2个4、3个1 ，因此我们说122344111 的 p 型编码串为 1122132431 ；类似的道理，编码串 101 可以用来描述 1111111111 ；00000000000 可描述为 11个0，因此它的p型编码串即为 110 ；100200300 可描述为 1个1、2个 0、1个2、2个0、1个3、2个0，因此它的 p 型编码串为 112012201320。

输入格式

输入仅一行，包含字符串 str。每一行字符串最多包含 $1000$ 个数字字符。

输出格式

输出该字符串对应的 $p$ 型编码串。

输入输出样例 #1

输入 #1

122344111

输出 #1

1122132431

---

题目分析

解题思路

1. 读取一个由数字字符组成的字符串
2. 遍历字符串中的每个字符：
   • 统计当前数字字符连续出现的次数
   • 当遇到不同的数字字符时：
     • 将前一个数字的出现次数和数字本身加入结果
     • 重置计数器
     • 更新当前正在统计的数字
3. 处理最后一组数字：
   • 将最后一个数字的出现次数和数字本身加入结果

复杂度分析：

• 时间复杂度为 $O(n)$，其中n为输入字符串的长度
• 空间复杂度为 $O(n)$，其中n为输入字符串的长度（最坏情况下，每个数字都不相同）

---

示例代码

#include <iostream>
#include <string>

int main() {
    // 用于存储输入的字符串
    std::string str;
    std::cin >> str;
    
    // 用于存储最终的p型编码结果
    std::string result;
    
    // 初始化计数器和当前字符
    int cur_count = 1;  // 记录当前字符的连续出现次数
    char cur_char = str[0];  // 记录当前正在统计的字符
    
    // 从第二个字符开始遍历字符串
    for (int i = 1; i < str.length(); i++) {
        if (str[i] == cur_char) {
            // 如果当前字符与前一个字符相同，计数器加1
            cur_count++;
        } else {
            // 如果遇到不同的字符：
            // 1. 将当前统计结果添加到结果字符串
            // 2. 重置计数器
            // 3. 更新当前字符
            result += std::to_string(cur_count) + cur_char;
            cur_count = 1;
            cur_char = str[i];
        }
    }
    
    // 处理最后一组字符
    result += std::to_string(cur_count) + cur_char;
    
    // 输出p型编码结果
    std::cout << result;
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。