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-23增量更新怎么做?-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些?-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码?-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗?-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行?-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
- 2024-11-23oss直传有什么好处?-icode9专业技术文章分享
- 2024-11-23如何将oss直传封装成一个组件在其他页面调用时都可以使用?-icode9专业技术文章分享
- 2024-11-23怎么使用laravel 11在代码里获取路由列表?-icode9专业技术文章分享
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能?-icode9专业技术文章分享