`
cozilla
  • 浏览: 91907 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

[Leetcode] Longest Valid Parentheses

 
阅读更多
Longest Valid ParenthesesMar 1 '125700 / 20657

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.

 

之前大摩面试时,问到了这题,当时愚昧了。

一开始,写错了。

后来,想了个N^2的方法。 T_T。

不过好歹这次一次AC :)

struct A {
    A(char cc, int vv=0) : c(cc), v(vv) {}
    char c;
    int v;
};
class Solution {
public:
    
    int longestValidParentheses(string s) {
        int len = s.size();
        if (len == 0) return 0;
        stack<A> st;
        st.push(A(s[0]));
        int cnt = 0;
        for (int i = 1; i < len; i++) {
            cnt = 0;
            if (s[i] == '(') st.push(A(s[i]));
            else {
                while (!st.empty() && st.top().c == '#') {
                    cnt += st.top().v;
                    st.pop();
                }
                
                if (!st.empty() && st.top().c == '(') {
                    cnt += 2;
                    st.pop();
                    st.push(A('#', cnt));
                }
                else {
                    // top().c == '#'
                    if (cnt > 0) st.push(A('#',cnt));
                    st.push(A(')'));
                }
            }
        }
        
        cnt = 0;
        int mx = 0;
        while (!st.empty()) {
            if (st.top().c == '#') {
                cnt += st.top().v;
                if (mx < cnt) mx = cnt;
            } else {
                cnt = 0;
            }
            st.pop();
        }
        return mx;
    }
};

 

 

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        if (n == 0) return 0;
        int i = 0;
        stack<pair<char, int> > st;
        st.push(make_pair('#', 0));
        st.push(make_pair(s[i++], 0));
        while (!st.empty() && i < n) {
            if (s[i] == '(') st.push(make_pair(s[i++], 0));
            else {
                i++;
                int cnt = 0;
                while (st.top().first == '.') cnt += st.top().second, st.pop();
                if (st.top().first == '(') {
                    st.pop();
                    st.push(make_pair('.', cnt + 1));
                }
                else {
                    if (cnt > 0) st.push(make_pair('.', cnt));
                    st.push(make_pair(')', 0));
                }
            }
        }
        int res = 0;
        while (st.top().first != '#') {
            int cnt = 0;
            while (st.top().first == '.') cnt += st.top().second, st.pop();
            res = max(res, cnt);
            while (st.top().first == '(' || st.top().first == ')') st.pop();
        }
        return res*2;
    }
};

 

分享到:
评论

相关推荐

    java-leetcode题解之Longest Valid Parentheses.java

    java java_leetcode题解之Longest Valid Parentheses.java

    js-leetcode题解之32-longest-valid-parentheses.js

    js js_leetcode题解之32-longest-valid-parentheses.js

    C语言-leetcode题解之32-longest-valid-parentheses.c

    c语言入门 C语言_leetcode题解之32-longest-valid-parentheses.c

    颜色分类leetcode-leetcode-[removed]我对Leetcode问题的解决方案

    颜色分类leetcode My Leetcode Problems Solutions Using javascript(ES6) 1 Two Sum 两数之和 5 Longest Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container...

    javalruleetcode-learn-algorithms::laptop:Java实现的各种算法题解

    java lru leetcode ...Parentheses](./leetcode/动态规划-Longest Valid Parentheses.java) [动态规划-Maximum Length of Repeated Subarray](./leetcode/动态规划-Maximum Length of Repeated Subar

    程序员面试宝典LeetCode刷题手册

    第四章 Leetcode 题解 ...20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli

    leetcode怎么改密码-Code:学会学习

    leetcode怎么改密码 Code leetcode easy 测试一下本地的... emmmmm之前修改了一下,现在用ssh提交 应该不用输入密码了吧 ~~emmmmm 先在这里立个flag!!...Longest Valid Parentheses :cross_mark:暴力解法(未通过)

    LeetCode 刷题汇总1

    * 有效的括号(Valid Parentheses):判断括号是否有效。 * 生成括号(Generate Parentheses):生成所有可能的括号组合。 6. 字符串匹配: * 正则表达式匹配(Regular Expression Matching):实现正则表达式...

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...

    LeetCode题解(java语言实现).pdf

    * Valid Parentheses:该题目要求检查括号是否匹配,实现方法使用了栈的数据结构。 * Implement strStr():该题目要求实现字符串查找算法,实现方法使用了Knuth-Morris-Pratt算法。 四、搜索和排序 * Search ...

    Leetcode book刷题必备

    41. Valid Parentheses:验证括号的有效性。 【动态规划】 42. Climbing Stairs:计算爬楼梯的不同方法数。 43. Unique Paths:机器人在一个 m x n 的网格中从左上角移动到右下角,有多少不同的路径。 44. Unique ...

    C语言基础-C语言编程基础之Leetcode编程题解之第32题最长有效括号.zip

    在本资源包中,主题聚焦于C语言的基础学习,特别是针对LeetCode编程挑战中的第32题——"最长有效括号"(Longest ValidParentheses)的解法。LeetCode是一个在线平台,提供了各种算法问题,旨在提升程序员的编程技能...

    lrucacheleetcode-leetcode:leetcode

    Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 25. Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array 27. Remove Element 28. Implement strStr() 3

    javalruleetcode-LeetCode::lollipop:个人LeetCode习题解答仓库-多语言

    java lru leetcode :ice_cream: LeetCode ...Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73

    leetcode530-algorithm:算法

    leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持对于数据结构的熟悉。 ** ...Valid Parentheses 022 Generate Parentheses 028 Implement strStr() 031 Next Permutat

    leetcode双人赛-LeetCode:力扣笔记

    leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 Add Two Numbers 中等 链结串列 重要 Longest Substring Without Repeating Characters 中等 字串 重要 Median of Two Sorted Arrays 困难 数学 ...

    leetcode中国-leetcode:leetcode刷题

    Parentheses 用栈判断括号匹配 Regular Expression Matching 递归匹配 wildcard matching 动态规划 longest common prefix , 简单 valid number, hard, 用有限自动机 integer to roman ,easy , 模拟 roman to ...

    LeetCode答案大全

    20. Valid Parentheses:判断给定的字符串是否是有效的括号字符串。 LeetCode的答案大全中整理的这些问题,包含了算法面试中经常考察的高频知识点,如数组操作、字符串处理、链表处理、数学问题、回溯算法、动态...

    _leetcode-python.pdf

    - Valid Parentheses: 验证给定的字符串中的括号是否有效。这通常可以通过栈结构来实现。 - Merge Two Sorted Lists: 合并两个有序链表。 - Generate Parentheses: 生成所有可能的有效的括号组合。 - Merge k Sorted...

    javalruleetcode-leetcode-java:力码笔记

    Parentheses 26.Remove Duplicates from Sorted Array 53.Maximum Subarray 70.Climbing Stairs 121.Best Time to Buy and Sell Stock 122.Best Time to Buy and Sell Stock II 123.Best Time to Buy and Sell Stock...

Global site tag (gtag.js) - Google Analytics