首页 > 编程语言 >python 最长有效括号 多种解法

python 最长有效括号 多种解法

时间:2024-01-15 14:00:53浏览次数:42  
标签:python max else 括号 length 解法 stack dp

  1. 使用栈: 遍历字符串,当遇到左括号时,将其下标压入栈中;当遇到右括号时,如果栈为空,则将当前右括号下标作为新的起始点,否则将栈顶元素出栈,并计算当前有效括号的长度。 Python代码示例:
def longest_valid_parentheses(s):
    stack = [-1]  # 栈中始终保持一个起始位置
    max_length = 0
    for i in range(len(s)):
        if s[i] == '(':
            stack.append(i)
        else:
            stack.pop()
            if len(stack) == 0:
                stack.append(i)
            else:
                max_length = max(max_length, i - stack[-1])
    return max_length
  1. 使用动态规划: 定义一个动态规划数组 dp,其中 dp[i] 表示以索引 i 结尾的最长有效括号的长度。对于每个右括号,需要考虑其前面的字符是否是左括号,如果是,则可以与该左括号匹配,此时的最长有效括号长度为 dp[i-2] 加上 2;还需要考虑右括号前面的字符是否是右括号,如果是,则需要找到与当前右括号匹配的左括号的前一个位置 j,此时的最长有效括号长度为 dp[i-1] 加上 2 再加上 dp[j-1]。 Python代码示例:
def longest_valid_parentheses(s):
    n = len(s)
    dp = [0] * n
    max_length = 0
    for i in range(1, n):
        if s[i] == ')':
            if s[i - 1] == '(':
                dp[i] = dp[i - 2] + 2 if i >= 2 else 2
            elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == '(':
                dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] >= 2 else 0) + 2
            max_length = max(max_length, dp[i])
    return max_length

标签:python,max,else,括号,length,解法,stack,dp
From: https://blog.51cto.com/lzning/9254035

相关文章

  • python学习
    dic={'名字':'小明','身高':168,'体重':55}print(dic['名字']+'的身高是'+str(dic['身高'])+'cm,'+'体重是'+str(dic['体重'])+'kg.')打印字典中的整形时记得转成字符串#......
  • python测试系列教程——python+Selenium+chrome自动化测试框架
    python测试系列教程——python+Selenium+chrome自动化测试框架需要的环境浏览器(Firefox/Chrome/IE…)PythonSeleniumSeleniumIDE(如果用Firefox)FireBug、FirePath(如果用Firefox)chromedriver、IEDriverServer、phantomjs.exeIDE(Pycharm/Sublime/Eclipse…)1、浏览器建议......
  • Python和RPA网页自动化-发送邮件
    以163邮箱为例,分别使用Python和RPA网页自动化发送邮件到指定邮箱其中2个方法都需要用到163邮箱授权码,开启IMAP/SMTP服务即可得到授权码(POP3/SMTP服务不用开启) 1、python代码如下importsmtplibfromemail.mime.textimportMIMETextfromemail.headerimportHeaderdef......
  • python多线程模块:threading使用方法(参数传递)
    先来看这段代码:importthreadingimporttimedefworker():print“worker”time.sleep(1)returnforiinxrange(5):t=threading.Thread(target=worker)t.start()这段代码就使用了多线程,但是没法传递参数,而实际使用多线程,往往是需要传递参数的......
  • Python 3各版本的新特性对比
    Python3各版本的新特性对比作者:HankZheng2024-01-1500:30:04开发前端Python3系列的各个版本都带来了许多重要的新特性和改进,从语法到标准库的增强,都为开发者提供了更好的编程体验和更高效的开发方式。Python是一种简单易学、功能强大的编程语言,广泛应用于各个领域。Py......
  • Python打包exe文件方法汇总【4种】
    Python作为解释型语言,发布即公开源码,虽然是提倡开源但是有些时候就是忍不住想打包成exe,不仅仅是为了对代码进行加密,而是为了跨平台。防止有些没有安装py环境的电脑无法运行软件。目录对python代码打包成exe的方式有4种,py2exe,pyinstaller,cx_Freeze,nuitka,分别对以上4种方法介绍,欢迎......
  • 使用 Python 将数据写入 Excel 工作表
    在数据处理和报告生成等工作中,Excel表格是一种常见且广泛使用的工具。然而,手动将大量数据输入到Excel表格中既费时又容易出错。为了提高效率并减少错误,使用Python编程语言来自动化数据写入Excel表格是一个明智的选择。Python作为一种简单易学且功能强大的编程语言,其丰富的......
  • Python-ttk的标签
    1:效果图2:代码importttkbootstrapasttkfromttkbootstrap.constantsimport*root=ttk.Window()ttk.Label(root,text="标签1",bootstyle=INFO).pack(side=ttk.LEFT,padx=5,pady=10)ttk.Label(root,text="标签2",bootstyle="inverse").pack(s......
  • 怎么在python中改进lightgbm 算法
    改进LightGBM算法通常涉及一系列步骤,这取决于你的数据集、问题的特点以及已有模型的性能。以下是一些建议:数据预处理和特征工程:处理缺失值:使用适当的方法填充或删除缺失值。异常值处理:检测并处理异常值,以确保模型对数据的噪声具有鲁棒性。特征缩放:确保特征在相似的范围内,可以......
  • 搭建 虚拟python conda环境
    查看当前conda所有环境condainfo--envs使用如下语句创建环境,kafka_monitor为我的环境名condacreate-nkafka_monitorpython=3.8删除环境condaenvremove-nkafka_monitor激活环境,安装python包sourceactivatekafka_monitorcondainstallpandascondainstallpymysql......