找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1744|回复: 3
收起左侧

[米群网刷题小分队] 【LeetCode】【Longest Valid Parentheses】

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 11-27-2014 02:45 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
快速通道:
https://oj.leetcode.com/problems/longest-valid-parentheses/

Given a string containing just the characters '(' and')', find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length = 2. Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.


建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)


=========点击传送门查看所有题目哟========
                          汇总贴 传送门
==================================

本帖被以下淘专辑推荐:

发表于 11-27-2014 01:34 PM | 显示全部楼层
思路:前缀扫一次 后缀扫一次 遇到负数就跳过。。。
代码:
  1. class Solution {
  2. public:
  3.     int longestValidParentheses(string s) {
  4.         // IMPORTANT: Please reset any member data you declared, as
  5.         // the same Solution instance will be reused for each test case.
  6.         int answer = 0, depth = 0, start = -1;
  7.         for (int i = 0; i < s.size(); ++i) {
  8.             if (s[i] == '(') {
  9.                 ++depth;
  10.             }
  11.             else if (--depth < 0) {
  12.                 start = i;
  13.                 depth = 0;
  14.             }
  15.             else if (depth == 0) {
  16.                 answer = max(answer, i - start);
  17.                
  18.             }
  19.         }
  20.         depth = 0;
  21.         start = s.size();
  22.         for (int i = s.size() - 1; i >= 0; --i) {
  23.             if (s[i] == ')') {
  24.                 ++depth;
  25.             }
  26.             else if (--depth < 0) {
  27.                 start = i;
  28.                 depth = 0;
  29.             }
  30.             else if (depth == 0) {
  31.                 answer = max(answer, start - i);
  32.             }
  33.         }
  34.         return answer;
  35.         
  36.     }
  37. };
复制代码

复杂度分析:
时间O(N) 空间可以做到O(1)
细节和陷阱:
优化空间复杂度
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
回复 支持 反对

使用道具 举报

9

主题

0

精华

51

积分

资深会员

Rank: 2

积分
51
发表于 11-29-2014 02:22 AM | 显示全部楼层
思路:  len[i] = len[i-1] + len[l-1] +2;   // l 是左边 括号的idx
()()
()(())  
    public int longestValidParentheses(String s) {
        if( s == null || s.length() == 0)
            return 0;
        int res = 0;
        int max = 0;
        int[] len = new int[s.length()];
        Stack<Integer> stack = new Stack<Integer>();
        for( int i=0; i<s.length(); i++ ){
            if( s.charAt(i) == '(' ){
                stack.push(i);
            }
            else{
                if( !stack.isEmpty() ){
                    int idx = stack.pop();
                    len[i] = (idx > 0 ? len[idx-1]:0) +  (i>0 ? len[i-1]:0) + 2;
                    max = Math.max( max, len[i]);
                }
            }
        }
        return max;
    }
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表