LeetCode第32题-最长有效括号-java实现-图解思路与手撕代码
admin
2024-04-04 14:43:43
0次

LeetCode第32题-最长有效括号-java实现-图解思路与手撕代码

文章目录

  • 一、题目描述
  • 二、解题思路与代码实现
    • 1.解题思路
    • 2.代码实现
  • 总结

一、题目描述

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

二、解题思路与代码实现

1.解题思路

对于最长类问题，可以考虑采用动态规划解决问题。

首先创建数组dp，遍历字符串s。

如果s(i)=('，则dp(i)=0

如果s(i)=‘)’，有两种情况：

若s(i-1)=‘(’，则

dp(i)=dp(i-1)+2

若s(i-1)=‘)’，且s(i-dp(i-1)-1)=‘(’，则

dp(i)=dp(i-1)+dp(i-dp(i-1)-2)+2

其余情况dp(i)=0。

2.代码实现

代码如下（示例）：

    private static int longestValidParentheses(String s) {if (s.length() <= 1) {return 0;}char[] ch = s.toCharArray();int res = 0;int[] dp = new int[s.length()];dp[0] = 0;for (int i = 1; i < s.length(); i++) {if (ch[i] == '(') {dp[i] = 0;} else {if (ch[i - 1] == '(') {dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;} else {if (i - dp[i - 1] - 1 >= 0 && ch[i - dp[i - 1] - 1] == '(') {dp[i] =i - dp[i - 1] - 2>=0 ? dp[i - 1] + dp[i - dp[i - 1] - 2] + 2:dp[i - 1] +  2;} else {dp[i] = 0;}}res = Math.max(res, dp[i]);}}return res;}

注意：其中数组下标要先确定没有越界。

总结

对于最长类问题，可以使用动态规划进行求解。

动态规划题目分析的 4 个步骤：

1、确定状态
2、转移方程
根据问题定义得到
3、初始条件和边界情况
4、计算顺序

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：Javase --- 多线程复习

下一篇：Vue08/Vue 配置路由规则 、Vue声明式导航、声明式导航传参接收两种方式

相关内容

热门资讯

安卓系统的如何测试软件,从入门... 你有没有想过，你的安卓手机里那些神奇的软件是怎么诞生的呢？它们可不是凭空出现的，而是经过一系列严格的...
小米8安卓系统版本,安卓系统版... 你有没有发现，手机更新换代的速度简直就像坐上了火箭呢？这不，小米8这款手机自从上市以来，就凭借着出色...
华为手机安卓系统7以上,创新体... 你有没有发现，最近华为手机越来越受欢迎了呢？尤其是那些搭载了安卓系统7.0及以上版本的机型，简直让人...
儿童英语免费安卓系统,儿童英语... 哇，亲爱的家长朋友们，你是否在为孩子的英语学习发愁呢？别担心，今天我要给你带来一个超级好消息——儿童...
ios系统切换安卓系统还原,还... 你有没有想过，有一天你的手机从iOS系统切换到了安卓系统，然后再从安卓系统回到iOS系统呢？这听起来...
灵焕3装安卓系统,引领智能新体... 你知道吗？最近手机圈里可是掀起了一股热潮，那就是灵焕3这款神器的安卓系统升级。没错，就是那个曾经以独...
安卓系统指南针软件,探索未知世... 手机里的指南针功能是不是让你在户外探险时倍感神奇？但你知道吗，安卓系统中的指南针软件可是大有学问呢！...
华为是不用安卓系统了吗,迈向自... 最近有个大新闻在科技圈里炸开了锅，那就是华为是不是不再使用安卓系统了？这可不是一个简单的问题，它涉及...
安卓系统热点开启失败,排查与解... 最近是不是你也遇到了安卓系统热点开启失败的小麻烦？别急，让我来给你详细说说这个让人头疼的问题，说不定...
小米max2系统安卓,安卓系统... 你有没有听说过小米Max2这款手机？它那超大的屏幕，简直就像是个移动的电脑屏幕，看视频、玩游戏，那叫...
电池健康怎么保持安卓系统,优化... 手机可是我们生活中不可或缺的好伙伴，而电池健康度就是它的生命力。你有没有发现，随着使用时间的增长，你...
安卓手机怎么调系统颜色,安卓手... 你有没有发现，你的安卓手机屏幕颜色突然变得不那么顺眼了？是不是也想给它换换“脸色”，让它看起来更有个...
安卓系统清粉哪个好,哪款清粉工... 手机用久了，是不是觉得卡得要命？别急，今天就来聊聊安卓系统清理垃圾哪个软件好。市面上清理工具那么多，...
华为被限制用安卓系统,挑战安卓... 你知道吗？最近科技圈可是炸开了锅！华为，这个我们耳熟能详的名字，竟然因为一些“小插曲”被限制了使用安...
安卓系统是不是外国,源自外国的... 你有没有想过，我们每天离不开的安卓系统，它是不是外国货呢？这个问题听起来可能有点奇怪，但确实很多人都...
安卓系统缺少文件下载,全面解析... 你有没有发现，用安卓手机的时候，有时候下载个文件真是让人头疼呢？别急，今天就来聊聊这个让人烦恼的小问...
kktv系统刷安卓系统怎么样,... 你有没有听说最近KKTV系统刷安卓系统的事情？这可是个热门话题呢！咱们一起来聊聊，看看这个新玩意儿到...
安卓系统连接电脑蓝牙,操作指南... 你有没有遇到过这种情况：手机里堆满了各种好用的应用，可就是想找个方便快捷的方式，把手机里的音乐、照片...
安卓车机11.0系统包,智能驾... 你有没有发现，最近你的安卓车机系统好像悄悄升级了呢？没错，就是那个安卓车机11.0系统包！这可不是一...
安卓系统最高到多少,从初代到最... 你有没有想过，你的安卓手机系统升级到哪一步了呢？是不是好奇安卓系统最高能到多少呢？别急，今天就来带你...