首页 > 其他分享 >最长有效括号

最长有效括号

时间:2022-11-08 19:14:05浏览次数:69  
标签:有效 int max ++ 最长 括号 length stack

题目

给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

示例 1:

输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"
示例 2:

输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"
示例 3:

输入:s = ""
输出:0

提示:

0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

暴力枚举

超时

public static int longestValidParentheses(String s) {
        int max=0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = s.length(); j >=i ; j--) {
                if(j-i<max)
                {
                    break;
                }
                String temp = s.substring(i,j);
                if(isTrueKuoHao(temp))
                {
                    max=Math.max(max,temp.length());
                    break;
                }
            }
        }
        return max;
    }
    public static boolean isTrueKuoHao(String s)
    {
        if(s.length()==0)
        {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)=='(')
            {
                stack.push('(');
            }
            else
            {
                if(!stack.isEmpty())
                {
                    stack.pop();
                }
                else
                {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

双指针遍历

  • 解题思路
    左括号数量一定大于等于右括号数量,当左括号数量小于有括号数量的时候,重新计算长度,当等于右括号数量的时候,计算一下最大长度。
public static int longestValidParentheses2(String s) {
        int max=0;
        for (int i = 0; i < s.length()-1; i++) {
            if(s.charAt(i)!='(')
            {
                continue;
            }
            int left=1;
            int right=0;
            for (int j = i+1; j < s.length(); j++) {
                if(s.charAt(j)=='(')
                {
                    left++;
                }
                else
                {
                    right++;
                }
                if(right>left)
                {
                    break;
                }else if(left==right)
                {
                    max=Math.max(max,left+right);
                }
            }
        }
        return max;
    }

  • 解题思路
    先往栈中压入一个-1,然后循环遍历这个字符串,当等于左括号时,压序号入栈,当等于右括号时,出栈。然后判断栈空没有,空了的话,插入当前序号入栈,表示当前序号分割了括号的连续;不空的情况,可以计算一下当前连续括号的长度
    public static int longestValidParentheses3(String s)
    {
        Stack<Integer> stack =new Stack<>();
        stack.push(-1);
        int len = 0;
        int maxLen=0;
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)=='(')
            {
                stack.push(i);
            }
            else
            {
                stack.pop();
                if(stack.isEmpty())
                {
                    stack.push(i);
                }
                else
                {
                    int pre = stack.peek();
                    len = i-pre;
                    maxLen=Math.max(len,maxLen);
                }

            }

        }
        return maxLen;
    }

标签:有效,int,max,++,最长,括号,length,stack
From: https://www.cnblogs.com/huacha/p/16870822.html

相关文章

  • 用 JavaScript 编写枚举的最有效方法
    英文|https://betterprogramming.pub/the-most-efficient-way-to-write-enumerations-in-javascript-a1b9f41ea651JavaScript语言本身不支持枚举。如果我们想模拟枚举,我......
  • 问题 N: 零基础学C/C++159——最长字符串
    题目一点也不难哦,就是要学会二维数组的输入输出但是不知为何这题有一个很奇怪的坑,如果你是AC:83%那么恭喜你掉坑里了!!这道题目竟然有一个检测点在最后的时候加\n确实......
  • UNTX部署到IIS,亲测有效
    一、安装服务器需要的环境1.安装Node.js下载地址:http://nodejs.cn/download,根据服务器环境选择对应版本的安装包即可,本人选的是Windows64位的.msi安装包......
  • leetcode 300. 最长递增子序列 js 动态规划实现
    给你一个整数数组nums,找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]是数组[0......
  • 最长上升子序列
    题目:题解:#include<bits/stdc++.h>usingnamespacestd;longlonga[1005];longlongf[1005];intmain(){intn;cin>>n;for(inti=1;i<=n;i++){......
  • 最长上升子序列 II
    题目:题解:使用二分#include<bits/stdc++.h>usingnamespacestd;constintN=5e5+10;longlonga[N],f[N];intcon;intfind(intx){intl=1,r=con;while(l<r){......
  • 【模板】最长回文串长度 manacher
    \(pa_i\)表示以\(i\)为中心的(原串的)回文串长度#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;typedeflonglongLL;intn,m,pa[......
  • 降低模拟量信号干扰的10个有效方法
    想要快速有效地降低模拟量信号传输干扰,可以从以下10个方面着手:1.专用接地首先,PLC系统有自己的专用接地,做到这一点,很多干扰问题都会迎刃而解。2.隔离变压器PLC供电加隔离变压......
  • 32. 最长有效括号
    32.最长有效括号题解:合法子串中num('(')>num(')')左右括号的数量相等合法序列的前缀num('(')>=num(')')左括号的序列要大于右括号的序列如果出现num('(')<......
  • [dp 记录]szjudge#26 括号序列
    dp部分平凡,但是后面找最值是值得深思的。题意:给出两个由左右括号形成的字符串,求在长度最小的基础上字典序最小的合法括号序列,使给出字符串均为其子串。\(|s|,|t|\leq30......