OneCoder Avatar
OneCodercoderli.com · 958 篇博文
三级

C++ 算法考级专栏

真题分析、矩阵探测、递归回溯与基础语法

🎨 视觉封面

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

📅 2025-04-17·✍️ OneCoder·计算中...·⏱️ 4 分钟
#GESP#C++#字符串

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 可以用来描述 111111111100000000000 可描述为 11个0,因此它的p型编码串即为 110100200300 可描述为 1个1、2个 0、1个2、2个0、1个3、2个0,因此它的 p 型编码串为 112012201320

输入格式

输入仅一行,包含字符串 str。每一行字符串最多包含 10001000 个数字字符。

输出格式

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

输入输出样例 #1

输入 #1

CONSOLE 1 行
122344111

输出 #1

CONSOLE 1 行
1122132431

题目分析

解题思路

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

复杂度分析:

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

示例代码

C++ 38 行
#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;
}

💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745)Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder (lihongzheshuai)

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

0 条讨论
✨ 支持点击留言直接回复 · Markdown 引用格式
💬 还没有读者留言,快来成为第一个讨论者吧!