统计连续字符-2022年全国青少年信息素养大赛Python国赛第7题

全国青少年信息素养大赛(原全国青少年电子信息智能创新大赛)是“世界机器人大会青少年机器人设计与信息素养大赛”赛事之一,由中国电子学会主办,包含很多赛项,大赛自2013年举办,已连续成功举办八届,已正式入围“2022-2025学年面向中小学生的全国性竞赛活动名单”。

大赛旨在激发广大青少年的科学兴趣和想象力,培养钻研探究、创新创造的科学精神和实践能力,促进青少年科技创新活动的广泛开展,发现和培养一批具有科研潜质和创新精神的青少年科技创新后备人才。

大赛主要竞赛类别包括电子科技、智能机器人、软件编程三类,全国青少年Python编程挑战赛就属于其中的软件编程类。

一.赛事说明

2021-2022年(第8届)Python挑战赛赛程分为初赛、复赛和总决赛三个阶段。初赛是资格赛,复赛是地方选拔赛,总决赛是全国各地选拔的精英汇聚在一起进行PK。2021-2022年全国青少年Python编程挑战全国总决赛于2022年8月27日正式举行。一共是10道编程题,每道题100分,满分1000分,考试时间是120分钟。

10道编程题分别如下:

  • 分苹果
  • 韩信点兵
  • 借书问题
  • 四位数密码
  • 邮票面值
  • 组合取球
  • 统计连续字符
  • n的n次方
  • 海盗搜身
  • 父与子

超平老师将分10讲对每道题进行详细的解读和剖析,今天要解读的是第7题,统计连续字符。

二.题目描述

题目背景:

依次输入一个字符串s与一个数字n,寻找字符串中所有连续出现n次的字符,统计符合要求的字符数量并输出。

例如输入abbcccdddd,输入2,字符串中连续出现2次的字符包括b、c、d这3种。

输入描述:

第一行一个字符串(保证有连续的n个字符)

第二行一个数字n

输出描述:

符合要求的字符数量

样例输入:

abbcccdddd

2

样例输出:

3

注意:

input()内不添加任何参数

只有完全正确才可提交,若无法点击提交说明答题存在错误,可及时进行检查并修改

三.思路分析

本题的思路非常直观,就是先固定好第一个字符的位置,然后从下一个字符开始逐个比较,直到碰到不相等的情况,就说明找到一个连续字符串了。接着把当前字符作为新的第一个字符,重复上述过程,直到整个字符串遍历完毕。

在这个过程中,需要使用两个变量来记录每个字符串的起点和终点,在算法编程中,通常称之为指针。我们以字符串”abbcccdddd“为例,说明上述过程。

首先从第一个字母a开始,如图:

其中,蓝色指针i表示起点,红色指针j表终点,所以对于字母a来说,只有一个是连续的,代码层面,直接使用切片操作s[i:j]就可以了。

接下来,将蓝色指针i移到j的位置,然后逐个比较,直到碰到不等于b的情况,如图:

同理,直接使用切片操作s[i:j]就可以得到连续的字符串”bb”。

继续将蓝色指针i移到j的位置,逐个比较,直到碰到不等于c的情况,如图:

仍然使用切片操作s[i:j]取出连续字符串”ccc“。

最后,将将蓝色指针i移到j的位置,逐个比较,直到碰到不等于d的情况,或者到字符串结束,如图:

注意,红色指针j已经指向最后一个位置了,所以这一次结束的条件不再是不等于d了,而是字符串结束了。

每获取到一个连续字符串,就将其保存到一个列表中,如下:

['a','bb','ccc','dddd']

然后,就可以遍历列表,根据n的值,将字符串长度大于等于n的统计出来即可。

接下来,我们进入具体的编程实现环节。

四.编程实现

根据上面的思路分析,我们编写代码如下:

# 获取字符串
s = input()
# 获取数字n
n = int(input())

res = []
i = 0
while i < len(s): 
    j = i + 1
    # 判断前后连个字符是否相等
    while j < len(s) and s[i] == s[j]:
        j += 1
    # 将连续字符取出来,存入到列表中  
    res.append(s[i:j])
    i = j

# 对结果进行过滤
res = [r for r in res if len(r) >= n]

# 输出次数
print(len(res))

简单说明三点:

1). 代码中的变量i表示蓝色指针i,变量j表示红色指针j;

2). 每找到一个连续字符串,就立刻将指针i移到指针j处,第15行代码 i = j 的作用就在于此;

3). 第18行代码运用了列表推导式,对结果进行了过滤,将满足条件的字符串保存到列表res中。

五.总结与思考

本题难度中等,考查的知识点主要包括:

  • 输入输出函数;
  • 循环嵌套语句;
  • 列表操作;
  • 指针的概念及实现方式;

解决本题的关键在于对双指针的理解,尤其是指针移动的过程,建议使用画图的方式来梳理思路。

超平老师给你留一道思考题,在上面的代码中,我们使用了两个while来实现循环嵌套,能使用for循环来替代吗,为什么呢?

给TA赞助
共{{data.count}}人
人已赞助
综合资讯

组合取球-2022年全国青少年信息素养大赛Python国赛第6题

2023-7-13 8:21:37

综合资讯

n的n次方-2022年全国青少年信息素养大赛Python国赛第8题

2023-7-14 8:09:52

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索