蓝桥杯-正则问题-python

简介: 蓝桥杯-正则问题-python

考虑一种简单的正则表达式:

只由 x ( ) | 组成的正则表达式。

小明想求出这个正则表达式能接受的最长字符串的长度。  

例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是: xxxxxx,长度是6。

输入

----

一个由x()|组成的正则表达式。输入长度不超过100,保证合法。  

输出

----

这个正则表达式能接受的最长字符串的长度。  

例如,

输入:

((xx|xxx)x|(x|xx))xx  

程序应该输出:

6  

资源约定:

峰值内存消耗(含虚拟机) < 256M

CPU消耗  < 1000ms


思路:


这道题使用深度搜索的方法,输入字符串,从前往后读读字符串的过程中,如果读到‘(’,则进入递归。递归是为了计算一个’()‘内的值。

读字符串的过程中,如果遇到‘x'就让temp++,位置++;如果遇到’|‘,则用ans保存temp的值,tenp=0,从而让temp保存’|‘之后的值,位置++;读到’)‘时,位置++,退出循环。最后进行一次比较,比较ans保存的|前面的值的大小和|后面temp的值,返回最大值。

递归回退,解决完小问题之后解决大问题,最终返回最大值。


代码:


1. s = input()
2. pos, length = 0, len(s)
3. def dfs():
4. global pos, length
5.     ans, temp = 0, 0
6.     while pos<length:   # length达不到 所以pos会遍历所有索引的位置
7. if s[pos] == '(': #遇到(,进入下一位置,进入递归,将大问题划分为小问题
8.             pos += 1
9.             temp += dfs()
10.         elif s[pos] == 'x':#遇到x
11.             pos += 1
12.             temp += 1
13.         elif s[pos] == '|':
14.             pos += 1
15.             ans = max(ans, temp)
16.             temp = 0
17.         elif s[pos] == ')':
18.             pos += 1
19.             break
20.     # xx|xxxxx
21.     ans = max(ans, temp)
22. return ans
23. ans = dfs()
24. print(ans)
目录
相关文章
|
2月前
|
Python
蓝桥杯练习题(一):Python组之入门训练题
这篇文章是关于蓝桥杯Python组的入门训练题,包括Fibonacci数列、圆的面积、序列求和和A+B问题的具体代码实现和样例输出。
138 0
|
2月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
93 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
2月前
|
人工智能 Python
蓝桥杯练习题(四):Python组之历届试题三十题
关于蓝桥杯Python组历届试题的三十个练习题的总结,包括题目描述、输入输出格式、样例输入输出以及部分题目的解题思路和代码实现。
41 0
蓝桥杯练习题(四):Python组之历届试题三十题
|
2月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(二):Python组之基础练习三十题
蓝桥杯Python编程练习题的集合,包含了三十个不同难度的编程题目,覆盖了基础语法、数据结构和算法等领域。
42 0
|
7月前
|
Python
python小案例-re正则
python小案例-re正则
|
7月前
|
机器学习/深度学习 算法 算法框架/工具
【Python机器学习专栏】深度学习中的正则化与优化技术
【4月更文挑战第30天】本文探讨了深度学习中的正则化和优化技术,以提升模型的泛化能力和训练效率。正则化包括L1和L2正则化以及Dropout,防止过拟合。优化技术涵盖梯度下降法、动量法和Adam优化器,加速模型收敛。Python示例展示了如何在Keras中应用这些技术,如L2正则化、Dropout及Adam优化器。
123 0
|
7月前
|
索引 Python 容器
【备战蓝桥杯】探索Python内置标准库collections的使用
【备战蓝桥杯】探索Python内置标准库collections的使用
97 1
|
7月前
|
开发者 Python
【备战蓝桥杯】如何使用Python 内置模块datetime去计算我与CSDN相遇的天数
【备战蓝桥杯】如何使用Python 内置模块datetime去计算我与CSDN相遇的天数
72 1
|
7月前
|
算法 测试技术 编译器
蓝桥杯-02-python组考点与14届真题
蓝桥杯-02-python组考点与14届真题
|
7月前
|
Python
第十三届蓝桥杯B组python(试题A:排列字母)
第十三届蓝桥杯B组python(试题A:排列字母)
67 0