luogu-B2126 连续出现的字符

luogu-B2126 连续出现的字符

GESP三级练习,字符串练习(C++三级大纲中6号知识点,字符串),难度★★☆☆☆。

luogu-B2126 连续出现的字符

题目要求

题目描述

给定一个字符串,在字符串中寻找第一个连续出现次数不低于 kk 次的字符。

输入格式

22 行。第 11 行是 kk;第 22 行是仅包含大小写字母的字符串。

输出格式

字符串中第一个连续出现次数不低于 k 次的字符。如果没有符合条件的字符,输出 No

输入输出样例 #1

输入 #1

3
abcccaaab

输出 #1

c

说明/提示

1k10001\leq k\leq1000,字符串长度不超过 10001000


题目分析

解题思路

  1. 读取连续出现次数的阈值k
  2. 读取待检查的字符串str
  3. 遍历字符串中的每个字符:
    • 记录当前字符的连续出现次数count
    • 如果当前字符与前一个字符相同:
      • count加1
    • 否则:
      • 重置count为1
    • 如果count大于等于k:
      • 输出当前字符并结束程序
  4. 如果遍历结束仍未找到符合条件的字符,输出"No"

复杂度分析:

  • 时间复杂度为 O(n)O(n),其中n为字符串长度
  • 空间复杂度为 O(1)O(1),只需要存储计数器和当前字符

{% include custom/custom-post-content-inner.html %}


示例代码

#include <iostream>
#include <string>

int main() {
    // 读取连续出现次数的阈值k
    int k;
    std::cin >> k;
    
    // 读取待检查的字符串
    std::string str;
    std::cin >> str;
    
    // 初始化计数器和当前字符
    int count = 1;  // 当前字符的连续出现次数
    char cur_c = str[0];  // 当前正在检查的字符
    
    // 遍历字符串中的每个字符(从第二个字符开始)
    for (int i = 1; i < str.length(); i++) {
        if (str[i] == cur_c) {
            // 如果当前字符与前一个字符相同,计数器加1
            count++;
        } else {
            // 如果当前字符与前一个字符不同,重置计数器并更新当前字符
            cur_c = str[i];
            count = 1;
        }
        
        // 检查是否找到符合条件的字符
        if (count >= k) {
            // 找到连续出现k次及以上的字符,输出并结束程序
            std::cout << cur_c << std::endl;
            return 0;
        }
    }
    
    // 未找到符合条件的字符,输出"No"
    std::cout << "No";
    return 0;
}

{% include custom/custom-post-content-footer.md %}

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

luogu-”系列题目可在 洛谷题库 在线评测。

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

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
Last updated on