2022年9月秋招算法工程师笔试题
1 题目
括号匹配问题
定义一个括号串的权值为，它的最长合法括号子序列的长度，例如()())的权值是4，因为它的最长合法括号子序列为()(),求一个给定括号串的所有子串权值之和。
注意，我忘了题目，自己理解的题意是，先求一个字符串的所有子串，并计算子串的权值（即最长合法括号子序列）
并且，权值的计算，我忘记了，不确定是否是这么计算的，我记得的题目给中())())的权值是4。我理解不通。我把题目改成了()())。
我的这种方法，应该算法效率很低，没有在线上运行过
2 python实现
from itertools import combinations
# 求最长合法括号子序列的长度，即权值
def Process(s):
# resl记录最长合法子串的长度
w = 0
stack = list()
for i in range(len(s)):
if stack and s[i] == ")" and s[stack[-1]] == "(":
stack.pop()
# 将当前的右括号加入到栈中, 可以充当分割的作用
else:
stack.append(i)
# 栈非空的时候更新当前的长度, 说明已经匹配完所有的左括号了
if stack:
r = i - stack[-1]
else:
# 说明当前的左括号已经全部消除掉了
r = i + 1
# 合法序列的长度更大则更新, 相等则数目加1
if r > w:
w = r
return w
# 生成所有子串
def generate_s(s):
substring = []
for i in range(1,len(s)+1):
substring.extend(list(combinations(s,i)))
substring = [''.join(i) for i in substring]
return substring
if __name__ == '__main__':
s = '()()())'
score = 0
for i in generate_s(s):
score +=Process(s)
print(score)
