2025-4-4-python算法题（OD算法题-最长合法表达式）

几个常用库函数的使用

import functools
import sys
from collections import Counter, defaultdict
import copy
from itertools import permutations
import re
import math
import sys

1. functools 模块

functools 中的 reduce 函数可以对可迭代对象进行累积操作，lru_cache 可以缓存函数的返回值以避免重复计算。

import functools# 使用 reduce 计算阶乘
numbers = [1, 2, 3, 4, 5]
factorial = functools.reduce(lambda x, y: x * y, numbers)
print(f"5 的阶乘是: {factorial}")# 使用 lru_cache 缓存函数结果
@functools.lru_cache(maxsize=None)
def fibonacci(n):if n < 2:return nreturn fibonacci(n - 1) + fibonacci(n - 2)print(f"斐波那契数列第 10 项是: {fibonacci(10)}")

2. sys 模块

sys 可以获取命令行参数，还能控制程序的退出。

import sys# 获取命令行参数
if len(sys.argv) > 1:print(f"你传入的参数是: {sys.argv[1]}")
else:print("没有传入命令行参数。")# 退出程序
sys.exit(0)

3. collections 模块

• Counter：统计可迭代对象中元素的出现次数。

from collections import Counterwords = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
word_count = Counter(words)
print("单词出现次数统计:", word_count)

• defaultdict：当访问不存在的键时返回默认值。

from collections import defaultdict# 创建一个默认值为 0 的字典
fruit_prices = defaultdict(int)
fruit_prices['apple'] = 1.5
print("苹果的价格是:", fruit_prices['apple'])

4. copy 模块

copy 模块可以进行浅复制和深复制。

import copyoriginal_list = [[1, 2], [3, 4]]
# 浅复制
shallow_copy = copy.copy(original_list)
# 深复制
deep_copy = copy.deepcopy(original_list)# 修改原始列表
original_list[0][0] = 99print("浅复制后的列表:", shallow_copy)
print("深复制后的列表:", deep_copy)

5. itertools 模块

permutations 函数可以生成可迭代对象的所有排列组合。

from itertools import permutationsnumbers = [1, 2, 3]
perms = permutations(numbers)
print("数字 1, 2, 3 的所有排列组合:")
for perm in perms:print(perm)

6. re 模块

re 模块可以用于字符串的匹配和替换。

import retext = "Hello, my email is [e-mail]. Contact me!"
# 查找邮件地址
email_pattern = r'\b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Z|a-z]{2,}\b'
emails = re.findall(email_pattern, text)
print("找到的邮件地址:", emails)# 替换文本中的单词
new_text = re.sub(r'Hello', 'Hi', text)
print("替换后的文本:", new_text)

7. math 模块

math 模块提供了许多数学函数。

import math# 计算平方根
sqrt_result = math.sqrt(25)
print("25 的平方根是:", sqrt_result)# 计算正弦值
sin_result = math.sin(math.radians(30))
print("30 度的正弦值是:", sin_result)

OD算法题-最长合法表达式

  提取字符串中的最长合法简单数学表达式，字符串长度最长的，并计算表达式的值。如果没有，则返回 0 。
  简单数学表达式只能包含以下内容：
  0-9 数字，符号 ±*

说明：
所有数字，计算结果都不超过 long
如果有多个长度一样的，请返回第一个表达式的结果
数学表达式，必须是最长的，合法的
操作符不能连续出现，如 ±-+1 是不合法的

import redef is_valid_expr(expr):# 检查操作符是否连续if re.search(r'[+\-*]{2,}', expr):return False# 表达式必须以数字开头和结尾if not re.match(r'^\d', expr) or not re.search(r'\d$', expr):return Falsereturn Truedef calculate_expr(expr):try:return eval(expr)except:return Nonedef longest_valid_expression(s):max_length = 0max_result = 0n = len(s)for start in range(n):for end in range(start + 1, n + 1):sub_expr = s[start:end]if is_valid_expr(sub_expr):result = calculate_expr(sub_expr)if result is not None and len(sub_expr) > max_length:max_length = len(sub_expr)max_result = resultreturn max_result# 示例测试
s = "a1+2b3*4"
print(longest_valid_expression(s))

1. is_valid_expr 函数

   • 使用 re.search 检查表达式中是否存在连续的操作符（[+\-*]{2,}），如果存在则表达式不合法。
   • 使用 re.match 和 re.search 分别检查表达式是否以数字开头（^\d）和结尾（\d$），不满足则不合法。

2. calculate_expr 函数

   • 利用 eval 函数计算表达式的值，如果计算过程中出现异常（如语法错误等），返回 None。

3. longest_valid_expression 函数

   • 通过两层循环遍历字符串所有可能的子串。
   • 对每个子串，先调用 is_valid_expr 判断是否合法，若合法再用 calculate_expr 计算值。
   • 若计算结果有效且子串长度大于当前记录的最大长度，更新最大长度和结果。

4. 最后通过示例字符串测试函数功能。

学习python的内置函数 eval(expr)

eval(expr) 是 Python 内置函数，功能强大且使用需谨慎。
eval() 函数能将字符串 expr 当成有效的 Python 表达式来执行，并返回表达式的计算结果 。例如：

result = eval("1 + 2 * 3")
print(result)  # 输出7

这里字符串 "1 + 2 * 3" 被当作数学表达式计算，返回运算结果 7 。