专栏首页刷题笔记【未完成】7-8 最长有效括号串 (20 分)13分

【未完成】7-8 最长有效括号串 (20 分)13分

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/shiliang97/article/details/101473397

7-8 最长有效括号串 (20 分)

给定一个只含左右小括号的括号串序列exp,找出其中最长的有效括号串。

输入格式:

输入一个只含左右小括号的括号字符串,以换行结束。

输出格式:

输出其中最长的有效括号串。输出的每个括号之后均有空格。

输入样例:

())(()())

输出样例:

在这里给出相应的输出。例如:

( ( ) ( ) ) 

挂掉的代码

#include<iostream>
using namespace std;
int main(){
	string s;
	char c;
	while(c!='\n'){
		c=getchar();
		if(c=='('||c==')'){
			s+=c;
		}
	}
	int max=-1;
	int num=0;
	int maxid=0;
	for(int i=0;i<s.length();i++){
		string s2=s.substr(i);
		int flag=0;
		for(int l=0;l<s2.length();l++){
			if(s2[l]=='('){
				flag++;
			}else{
				flag--;
				if(flag==0){
					if(num>max){
					maxid=i;
					max=num;
					}
				}
				if(flag<0){break;}
				num+=2;
			}
		}
		if(flag>0){
			num=0;
		}
		if(num>max){
			maxid=i;
			max=num;
		}num=0;
		//cout<<maxid<<max<<endl;
	}
	int k=0;
	for(int i=0;i<max&&max>1;i++){
		cout<<s[maxid+i]<<" ";
	}
	cout<<endl;
	return 0;
}

这道题刚好是LeetCode的原题

https://leetcode-cn.com/problems/longest-valid-parentheses/

32. Longest Valid Parentheses

查到的一种力扣的解法

class Solution {  
public:
    int longestValidParentheses(string s) {
        int ans = 0;
        int idx = 0;
        stack<pair<char, int>> sk;
        sk.push(make_pair<char, int>('b', 0));
        for (char c : s){
            idx++;
            if (c == '(')
                sk.push(make_pair(c, idx));
            else{
                pair<char, int> p = sk.top();
                if (p.first == '('){
                    sk.pop();
                    ans = max(ans, idx - sk.top().second); 
                }
                else{
                    assert(p.first == 'b');
                    sk.top().second = idx;
                }
            }
        }
        return ans;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1052 卖个萌 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【LeetCode】221. 最大正方形

    在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

    韩旭051
  • 【LeetCode】977. Squares of a Sorted Array数组 双指针

    Given an array of integers A sorted in non-decreasing order, return an array of ...

    韩旭051
  • PAT 甲级 1001 A+B Format

    1001. A+B Format (20) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程...

    ShenduCC
  • 2015年javaB组1-4题解析与理解

    X老板脾气古怪,他们公司的电话分机号都是3位数,老板规定,所有号码必须是降序排列,且不能有重复的数位。比如:

    萌萌哒的瓤瓤
  • Codeforces Round #512 Div. 2 A,B,C Vasya and Golden Ticket

    题目链接:http://codeforces.com/contest/1058/problem/A

    Ch_Zaqdt
  • 【opencv】带你再学一遍直方图

    直方图到底可以干什么呢?我觉得最明显的作用就是有利于你对这个图像进行分析了,直方图就像我们常用的统计图,只不过直方图统计的是图片的一些特征,例如像素值(这是最常...

    周旋
  • 【有人@我】Android中高亮变色显示文本中的关键字

    应该是好久没有写有关技术类的文章了,前天还有人在群里问我,说群主很长时间没有分享干货了,今天分享一篇Android中TextView在大段的文字内容中如何让关键...

    非著名程序员
  • HDU 2087 剪花布条(裸KMP)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    Ch_Zaqdt
  • PTA刷题记录:L1-034 点赞 (20分)

    题目描述: 微博上有个“点赞”功能,你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签,而你点赞的博文的类型,也间接刻画了你的特性。本题就要...

    英雄爱吃土豆片

扫码关注云+社区

领取腾讯云代金券