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声明式导航、声明式导航传参接收两种方式

相关内容

热门资讯

安卓系统所有手机通用,揭秘所有... 你有没有发现，现在市面上各种各样的手机，品牌琳琅满目，让人挑花了眼？不过，不管你用的是哪个品牌的手机...
安卓系统变ios系统好用吗,体... 你有没有想过，为什么有些人从安卓手机换到了苹果的iPhone，而且好像换了之后整个人都精神焕发呢？没...
华为安卓系统文件删除,轻松掌握... 你有没有遇到过这种情况？手机里的文件突然不见了，尤其是华为安卓系统里的那些重要文件，真是让人心头一紧...
安卓1.5系统软件,初代智能革... 你有没有想过，手机里的那些看似普通的系统，其实背后藏着无数的故事呢？今天，就让我带你走进安卓1.5系...
安卓 代替系统音效设置,打造个... 你有没有发现，手机里的那些系统音效有时候真的让人有点烦躁呢？比如那个每次接电话时“叮咚”一声，或者是...
安卓系统整体性,构建移动设备的... 你知道吗？在智能手机的世界里，安卓系统就像是个全能的魔术师，它不仅拥有丰富的魔法，还能让各种神奇的魔...
安卓系统能玩鬼泣么?,畅享动作... 你有没有想过，在安卓系统上玩《鬼泣》这款游戏会是怎样的体验呢？没错，就是那个让你热血沸腾、挑战极限的...
安卓系统手机编曲软件,音乐创作... 你有没有想过，用手机也能轻松编曲？没错，就是那个你每天不离手的安卓系统手机！现在，我就要给你揭秘几款...
车载导航显示安卓系统,车载导航... 你有没有发现，现在的车载导航系统越来越智能了？尤其是那些搭载了安卓系统的车载导航，简直就像是个贴心的...
安卓系统启动黑屏,安卓系统启动... 手机屏幕突然黑了，这可怎么办？别急，今天就来和你聊聊安卓系统启动黑屏这个让人头疼的问题。你知道吗，这...
怎么解除订阅安卓系统,安卓系统... 你是不是也和我一样，手机里订阅了好多服务，结果现在想解除订阅，却一头雾水？别急，今天就来手把手教你如...
安卓系统停用怎么开启,轻松恢复... 亲爱的手机控们，你是否曾经遇到过安卓系统突然停用的情况，让你手忙脚乱，不知所措？别担心，今天就来教你...
安卓系统电池健康度,电池健康度... 你有没有发现，你的安卓手机最近是不是有点儿不给力了？电池续航能力大不如前，充电速度也慢了不少？别急，...
安卓系统按键怎么截图,安卓系统... 你是不是也和我一样，有时候想截个图分享给朋友，却发现安卓手机的截图功能有点神秘呢？别急，今天就来手把...
购票系统安卓源代码,架构设计与... 你有没有想过，那些我们每天离不开的购票系统，它们背后的秘密是什么呢？今天，就让我带你一探究竟，揭开购...
安卓手机系统后台测试,深度解析... 你有没有发现，你的安卓手机后台总是悄悄地忙碌着？别小看了这些后台程序，它们可是手机系统稳定运行的关键...
安卓系统重启的图标,解锁设备新... 手机突然重启，是不是心里有点慌？别急，今天就来和你聊聊安卓系统重启的图标，让你一眼就能认出它，再也不...
车载智慧屏安卓系统,智能出行新... 你有没有发现，现在的车载智慧屏越来越智能了？尤其是那些搭载了安卓系统的，简直就像是个移动的小电脑，不...
安卓系统连上网权限,解锁设备无... 你有没有发现，你的安卓手机里有些应用总是偷偷连上网？别小看这个小小的网络权限，它可是能影响你隐私、消...
安卓谷歌操作系统,探索安卓谷歌... 你知道吗？在智能手机的世界里，有一个操作系统可是无人不知、无人不晓，那就是安卓谷歌操作系统。它就像一...