有关做内购的网站,科学规划网页的做法是(),如何搭建购物平台,工具站seo博客主页#xff1a;誓则盟约系列专栏#xff1a;IT竞赛 专栏关注博主#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出#xff0c;及时修改感谢大家点赞#x1f44d;收藏⭐评论✍ 试题F:括号与字母
【问题描述】 给定一个仅包含小写字母和括号的字符串 S …博客主页誓则盟约系列专栏IT竞赛 专栏关注博主后期持续更新系列文章如果有错误感谢请大家批评指出及时修改感谢大家点赞收藏⭐评论✍ 试题F:括号与字母
【问题描述】 给定一个仅包含小写字母和括号的字符串 S 保证括号可以两两匹配。 给出 Q 组询问每组询问给出一个小写字母 ci 和一个数 xi 询问 S 中有 多少对匹配的括号之间有不少于 xi 个 ci 。
【输入格式】 输入的第一行包含一个字符串 S 。 第二行包含一个整数 Q 。 接下来 Q 行每行包含一个小写字母 ci 和一个整数 xi 表示一组询问用 一个空格分隔。
【输出格式】 输出 Q 行每行包含一个整数依次表示每个询问的答案。
【样例输入】
((a)()((b)((c))))
3
a 2
b 1
c 1
【样例输出】
0
3
4
【评测用例规模与约定】 对于 40% 的评测用例|S |, Q ≤ 5000 对于 70% 的评测用例|S | ≤ 100000 对于所有评测用例1 ≤ |S | ≤ 106 1 ≤ Q ≤ 100000 0 ≤ xi 106 。其中 |S | 表示 S 的长度。 分析问题 仔细读题保证给的s中括号都两两匹配那么这道题就相当于是在考察入栈和出栈的问题了这里我们需要定义一个符号栈和一个字母栈。
符号栈专门用来存储左括号遇见左括号则入栈遇见右括号则栈顶的左括号出栈。并且对加入的左括号所包含的字母个数做标记记录出栈前的左括号和右括号之间有几个字母最后可以通过字符串切割来找到这个括号内的字母。字母栈遇见字母则入栈不需要出栈。用于储存字母。 代码实现
sstr(input()) # 输入s
s0abcdefghijklmnopqrstuvwxyz # 一会判断字母要用
qint(input()) # 输入询问次数q
for i in range(q): # q次循环每次询问都有一个输出值s1,b1map(str,input().split()) # 输入要询问的字母和被包括的个数bint(b1) # 转次数为int型vs.count(s1) if vb:print(0) # 此时总个数都小于要询问的个数b一定没有符合题意的 返回0else:re0 # 记录个数stick_1[] # 符号栈stick_2[] # 字母栈for j in s: # 遍历sif j(: #遇见左括号则入栈stick_1.append([j,0]) # 后面的0 用于标记这个左括号与对应的右括号之间有几个字母elif j in s0: # 如果是字母则入字母栈stick_2.append(j)for w in range(len(stick_1)): stick_1[w][-1]1 # 对于所有的左括号对应的标记值都加1说明他们与对应的右括号之间多了一个字母else: # 否则则是右括号k_1,ststick_1.pop() # 遇见右括号则从符号栈出栈一个左括号if st0: continue # 说明左括号右括号之间没有元素直接跳vestick_2[-1:-st-1:-1] # 否则说明之间有元素则找到这些元素if ve.count(s1)b:# 判断ve中要查询的字母个数是否合题意re1 # 标记的个数1print(re) # 对于每次询问都返回 res 总结
以下是对这段代码的详细解释
s str(input())获取用户输入的字符串 s。s0 abcdefghijklmnopqrstuvwxyz定义了所有小写字母的字符串用于后续判断字母。q int(input())获取询问的次数。然后进入 q 次循环 s1, b1 map(str, input().split())分别获取要询问的字母和期望的包含个数将 b1 转换为整数类型。v s.count(s1)计算字符串 s 中该字母出现的总次数。如果总次数小于期望个数直接输出 0。否则进行复杂的处理 re 0 用于记录符合条件的个数。stick_1 是符号栈stick_2 是字母栈。遍历字符串 s 遇到左括号将其及初始标记值 0 入栈。遇到字母入字母栈并更新符号栈中每个左括号对应的标记值表示它们之间多了一个字母。遇到右括号弹出符号栈中的一个左括号和标记值。如果标记值为 0则直接跳过否则找到左括号和右括号之间的元素判断其中要查询的字母个数是否满足条件如果满足则增加标记个数 re。最后输出每次询问对应的 re。 总的来说这段代码主要是通过栈的操作来处理字符串中括号内的子串并判断其中特定字母的出现次数是否满足要求。
对于这道题的考点和反思如下:
考查内容
对字符串的处理和操作能力包括字符的统计、遍历等。栈这种数据结构的运用通过栈来处理括号内的内容和计数。逻辑思维和问题分析解决能力需要仔细思考如何在复杂的条件下准确判断符合要求的情况。 学会的内容
更加深入地掌握了字符串处理的技巧和方法。熟悉了栈的实际应用场景以及如何通过栈来解决特定问题。提升了面对复杂逻辑问题时设计算法和代码实现的能力。 反思
在处理复杂逻辑时要更加仔细地设计算法和流程避免遗漏特殊情况。对于数据结构的运用要更加灵活根据具体问题选择合适的数据结构来优化解决方案。编写代码时要注意代码的可读性和可维护性以便后续的理解和修改。同时要充分考虑代码的效率和性能。 总之,这道题放在15分的位置并不算是难题主要还是考察对栈的应用熟练程度是否到位。 相关栈的篇章栈的理解与应用 “甲之蜜糖乙之砒霜。” ——《曼陀罗》
