Hard | LeetCode 32. 最长有效括号 | 正反方向扫描
2021/7/17 23:35:44
本文主要是介绍Hard | LeetCode 32. 最长有效括号 | 正反方向扫描,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
32. 最长有效括号
给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例 1:
输入:s = "(()" 输出:2 解释:最长有效括号子串是 "()"
示例 2:
输入:s = ")()())" 输出:4 解释:最长有效括号子串是 "()()"
示例 3:
输入:s = "" 输出:0
提示:
0 <= s.length <= 3 * 104
s[i]
为'('
或')'
解题思路
方法一
从左往右扫描, 对'('
和')'
进行计数。如果左括号的数量大于右括号, 最长有效的长度还能继续增加。如果等于右括号, 则要把当前的长度记录下来, 这个长度是一个候选的答案。如果小于。则需要将技术归零。重新找第一个左括号。
但是上面的策略有一个问题'()()(()()()'
, 对于这种情况, 长度应该是6。由于这个过程, 左括号数量在经过第一个长度4的子串之后, 左括号数量一直大于右括号, 不会等于右括号。则右半边的长度为6的子串无法得到结果。这种情况只需要使用同样的算法从右往左扫描一遍, 就能找到右边的子串的长度了。
public int longestValidParentheses(String s) { int left = 0, right = 0, maxlength = 0; for (int i = 0; i < s.length(); i++) { // 从左往右扫描, 对左、右括号分别进行计数 if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { // 当左右括号数量相等。则找到一个候选的值。 maxlength = Math.max(maxlength, 2 * right); // left = right = 0 这个时候计数器不归零。因为'()()'是连续的, 长度是4, 归零只能得到一段的效果 } else if (right > left) { // 当右括号的数量大于左括号, 则将计数归零。因为这是无意义的。 left = right = 0; } } // 由于使用上面的策略遇到'(()'的情况计算不出结果, 所以需要反方向再扫描一遍。 left = right = 0; for (int i = s.length() - 1; i >= 0; i--) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { maxlength = Math.max(maxlength, 2 * left); } else if (left > right) { left = right = 0; } } return maxlength; }
这篇关于Hard | LeetCode 32. 最长有效括号 | 正反方向扫描的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享