LeetCode刷题实战31:最长有效括号
程序IT圈
共 5943字,需浏览 12分钟
· 2020-09-10
来源:
https://www.cnblogs.com/techflow/p/12393742.html
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做最长有效括号,我们先来看题面:
https://leetcode-cn.com/problems/longest-valid-parentheses/
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
题意
样例
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
题解
暴力
def brute_force(s):
ans = 0
for i in range(len(s)):
if s[i] == '(':
l = r = 0
for j in range(i, len):
if s[j] == '(':
l++
else:
r++
# 如果已经不可能构成答案
if r > l:
break
if r == l:
ans = max(ans, 2 * r)
return ans
寻找模式法
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
ans = 0
l, r = 0, 0
# 正向遍历,寻找)t( 和 )t(两种情况
for i in range(n):
if s[i] == '(':
l += 1
else:
r += 1
if r > l:
l, r = 0, 0
elif r == l:
ans = max(ans, l + r)
l, r = 0, 0
# 反向遍历,寻找(t(这种情况
for i in range(n-1, -1, -1):
# 由于反向遍历,所以非法的判断条件和正向相反
if s[i] == '(':
l += 1
if l > r:
l, r = 0, 0
elif l == r:
ans = max(ans, l+r)
else:
r += 1
return ans
dp
s: a b ( ) )
idx: i-4 i-3 i-2 i-1 i
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
ans = 0
dp = [0 for _ in range(n)]
for i in range(1, n):
if s[i] == ')':
# 如果i-1是(,那么我们判断i-2
if s[i-1] == '(':
dp[i] = 2 + (dp[i-2] if i > 1 else 0)
# 如果i-1也是),我们需要继续往前判断
# 这里要特别注意下下标, 很容易写错
elif i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
dp[i] = 2 + dp[i-1] + (dp[i - dp[i-1] - 2] if i - dp[i-1] - 2 >= 0 else 0)
ans = max(ans, dp[i])
return ans
上期推文:
评论
5000w+ 的大表如何拆?亿级别大表拆分实战复盘
前言笔者是在两年前接手公司的财务系统的开发和维护工作。在系统移交的初期,笔者和团队就发现,系统内有一张5000W+的大表。跟踪代码发现,该表是用于存储资金流水的表格,关联着众多功能点,同时也有众多的下游系统在使用这张表的数据。进一步的观察发现,这张表还在以每月600W+的数据持续增长,也就是说,不超
码农编程进阶笔记
0
好未来测开一面,挺简单!(0428面试原题解析)
大家好,我是二哥呀。今天继续给大家分享春招面试题《好未来测开一面原题》,附详细答案,我会用通俗易懂+手绘图的方式,让天下所有的面渣都能逆袭 😁二哥的 Java 面试指南内容较长,建议正在冲刺 24 届春招和 25 届暑期实习、秋招的同学先收藏起来,面试的时候大概率会碰到,1、二哥的 Linux 速查
沉默王二
0
【性能监控】如何有效监测网页静态资源大小?
前言作为前端人员肯定经常遇到这样的场景:需求刚上线,产品拿着手机来找你,为什么页面打开这么慢呀,心想自己开发的时候也有注意性能问题呀,不可能会这么夸张。那没办法只能排查下是哪一块影响了页面的整体性能,打开浏览器控制台一看,页面上的这些配图每张都非常大,心想这些配图都这么大,页面怎么快,那么我们有没有
高级前端进阶
0
【每周一课#06】MidJourney应用实战
#AI绘画# #MJ# #文生图#时间:4月24日周三 21:00课程大纲:1、关于AIGC:概念、发展历程、就业前景2、MJ基础认识:如何使用、底层逻辑、MJ与SD优缺点比较3、MJ基础功能介绍:任务指令、后缀参数、图生图、图生文、垫图、局部修改等4、MJ应用场景与变现方向
Python涨薪研究所
0
【每周一课#06】MidJourney 应用实战
#AI绘画# #MJ# #文生图#时间:4月24日周三 21:00课程大纲:1、关于AIGC:概念、发展历程、就业前景2、MJ基础认识:如何使用、底层逻辑、MJ与SD优缺点比较3、MJ基础功能介绍:任务指令、后缀参数、图生图、图生文、垫图、局部修改等4、MJ应用场景与变现方向
Python涨薪研究所
0
Java项目实战——打造一款股票区间交易盯盘系统
点击上方“Java进阶学习交流”,进行关注后台回复“Java”即可获赠Java学习资料今日鸡汤身无彩凤双飞翼,心有灵犀一点通。一、简介大家好,我是Snowball。今天给大家分享的内容是基于Java编程,实现股票交易相关功能开发,如果读者对股票或金融衍生物交易不太了解,又比较感兴趣的话可自行查询相关
Java进阶学习交流
0
【PythonCode】力扣Leetcode16~20题Python版
作者通常周更,为了不错过更新,请点击上方“Python碎片”,“星标”公众号前言力扣Leetcode是一个集学习、刷题、竞赛等功能于一体的编程学习平台,很多计算机相关专业的学生、编程自学者、IT从业者在上面学习和刷题。在Leetcode上刷题,可以选择各种主流的编程语言,如C++、JAVA、Pyth
Python 碎片
0
实战必备-数据清洗、数据存储、数据可视化-《AKShare-初阶-实战应用》
✔️课程介绍本课程主要给大家介绍 AKShare 的实战应用部分,主要包括对 AKShare 获取到的数据进行数据清洗,数据存储和数据可视化。课中会提供我们在进行数据处理中的最佳实践!课程目录✔️获取方式如下: 直接购买订阅: ¥39.8/年🔗扫码进入课程店铺:🔅懒得
数据科学实战
31